Reply to thread

Message: [QUOTE="JSH, post: 3597556"] That's what I thought to do at first as well, which was last week, but after pondering the problem for some days I decided that an equal weight for distance along all nodes was preferable, if no distance between nodes is given as then one can assume that distance is equally weighted or wouldn't it be included? And besides it's easy. The m-1 dimensional space provides an easy solution to the issue, and equal weights distance. I think it's more fun now to go after the general problem, though the concept I'm using is easier I think to understand with the Euclidean, as distance is so key to it, so I'll babble on a bit here on that issue though now I'll get more speculative. I think it's provable to solve the Euclidean TSP by considering in a 2- D space a ring going outward from a start of just two nodes with the forward traveler on one and the backwards traveler on another, where these nodes are well behaved in that you can expand a circle out and get only 4 new nodes at a time, and the weight is the distance, and then consider the decision points of picking the best path, where also the best path tends to go in one direction--so I'm cheating a bit to make it easier to conceptualize. Then the idea I have is like chewing at the problem from both ends, as each traveler gets two nodes at a time and there must be a best path between those two, so you move the travelers out and expand your circle to get 4 more nodes and do so until you have all nodes. Key here is that one traveler is moving forward in time while the other is moving backwards so at the end you collapse your solution to one traveler moving forward from the starting point to the end. AT each decision point you picked the shortest so the final full path is the shortest one. Lots of problems with the specifics of that thought experiment as it's very well behaved, but maybe it can give an idea of why using two travelers--one going forward in time while the other goes backwards in time--is so key of an idea! Without that, if you have one traveler in the middle of your graph on one node and expand your circle to have just two more nodes, how do you get to an end? How do you get to your beginning? My idea allows you to start in the middle, and work your way out from BOTH sides. James Harris [/QUOTE]

Verification