Thread: Travelling salesman problem algorithm

  1. #16
    Registered User
    Join Date
    Mar 2010
    Posts
    18
    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.]

  2. #17
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    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.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #18
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    Hmm well, mathworld agrees with you. Several other sources don't. I think my textbook for university didn't, but I'm not sure...

  4. #19
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    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.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #20
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    Quote Originally Posted by laserlight View Post
    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)!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. what is the algorithm in this problem..
    By cfan in forum C Programming
    Replies: 2
    Last Post: 08-04-2009, 11:52 AM
  2. data mamgment problem (algorithm)
    By cfan in forum C Programming
    Replies: 0
    Last Post: 08-02-2009, 12:07 PM
  3. Help with grid problem (dynamic programming)
    By scp89 in forum C Programming
    Replies: 15
    Last Post: 05-07-2009, 12:16 PM
  4. Simple algorithm problem
    By stodd04 in forum C Programming
    Replies: 11
    Last Post: 03-04-2005, 11:08 AM
  5. algorithm problem
    By cdonlan in forum C++ Programming
    Replies: 3
    Last Post: 02-10-2005, 09:16 PM

Tags for this Thread