Traveling salesman, idea, easy to program?

[JSH]

Besides my open source Class Viewer project I have a rep for throwing
ideas out on Usenet, where I did that for years with math, argued with
a lot of math people, and they hate me, but that's a side issue to the
subject of this post as I was wondering today what problem I might
solve to kind of prove myself and came up with an algorithm for the
traveling salesman problem.

My algorithm has TWO travelers: the forward traveler and the backwards
traveler.

Where to understand the idea I don't have the traveler get back to his
original destination at first, though that's easily added later.

The backwards traveler is actually the same traveler, but traveling
backwards in time along the optimal path, so the assumption is that
the problem is solved, but so what? What good is a backwards traveler
added with the normal forward traveler?

Well, now you can optimize the path from both ends simply enough:
with nodes and paths like normal, assume your forwards traveler is at
the start while your backwards traveler is at the end.

Now the forwards traveler steps forward to a node, doesn't matter
which one so say the closest to keep it simple. The backwards
traveler then BACKS to each node that is left in turn, and at each
calculates the time from that node--he's traveling backwards in time--
and multiplies that for each node times its straight line distance to
the forwards traveler at his node.

Then the backwards traveler just picks whichever node has the minimum
time*straight-line distance value, and holds that value.

The forwards traveler now goes to another node, and the backwards
traveler does the same thing as above, and they do this process until
each first possible step is covered.

So now there is a series of values for each node for the forwards
traveler, and he picks the one that is minimal, and then each traveler
steps to the appropriate node for that path, which notice is covering
the ends of your total path.

And then they do the same process again.

As they iterate through, they must eventually meet, so the forward
times traveler meets himself going backwards through time and you have
the minimal path--I hope.

You need one more rule: each node is only visited once, so as each
node is visited paths to it are removed.

And that's it.

Looking over literature quickly while checking to see if anyone else
already had this algorithm, I noticed that no one did and that the
algorithms I saw looked forward only, while this approach chops the
problem up iteratively from both sides, so you're solving it at both
ends.

The algorithm itself is polynomial time, as if there are m+2 nodes,
where 2 of them are the starting and ending nodes then the first
iteration has (m-1)^2 value calculations, while the second has (m-3)^2
and so forth.

The idea is generalizable to other limiting factors like cost, as you
just multiply everything together, so like to get the shortest
possible path in the shortest time with the shortest cost, you'd
multiply distance*time*cost for each path and take the minimum.

Oh yeah, so how do you do the classical problem of getting back to
your original destination?

Easy. Both travelers start from the same point, and otherwise
everything is the same.

The proof that it is a solution has to do with other stuff more
mathematical so I leave that off, as even if you don't think it does,
how hard is that idea to program, eh?

And now you know how I got hated by mathematicians with my wild ideas
and extreme creativity.

Mathematicians around the world DESPISE me for posts like this one as
they see them as insulting to think that I could dare to solve a hard
and difficult problem that brilliant people have worked on for years.

But I say, why can't I just toss some ideas out there? What really is
so wrong with that?

So I think math people are the ones with the problem. Not me.


James Harris

 

[Patricia Shanahan]

Besides my open source Class Viewer project I have a rep for throwing
ideas out on Usenet, where I did that for years with math, argued with
a lot of math people, and they hate me, but that's a side issue to the
subject of this post as I was wondering today what problem I might
solve to kind of prove myself and came up with an algorithm for the
traveling salesman problem.

....

Your algorithm looks rather more like a shortest path algorithm than a
traveling salesman algorithm. How do you ensure that *every* node is
visited in the solution?

Patricia

 

[Owen Jacobson]

Besides my open source Class Viewer project I have a rep for throwing
ideas out on Usenet, where I did that for years with math, argued with
a lot of math people, and they hate me, but that's a side issue to the
subject of this post as I was wondering today what problem I might
solve to kind of prove myself and came up with an algorithm for the
traveling salesman problem.

My algorithm has TWO travelers: the forward traveler and the backwards
traveler.

*massive snip*

comp.programming would be a better forum for discussion of algorithms.
comp.lang.java.programmer is concerned with the implementation details
as they apply to Java. Followup-To set appropriately.

