Thursday, July 24, 2008
Distance normalized TSP algorithm
I came up with this idea for figuring out a path with the Traveling Salesman Problem and posted about it, and an objection that came up was the the algorithm required the distance between each of the nodes, while the standard problem does not require this information.
In reaction to that objection I got upset, but now after taking some time to think and ponder the problem I found I could handle the issue easily so that a new distance normalized algorithm could handle any TSP setup.
The simple idea is that if there are m nodes, and there is no distance information between nodes given, then they are to be considered to be embedded in an m−1 dimensional space equidistant from each other.
Then the algorithm proceeds as before, where you have two travelers T1 and T2, where I'll talk through a single weight, but you can have multiple weights. With a single weight between nodes, I'll use cost to keep the idea closer to the standard way of stating the problem, and also so that they complete a round trip circuit, I'll say they begin from the same node N1.
To use the algorithm and take them to the next nodes, T1 considers moving to another node, which I'll say is N2.
Then T2 considers moving to all other nodes available, not currently under consideration by T1, and not already visited, so T2 might start with N3 and proceed from there, and calculates the cost×distance from each path BACK to N1 because T2 is moving BACKWARDS, while T1 is moving forwards.
Notice that with the distance normalized algorithm you just have cost considered as distance=1. Also if there are multiple weights you simply multiply by each weight, so if there were a cost and a time for each path, you'd have cost×time×distance and so forth.
T2 considers every available move back to N1, and selects the one with the least value, and returns that information.
T1 stores that info and now considers moving to N3, and T2 now calculates for all available nodes again, excluding the one under consideration or already visited, so now T2 could start with N2 and loop through all available, and again T2 picks the lowest cost move BACK to N1 and returns that to T1.
In this way, all possible moves by T1 and T2 are considered, and after T1 has gotten values back from T2 for each possible move, T1 selects the lowest cost move, and then BOTH T1 and T2 make their moves, and T1 moves forward to the node that fits that least path, while T2 moves BACKWARD to the node that does, where those will be different nodes and there is a rule that T1 and T2 can never move to the same node.
A special case occurs if there are only 3 nodes left, meaning only one is unvisited, and in this case the algorithm arbitrarily has T1 move forward to that node.
Notice that when the algorithm exits you have a path taken by T1 and a path taken by T2, but you collapse that into a single journey by a single traveler moving along the path of T1, and then continuing forward along the path of T2, where to conceptualize it, T2 is the same traveler moving backwards in time to meet himself moving forwards.
I am prepared to step through a simple example if that is necessary but would not mind if someone else might help out in that regard, as I'm curious to know if ANYONE else in the world can understand this algorithm!!!
It seems so simple to me but often it's hard to explain something new to people so I understand that it may take some time and patience for others to know how to do the algorithm and I apologize for getting frustrated and angry before, versus just coming up with the normalized algorithm earlier.
Oh yeah, I'm still angling for coders if I can get some people interested in this thing, as I have a Google Code project called optimalpathengine.
In reaction to that objection I got upset, but now after taking some time to think and ponder the problem I found I could handle the issue easily so that a new distance normalized algorithm could handle any TSP setup.
The simple idea is that if there are m nodes, and there is no distance information between nodes given, then they are to be considered to be embedded in an m−1 dimensional space equidistant from each other.
Then the algorithm proceeds as before, where you have two travelers T1 and T2, where I'll talk through a single weight, but you can have multiple weights. With a single weight between nodes, I'll use cost to keep the idea closer to the standard way of stating the problem, and also so that they complete a round trip circuit, I'll say they begin from the same node N1.
To use the algorithm and take them to the next nodes, T1 considers moving to another node, which I'll say is N2.
Then T2 considers moving to all other nodes available, not currently under consideration by T1, and not already visited, so T2 might start with N3 and proceed from there, and calculates the cost×distance from each path BACK to N1 because T2 is moving BACKWARDS, while T1 is moving forwards.
Notice that with the distance normalized algorithm you just have cost considered as distance=1. Also if there are multiple weights you simply multiply by each weight, so if there were a cost and a time for each path, you'd have cost×time×distance and so forth.
T2 considers every available move back to N1, and selects the one with the least value, and returns that information.
T1 stores that info and now considers moving to N3, and T2 now calculates for all available nodes again, excluding the one under consideration or already visited, so now T2 could start with N2 and loop through all available, and again T2 picks the lowest cost move BACK to N1 and returns that to T1.
In this way, all possible moves by T1 and T2 are considered, and after T1 has gotten values back from T2 for each possible move, T1 selects the lowest cost move, and then BOTH T1 and T2 make their moves, and T1 moves forward to the node that fits that least path, while T2 moves BACKWARD to the node that does, where those will be different nodes and there is a rule that T1 and T2 can never move to the same node.
A special case occurs if there are only 3 nodes left, meaning only one is unvisited, and in this case the algorithm arbitrarily has T1 move forward to that node.
Notice that when the algorithm exits you have a path taken by T1 and a path taken by T2, but you collapse that into a single journey by a single traveler moving along the path of T1, and then continuing forward along the path of T2, where to conceptualize it, T2 is the same traveler moving backwards in time to meet himself moving forwards.
I am prepared to step through a simple example if that is necessary but would not mind if someone else might help out in that regard, as I'm curious to know if ANYONE else in the world can understand this algorithm!!!
It seems so simple to me but often it's hard to explain something new to people so I understand that it may take some time and patience for others to know how to do the algorithm and I apologize for getting frustrated and angry before, versus just coming up with the normalized algorithm earlier.
Oh yeah, I'm still angling for coders if I can get some people interested in this thing, as I have a Google Code project called optimalpathengine.
# posted by James Harris @ 22:31 
