### 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 T

To use the algorithm and take them to the next nodes, T

Then T

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.

T

T

In this way, all possible moves by T

A special case occurs if there are only 3 nodes left, meaning only one is unvisited, and in this case the algorithm arbitrarily has T

Notice that when the algorithm exits you have a path taken by T

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 T

_{1}and T_{2}, 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 N_{1}.To use the algorithm and take them to the next nodes, T

_{1}considers moving to another node, which I'll say is N_{2}.Then T

_{2}considers moving to all other nodes available, not currently under consideration by T_{1}, and not already visited, so T_{2}might start with N_{3}and proceed from there, and calculates the cost×distance from each path BACK to N_{1}because T_{2}is moving BACKWARDS, while T_{1}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.

T

_{2}considers every available move back to N_{1}, and selects the one with the least value, and returns that information.T

_{1}stores that info and now considers moving to N_{3}, and T_{2}now calculates for all available nodes again, excluding the one under consideration or already visited, so now T_{2}could start with N_{2}and loop through all available, and again T_{2}picks the lowest cost move BACK to N_{1}and returns that to T_{1}.In this way, all possible moves by T

_{1}and T_{2}are considered, and after T_{1}has gotten values back from T_{2}for each possible move, T_{1}selects the lowest cost move, and then BOTH T_{1}and T_{2}make their moves, and T_{1}moves forward to the node that fits that least path, while T_{2}moves BACKWARD to the node that does, where those will be different nodes and there is a rule that T_{1}and T_{2}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 T

_{1}move forward to that node.Notice that when the algorithm exits you have a path taken by T

_{1}and a path taken by T_{2}, but you collapse that into a single journey by a single traveler moving along the path of T_{1}, and then continuing forward along the path of T_{2}, where to conceptualize it, T_{2}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.