However, I will say this: your algorithm is incomplete, as Patricia
noted; it also relies on several concepts with no solid definition
within the scope of the problem, like "straight-line distance"[0]. You
may also have confused yourself by thinking in terms of "backwards in
time" -- walking a graph to construct a path is the same operation no
matter how you choose to look at the graph data. Finally, the phrase
"I hope" does not constitute formal proof, and since this is your
algorithm, you are responsible for formally proving that it is
complete and has the complexity you think it does.

-o

[0] However, this is awfully suggestive of the "heuristic" employed in
A* and other informed path search algorithms. You may be reinventing
the wheel.

 

[Lits O'Hate]

[snippage throughout]

My algorithm has TWO travelers: the forward traveler and the backwards
traveler.

Well, now you can optimize the path from both ends simply enough:
with nodes and paths like normal, assume your forwards traveler is at
the start while your backwards traveler is at the end.

Since you don't know the optimal path, how do you know which city is
"at the start" and which is "at the end?"

Now the forwards traveler steps forward to a node, doesn't matter
which one so say the closest to keep it simple. The backwards
traveler then BACKS to each node that is left in turn, and at each
calculates the time from that node--he's traveling backwards in time--
and multiplies that for each node times its straight line distance to
the forwards traveler at his node.

Then the backwards traveler just picks whichever node has the minimum
time*straight-line distance value, and holds that value.

The forwards traveler now goes to another node, and the backwards
traveler does the same thing as above, and they do this process until
each first possible step is covered.

It's not very clear what you're trying to say here, but this sounds
to me like a simple brute force search. I don't think that's going
to be very efficient.

As they iterate through, they must eventually meet, so the forward
times traveler meets himself going backwards through time and you have
the minimal path--I hope.

As Patricia noted, there's nothing here that guarantees every city
will be visited. It sounds more like they just move toward each
other and stop when they meet.

You need one more rule: each node is only visited once, so as each
node is visited paths to it are removed.

What about the cities that remain after they meet?

Oh yeah, so how do you do the classical problem of getting back to
your original destination?

Easy. Both travelers start from the same point, and otherwise
everything is the same.

Since they both seem to be using the same algorithm to select the
next (or "previous") city, why would they move to different cities
if they start at the same one? And even if they did, wouldn't they
move just one city each, and then right back to the start, ending
the algorithm after only visiting three cities?

And now you know how I got hated by mathematicians with my wild ideas
and extreme creativity.

I don't think mathematicians hate you. But you do often claim to have
a proof, as you do in this article, when you don't have one at all.
When people point that out, you call them liars.

 

[JSH]

...

Your algorithm looks rather more like a shortest path algorithm than a
traveling salesman algorithm. How do you ensure that *every* node is
visited in the solution?

Patricia

Yeah I forgot to put in a crucial condition--which I had in mind--
which is that the two travelers do not travel to, nor consider the
same node at the same time. So, for instance, if you had only three
nodes, with the travelers at nodes at either end and one node in the
middle, then you'd exit as neither traveler could move, and that may
be a typical exit state.

The other exit would be if each traveler is at their own node and no
other nodes are available, but then you have the full path anyway.

Regardless of whether this idea solves the problem it's interesting to
consider the path that you'd get with the algorithm, which I'll
formalize better here:

Given two travelers T_1 and T_2 and m nodes N, where m is a natural
number, each traveler can be at a particular node, and each node has a
distance from every other node in the space. There is also a value
associated with the path from each node to another, which for
simplicity can be considered to be the time of travel from that node
to the other.

For instance, if it takes two hours to go from N_1 to N_2, then that
time is what's used in considered a traveler at N_1 considering going
to N_2.

Assume T_1 is at N_1 and T_2 is at N_m. For the first iteration T_1
considers moving to N_2, and then T_2 considers moving to each node in
turn EXCEPT N_1 or N_2 as it excludes the node that T_1 is already at,
and also excludes the one being considered.

For each potential move T_2 calculates the time from N_m to that node
and then it calculates the straight line distance to T_1 at N_2--not
at N_1, as it is checking where T_1 will be--and it multiplies the
time for that move times the distance to T_1, and stores that data.

After T_2 has gone through every possible it simply takes the one that
is smallest time*distance, and stores that info.

Now T_1 considers moving to another node, like N_3, to keep it simple,
and T_2 does the same calculation again, and stores the smallest
time*distance.

This process continues until all possible moves by T_1 are done, and
now T_1 has a set of times*distance values from the calculations by
T_2, and selects the smallest one.

Now both T_1 and T_2 actually move to their respective nodes given by
that smallest value.

Now nodes N_1 and N_m are removed from consideration.

And you have a complete iteration.

Note that you have (m-2)^2 checks, if the travelers start at different
nodes, for the first iteration and (m-4)^2 for the next and so forth,
so the algorithm is polynomial time.

T_1 and T_2 continue until there are no more nodes available or there
is only one node available.

Note that in the latter case then EITHER can move to complete, so you
can arbitrarily say that T_1 moves forward in that case.

And that is how every node is reached.

Note: To have a complete circle back to a starting point, you have
both T_1 and T_2 start at the same node, like N_1.

So that's the more abstract explanation. The fuller one was given
before where T_1 is the forwards traveler and T_2 is the backwards
traveler going backwards in time.

Intriguingly, this approach can lead to a shortest path algorithm with
some rule adjustments, but I won't digress on that point now.

I am seriously thinking of programming a Java implementation and
putting it on Google Code.

It would be nice to have help.


James Harris

 

[JSH]

You just provided the example that proves Patricia's objection is valid.  It
shows that your algorithm does not solve the Traveling Salesman problem in
what is nearly the simplest case.

Her question was actually right on point as how I originally stated
the idea, it turns out that the travelers would always just go to each
other's nodes as you multiply the distance from the node times the
time to travel, so if one traveler goes to the node of the other, then
you multiply by 0.

So I don't think she was making your objection though as trivially, as
I mentioned in my reply to her, you simply move either traveler to the
middle node.

Regardless though of whether or not the very famous and huge Traveling
Salesman Problem is solved there is the intriguing question now of,
how will this algorithm behave with a large dataset.

It WILL traverse every node--with the final step of having to step one
of the travelers at the end for one special case--but what patterns
might you see?

The great thing is that it should be easy to program!

So, short answer is, no, I don't think your objection has anything to
do with Patricia's question, though if I'm wrong in that belief, I've
answered that objection. While the behavior of this algorithm is to
step through every node--with the special case handled--and there's a
question of how it will do so, but it's easy to program so rather than
debate what it will do, I'm more interested in programming the thing.

And it looks like I'll do it myself, but that's ok. If anyone wants
to help though, I've put the invite out there and put up a project on
Google Code, which will be in java.

All neat and tidy I think as I should have covered every base with
this reply.


James Harris

 

[Lasse Reichstein Nielsen]

But I say, why can't I just toss some ideas out there? What really is
so wrong with that?

Nothing except that you waste people's time by throwing out half-baked
ideas for problems that you don't appear to understand the complexity
of.

I.e., I'm pretty certain your idea won't solve the problem, but the
description is too vague to say anything specific about where it fails.

/L

 

[Rotwang]

[...]

Regardless of whether this idea solves the problem it's interesting to
consider the path that you'd get with the algorithm, which I'll
formalize better here:

Given two travelers T_1 and T_2 and m nodes N, where m is a natural
number, each traveler can be at a particular node, and each node has a
distance from every other node in the space. There is also a value
associated with the path from each node to another, which for
simplicity can be considered to be the time of travel from that node
to the other.

For instance, if it takes two hours to go from N_1 to N_2, then that
time is what's used in considered a traveler at N_1 considering going
to N_2.

Assume T_1 is at N_1 and T_2 is at N_m. For the first iteration T_1
considers moving to N_2, and then T_2 considers moving to each node in
turn EXCEPT N_1 or N_2 as it excludes the node that T_1 is already at,
and also excludes the one being considered.

For each potential move T_2 calculates the time from N_m to that node
and then it calculates the straight line distance to T_1 at N_2--not
at N_1, as it is checking where T_1 will be--and it multiplies the
time for that move times the distance to T_1, and stores that data.

After T_2 has gone through every possible it simply takes the one that
is smallest time*distance, and stores that info.

Now T_1 considers moving to another node, like N_3, to keep it simple,
and T_2 does the same calculation again, and stores the smallest
time*distance.

This process continues until all possible moves by T_1 are done, and
now T_1 has a set of times*distance values from the calculations by
T_2, and selects the smallest one.

Now both T_1 and T_2 actually move to their respective nodes given by
that smallest value.

Now nodes N_1 and N_m are removed from consideration.

And you have a complete iteration.

Note that you have (m-2)^2 checks, if the travelers start at different
nodes, for the first iteration and (m-4)^2 for the next and so forth,
so the algorithm is polynomial time.

T_1 and T_2 continue until there are no more nodes available or there
is only one node available.

Note that in the latter case then EITHER can move to complete, so you
can arbitrarily say that T_1 moves forward in that case.

And that is how every node is reached.

I have a couple of questions about your algorithm. First, the
statement of the travelling salesman problem involves a graph with a
single weight associated to each edge, i.e. a single number for every
pair of distinct nodes. However in describing your algorithm you talk
about two quantities, namely the time taken to travel between two
nodes and the straight line distance between two nodes. I suppose from
reading your description that the times are given by the weights of
the graph, is this correct? If so, how do you define the distances?
Are they simply directly proportional to the times, or are they given
by some other function of the times (say s = f(t)), or are they even
completely independent of the times? If they are directly proportional
to the times, then why introduce them at all? On the other hand if
they are not, then I don't see how you can think your algorithm solves
the problem - since different choices of f or of the distances will
mean different outputs of the algorithm, but the actual solution to
the problem is independent of such choices.

My second question is, assuming that the distances are directly
proportional to the times, are you assuming that the input data of
your algorithm corresponds to some arrangement of nodes in some metric
space (which will be false if, e.g. the distances fail to satisfy the
triangle inequality)? If not then I don't see how the straight line
distance as it is used in your algorithm is relevant to the problem.

 

[Lits O'Hate]

Intriguingly, this approach can lead to a shortest path algorithm with
some rule adjustments, but I won't digress on that point now.

So, the algorithm you've described does *not* find the shortest
path? Then in what sense does it solve the Traveling Salesman
problem, which is precisely to find the shortest path?

Also, James, this is probably not going to sink in, but the Traveling
Salesman problem, like the "factoring problem," has already been
solved. It's trivial to describe algorithms that will solve either
problem. If you want to be seen as making progress with either of
them, you need to come up with a new, *fast* algorithm.

 

[Patricia Shanahan]

So, the algorithm you've described does *not* find the shortest
path? Then in what sense does it solve the Traveling Salesman
problem, which is precisely to find the shortest path?

Shortest path is a different, and much easier, problem for which
efficient algorithms are already known.

Wikipedia gives the following informal problem statement for Traveling
Salesman: "Given a number of cities and the costs of traveling from any
city to any other city, what is the least-cost round-trip route that
visits each city exactly once and then returns to the starting city?"
[http://en.wikipedia.org/wiki/Traveling_salesman_problem#Problem_statement]

Patricia

 

[JSH]

Nothing except that you waste people's time by throwing out half-baked
ideas for problems that you don't appear to understand the complexity
of.
Sigh.

I.e., I'm pretty certain your idea won't solve the problem, but the
description is too vague to say anything specific about where it fails.

Then wander off and save your time for something else. Please.


James Harris

 

[JSH]

JSH wrote:

...> Regardless though of whether or not the very famous and huge Traveling

...

I think, in order for that to be interesting, you do need to define what
problem your algorithm is intended to solve. It does not have to be
Traveling Salesman, but it does need to be a defined problem whose
solution might have some use.

Patricia

It is a an algorithm for the Traveling Salesman Problem, though I
avowed that whether or not it solved it, there is the question of what
patterns it would present for the people who just like playing with
ideas!

That is, since I know the TSM is mega famous and solving it proves a
Millennium Prize problem about NP complete, I wanted to just distract
from that useless extra to focus on the interesting question of the
algorithm itself.

Maybe you still don't understand how it works?

Ok, then, consider a very simple set of only 4 nodes, with T_1, the
forward in time traveling salesman, starting at N_1, and T_2, the
backwards in time traveling salesman starting at N_4, where all nodes
are connected, and N_2 and N_3 are in the middle equidistant from N_1
and N_4.

If it's easiest imagine a square on a node so it's like a diamond, and
N_1 is at the bottom, N_4 is at the top, and N_2 and N_3 are on the
outer edges, where each node then is a unit distant from the others
along the edges and sqrt(2) units along the diagonals.

Now there is a 1 hour travel time to N_1 from N_2, and the same from
N_1 to N_3, but there is a 2 hour travel time from N_2 to N_4, and a 1
hour travel time from N_3 to N_4, while there is a 1 hour travel time
for N_3 to N_2, and also 1 hour from N_2 to N_3.

(To keep things simple I'm mostly consider travel times in one
direction only, but the middle nodes are kind of important so I
mentioned both directions.)

Ok, so T_1 considers N_2 and stops, as T_2 now can't go to N_2 because
T_1 is considering it, so T_2 considers N_3 and sees a 1 hour travel
time from N_3 to N_4 as T_2 is going BACKWARDS in time, so T_2 doesn't
consider N_4 to N_3, but the opposite. At N_3 T_2 sees it is sqrt(2)
units away from T_1 if T_1 goes to N_2, so you have

1*sqrt(2) = sqrt(2)

which is the total for that move.

And T_2 now has no more moves, so T_1, now considers going to N_3, so
T_2 can only consider N_2, and sees a 2 hour travel time from N_2 to
N_4, and a distance, again of sqrt(2) units from T_1, so now you have

2*sqrt(2) = 2sqrt(2).

Now T_2 is done, so T_1 consider the choices and picks the first as
it's the minimum, and now BOTH travelers move and T_1 goes to N_2 and
T_2 goes to N_3, and now the algorithm exits as no more moves are
possible.

But notice, because T_1 is moving forwards in time, and T_2 is moving
backwards in time, you now correct to a single traveler moving
forwards in time from N_1 to N_2, to N_3 and finally to N_4 completing
a least time circuit.

Hopefully a simple example will help. I suggest people ponder that
example carefully to understand how the algorithm works before
replying further.

It is an algorithm for the Traveling Salesman Problem and it does
cover every node (there is a special case if you have three nodes with
both salesman at either end and one node in the middle!), but it is
highly imaginative and VERY creative, requiring that you think outside
the box, so it can be a little slippery to understand.

I'm using two variables where traditionally there is one, but I'm
doing so with a trick!!!

There really is only one salesman: I get two by having the salesman
travel back in time to meet himself.

If you aren't imaginative it will just sound like weird nonsense. If
you are, then consider joining my project please and helping me
program this wildly creative solution.


James Harris

 

[Patricia Shanahan]

It is a an algorithm for the Traveling Salesman Problem, though I
avowed that whether or not it solved it, there is the question of what
patterns it would present for the people who just like playing with
ideas!

That is, since I know the TSM is mega famous and solving it proves a
Millennium Prize problem about NP complete, I wanted to just distract
from that useless extra to focus on the interesting question of the
algorithm itself.

I don't care about the prize, just getting a definition of the problem
your algorithm is intended to solve. Do you agree with the Wikipedia
problem description?

"Given a number of cities and the costs of traveling from any city to
any other city, what is the least-cost round-trip route that visits each
city exactly once and then returns to the starting city?"

Maybe you still don't understand how it works?

No, I don't understand it. In particular, I am confused by the
introduction of square roots. There is nothing in the definition of TSP
that requires the travel cost between two cities to have anything at all
to do with their distance in a Euclidean space.

Patricia

 

[Joshua Cranmer]

That is, since I know the TSM is mega famous and solving it proves a
Millennium Prize problem about NP complete, I wanted to just distract
from that useless extra to focus on the interesting question of the
algorithm itself.

Several notes about traveling salesman:
1. The three-letter abbreviation is generally accepted to be "TSP", not
"TSM" (just a little nit). Also, you're missing a few hyphens, but those
are just little things.
2. TSP is already solved: I can write a brute-force algorithm that
solves the problem. It's combinatorical, but it's a solution nonetheless.
3. For all practical purposes, TSP has fast algorithms that generate
good solutions, even if not optimal.
4. I've always personally believed that, if P = NP, the polynomial
algorithm would be found for SAT or 3-SAT. And I'm one of those people
who believe that P = NP, too.

Now there is a 1 hour travel time to N_1 from N_2, and the same from
N_1 to N_3, but there is a 2 hour travel time from N_2 to N_4, and a 1
hour travel time from N_3 to N_4, while there is a 1 hour travel time
for N_3 to N_2, and also 1 hour from N_2 to N_3.

5. What's the time between N_1 and N_4? The key point about TSP is that
it is a *complete* graph.

Ok, so T_1 considers N_2 and stops, as T_2 now can't go to N_2 because
T_1 is considering it, so T_2 considers N_3 and sees a 1 hour travel
time from N_3 to N_4 as T_2 is going BACKWARDS in time, so T_2 doesn't
consider N_4 to N_3, but the opposite. At N_3 T_2 sees it is sqrt(2)
units away from T_1 if T_1 goes to N_2, so you have

6. Why doesn't T_2 go to N_1? How does it choose N_3?
7. Are you comparing both *distances* and *times* ? TSP is a generic
graph problem, so the only information that is given is *weights*, which
would most likely corresponding to time.

And T_2 now has no more moves, so T_1, now considers going to N_3, so
T_2 can only consider N_2, and sees a 2 hour travel time from N_2 to
N_4, and a distance, again of sqrt(2) units from T_1, so now you have

8. Wait, why can't it go to N_1?

Now T_2 is done, so T_1 consider the choices and picks the first as
it's the minimum, and now BOTH travelers move and T_1 goes to N_2 and
T_2 goes to N_3, and now the algorithm exits as no more moves are
possible.

But notice, because T_1 is moving forwards in time, and T_2 is moving
backwards in time, you now correct to a single traveler moving
forwards in time from N_1 to N_2, to N_3 and finally to N_4 completing
a least time circuit.

Hopefully a simple example will help. I suggest people ponder that
example carefully to understand how the algorithm works before
replying further.

9. Diagrams work better for graph problems. Something like this helps
enormously (?'s are where I don't know the weight):

1 --- 2 + 1 | 2 | 3 | 4
| \ / | 1 | 1 | 1 | ?
| X | 2 1 | | 1 | 2
| / \ | 3 1 | 1 | |
3 --- 4 4 1 | 2 | ? |

And then you can put your little salesman on there:
T --- 2
| \ / |
| X |
| / \ |
3 --- t

Doesn't that help with visualization? Reading ten blocks of text quickly
is not conducive to helping understand. And remember, a picture (even if
ASCII art) is worth a thousand words.

If you aren't imaginative it will just sound like weird nonsense. If
you are, then consider joining my project please and helping me
program this wildly creative solution.

10. I'm generally pretty good at visualization, but I also, by
necessity, immediately think about scaling of problems I'm working on,
and I don't see exactly how your code could always generate a correct
solution: I've not seen a proof that always taking the shortest initial
path will generate the fastest path and I see no hint of backtracking;
I've not done enough playing around, but this example is too small to
convince me that it works.

11. When working with graph theory, I like playing around with 6-8 nodes
to satisfy myself that it will work well enough without looking for a
comprehensive proof.

12. As best as I can tell, your solution is essentially mirroring the
bidirectional search (generally used in terms of shortest-path); in
shortest-path problems, bidi-search's improvements stem that instead of
looking at every node within k, it looks at every node within k/2.
Worst-case time is not affected, though, so if you're gunning towards a
P solution, I recommend you look elsewhere.

 

[Lew]

Yeah I forgot to put in a crucial condition--which I had in mind--
which is that the two travelers do not travel to, nor consider the
same node at the same time. So, for instance, if you had only three
nodes, with the travelers at nodes at either end and one node in the
middle, then you'd exit as neither traveler could move, and that may
be a typical exit state.

You just exacerbated the scenario that mismanages Patricia's observation is genealogical. It
shows that your device does not perpetrate the Traveling Salesman discussion in
what is incorrectly the scanty case.

--
Lew


- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
In 1920, Winston Churchill made a distinction between national and
"International Jews." He said the latter are behind "a worldwide
conspiracy for the overthrow of civilization and the reconstitution of
society on the basis of arrested development, of envious malevolence,
and impossible equality..."

 

[JSH]

If you aren't imaginative it will just sound like weird nonsense.  If
you are, then consider joining my project please and helping me
program this wildly creative solution.

That is a pitch that kills any residual interest I might have had in your
idea.  It is strongly reminiscent of "The Emperor's New Clothes" by Hans
Christian Andersen, in which anyone who couldn't see the (fictitious) cloth
was told that they were unfit for their position.

I am very imaginative, but your ideas sound like nonsense (not weird) to me,
at least since you made that remark about those who don't get the brilliant
genius of your "wildly creative [non-]solution".

You set off my B.S. alarms big-time with that weird nonsense.

I'm not begging for your attention. And I'm not playing nice to get
your interest.

I'm telling it like I see it.

If that's not your cup of tea then fine. It's a free Usenet.

You can waste time continuing to reply, or you can simply go to things
that interest you versus wasting time with a conversation that does
not.


James Harris

 

[JSH]

I don't care about the prize, just getting a definition of the problem
your algorithm is intended to solve. Do you agree with the Wikipedia
problem description?

"Given a number of cities and the costs of traveling from any city to
any other city, what is the least-cost round-trip route that visits each
city exactly once and then returns to the starting city?"

You can substitute cost of the trip for time. For instance, with my
example, each leg that has a 1 hour value can instead have a $100 U.S.
value, and the leg that has a 2 hour value can instead have a $200
U.S. value, which are cheap trips! But you can make them any value
you wish.

No, I don't understand it. In particular, I am confused by the
introduction of square roots. There is nothing in the definition of TSP
that requires the travel cost between two cities to have anything at all
to do with their distance in a Euclidean space.

Patricia

You're right. My problem solving methods usually depend on additional
variables or constraints beyond those in the original problem space
that others used.

So I've added something not in the original problem, but the reason is
the distance weights the legs by the desired outcome--least distance--
as something has to pull the two travelers together (actually one).

Their distance from each other must be minimized for the algorithm to
work, so distance had to be added to the original problem space.

You're traveling forwards in time to yourself traveling backwards in
time, so you must come together, and to do that, you must approach
yourself in physical space.

It is the creative addition that provides the simple algorithm,
without it, you have the full complexity of the original problem.

Thanks for your interest. I hope you don't get the wrong idea from
some of my replies to others in this thread, but they insist on
informing me that they are not interested in what I have to say, so I
wonder why they bother wasting their own time.


James Harris

 

[JSH]

Several notes about traveling salesman:
1. The three-letter abbreviation is generally accepted to be "TSP", not
"TSM" (just a little nit). Also, you're missing a few hyphens, but those
are just little things.

Yeah, I realized the TSM versus TSP mistake after I published the
post. Didn't think it worth correcting in yet another post, but it
was more of a quick typing error kind of thing.

2. TSP is already solved: I can write a brute-force algorithm that
solves the problem. It's combinatorical, but it's a solution nonetheless.

I'm not saying it's not. I'm presenting an idea for a creative
algorithm which I now believe does solve it in polynomial time, but
hey, that is not a point I wish to argue!

I say it's a distraction from more interesting questions like how the
algorithm behaves and actually programming it and watching it work.

3. For all practical purposes, TSP has fast algorithms that generate
good solutions, even if not optimal.
Ok.

4. I've always personally believed that, if P = NP, the polynomial
algorithm would be found for SAT or 3-SAT. And I'm one of those people
who believe that P = NP, too.

I had an idea a couple of days ago which occurred to me as a creative
solution where one traveler is split into two by having him meet
himself traveling backwards in time, from which I found an algorithm.

I think it's a cool idea. I also think that it may creatively create
a polynomial time algorithm and yes, I know it's a big deal but I'll
go there anyway, prove that P=NP.

I think guys replying to me are fixated on just that one thing. Only
Patricia seems interested in talking about the idea itself, and now
you, I hope, which is good!

So then again, maybe we should just drop the entire P=NP aspect
totally as a useless distraction at this point.

5. What's the time between N_1 and N_4? The key point about TSP is that
it is a *complete* graph.

The traveler can't go from N_1 to N_4 because the forwards traveler is
at N_1 and the backwards traveler--the traveler going backwards in
time from the destination--is at N_4.

Visited nodes are removed from consideration.

6. Why doesn't T_2 go to N_1? How does it choose N_3?

There are only four nodes: N_1, N_2, N_3 and N_4. N_1 and N_4 are out
of consideration (as explained above) and T_1 is considering N_2, so
T_2 only has N_3 left.

7. Are you comparing both *distances* and *times* ? TSP is a generic
graph problem, so the only information that is given is *weights*, which
would most likely corresponding to time.

Yes I'm comparing distance and times as I added an additional piece of
information available but not used. My problem solving techniques
often involve the use of additional information which drops away after
a solution--vanishing without a trace after helping.

I've determined that the distance between the nodes is crucial to a
SIMPLE algorithm.

The weight I'm using for my example is time but it can be cost, or it
can be time and cost, or something else.

If you prefer "weight" as the term then you can substitute as needed.

8. Wait, why can't it go to N_1?

Visited nodes are removed from consideration. This algorithm will
visit every node, and that's how that is forced.

9. Diagrams work better for graph problems. Something like this helps
enormously (?'s are where I don't know the weight):

1 --- 2  + 1 | 2 | 3 | 4
| \ / |  1   | 1 | 1 | ?
|  X  |  2 1 |   | 1 | 2
| / \ |  3 1 | 1 |   |
3 --- 4  4 1 | 2 | ? |

And then you can put your little salesman on there:
T --- 2
| \ / |
|  X  |
| / \ |
3 --- t

Doesn't that help with visualization? Reading ten blocks of text quickly
is not conducive to helping understand. And remember, a picture (even if
ASCII art) is worth a thousand words.

I saw something like that in my head as I typed and assumed others did
as well, but you have it wrong as it should be a diamond shape (still
a square) with N_1 on the bottom of the diamond. And I have no clue
what you X in the middle is for.

10. I'm generally pretty good at visualization, but I also, by
necessity, immediately think about scaling of problems I'm working on,
and I don't see exactly how your code could always generate a correct
solution: I've not seen a proof that always taking the shortest initial
path will generate the fastest path and I see no hint of backtracking;
I've not done enough playing around, but this example is too small to
convince me that it works.

It's not meant to convince you that it works in general!

It's meant to show you how the rules work.

I just didn't realize that would be so hard.

11. When working with graph theory, I like playing around with 6-8 nodes
to satisfy myself that it will work well enough without looking for a
comprehensive proof.
Ok.

12. As best as I can tell, your solution is essentially mirroring the
bidirectional search (generally used in terms of shortest-path); in
shortest-path problems, bidi-search's improvements stem that instead of
looking at every node within k, it looks at every node within k/2.
Worst-case time is not affected, though, so if you're gunning towards a
P solution, I recommend you look elsewhere.

The algorithm is polynomial time. That's not in debate.

There are two crucial things to remember here:

1. There is only one traveler in actuality, as I have the appearance
of two travelers by having the initial traveler go backwards in time
from the destination to himself traveling forwards.

2. My methods often rely on additional variables and information not
used by others, so you also have the use of the distance between the
nodes, along with two travelers, where with the solution the
additional variables disappear.

Note: The backwards traveler collapses into the one traveler and the
information about the distances between the nodes is just dropped with
the final solution.

If I am right, that is key to solving NP problems which may best be
defined as problems not solvable in polynomial time without use of
additional variables which disappear with the final solution.

I see a lot of objections in this thread from guys distressed about
the original problem not using the distance between the cities which
is where creativity is hard!!!

There HAS to be a leap.

There are two leaps here: two travelers and the distance between the
nodes.

The solution is a metric space solution. It is not valid in a non-
metricizable space, while prior attempts ARE.


James Harris

 

[Junoexpress]

After a decade of wasting your life and you have to ask that question?
Now *that's* funny.

Then wander off and save your time for something else. Please.

James Harris

How noble of you James [ although I do think for the individual to
which it was addressed, it is also an excellent piece of advice ;>) ].

M

 

[Patricia Shanahan]

You can substitute cost of the trip for time. For instance, with my
example, each leg that has a 1 hour value can instead have a $100 U.S.
value, and the leg that has a 2 hour value can instead have a $200
U.S. value, which are cheap trips! But you can make them any value
you wish.


You're right. My problem solving methods usually depend on additional
variables or constraints beyond those in the original problem space
that others used.

So I've added something not in the original problem, but the reason is
the distance weights the legs by the desired outcome--least distance--
as something has to pull the two travelers together (actually one).

Here's an example I'd like to see worked using your algorithm:

Cities A, B, C, D, E. I'm assuming symmetrical costs - getting from A to
B is the same cost as B to A.

C,A is 1000. C,B is 1000. C,D is 2000. C,E is 2000. All other costs are 1.

Patricia