J

#### JSH

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_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.

James Harris