J
JSH
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_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
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