# Travelling salesman problem algorithm

Show 80 post(s) from this thread on one page
Page 2 of 2 First 12
• 03-23-2010
assertion
Unfortunately, Wikipedia disagrees with mathematics and computer science mote often than not. You wouldn't believe how often I find myself in situations like that:
"The given graph has this-and-that property"
"Sure?"
"Um, yes..."
<simple proof by counter-example that the graph doesn't have the property proposed>
"But it has to have this-and-that property!"
"What part of the proof is unclear to you?"
"...It says so on Wikipedia!"

Unfortunately, the number of people I have to deal with who think that "It says so on Wikipedia" makes whatever they say the truth increases, while it becomes more and more difficult to convince them otherwise. Wikipedia is *not* an alternative to a book on graph theory, and is *especially* not an alternative to think for yourself. It is common to define attributes like length for a path. What is a longest path, if you allow it to be a walk? What is the shortest path, if the graph is not conservative? While you can define that "path" means "The Knights Who Say Ni!", this isn't exactly the thing you should do in order to make clear what you mean.
[/rant on wikipedia, and my apology to the thread owner for hijacking it. I'll shut up now.]
• 03-23-2010
laserlight
Quote:

Originally Posted by assertion
Unfortunately, the number of people I have to deal with who think that "It says so on Wikipedia" makes whatever they say the truth increases, while it becomes more and more difficult to convince them otherwise.

Apply a correction to the Wikipedia page that they are quoting. Duh. :D
• 03-24-2010
EVOEx
Hmm well, mathworld agrees with you. Several other sources don't. I think my textbook for university didn't, but I'm not sure...
• 03-24-2010
laserlight
Quote:

Originally Posted by EVOEx
Hmm well, mathworld agrees with you. Several other sources don't. I think my textbook for university didn't, but I'm not sure...

I tend to ask DADS when I need to clarify such definitions. In this case, a note in its definition of path supplies the clarification:

path: A list of vertices of a graph where each vertex has an edge from it to the next vertex. (Note: A path is usually assumed to be a simple path, unless otherwise defined.)

simple path: A path that repeats no vertex.

Furthermore, its definition of TSP eliminates any such confusion:

traveling salesman: Find a path through a weighted graph which starts and ends at the same vertex, includes every other vertex exactly once, and minimizes the total cost of edges.
• 03-24-2010
EVOEx
Quote:

Originally Posted by laserlight
path: A list of vertices of a graph where each vertex has an edge from it to the next vertex. (Note: A path is usually assumed to be a simple path, unless otherwise defined.)

simple path: A path that repeats no vertex.

Furthermore, its definition of TSP eliminates any such confusion:

traveling salesman: Find a path through a weighted graph which starts and ends at the same vertex, includes every other vertex exactly once, and minimizes the total cost of edges.

Oh, way to go, humanity. Let's just name something where nobody knows what we mean because the words have several proper definitions.
Usually a path is assumed to be a simple path. Not always. Not even if nothing is defined, otherwise the sentence would exclude the word usually.

Come on, can't everyone just agree on one definition? Like an ISO for Math definitions.
Time to buy IMSO.com (International Mathematical Standards Organisation)!
Show 80 post(s) from this thread on one page
Page 2 of 2 First 12