Talk:Travelling salesman problem

From Wikipedia, the free encyclopedia

This article is within the scope of the following WikiProjects:
This article has an assessment summary page.

Contents

[edit] Nearest Neighbor Algorithm

I believe the current text is incorrect: "Unfortunately, it is provably reliable only for special cases of the TSP, namely those where the triangle inequality is satisfied."

In fact, even for the TSP satisfying the triangle inequality, the approximation can be arbitrarily bad: "Theorem: For every r>1, there exists an instance of the TSP, obeying the triangle inequality, for which the solution obtained by the nearest-neighbor algorithm is at least r times the optimal value." Gross, Jonathan; Yellen, Jay. 1999. Graph Theory and Its Applications. New York: CRC Press. 228-232. So the text ought to be changed, no? Padde 22:51, 18 November 2006 (UTC)

[edit] Lukas Roots's solution

Don't have any insight but this article claims a 16 year old 'solved' the problem... [1] --67.187.48.82 04:18, 27 April 2006 (UTC)

By referring to the problem as an unsolved problem, and then claiming then he solved it, does he mean to say that he devised an efficient algorithm for an optimal solution or an approximate solution? I did a web search but could not find any reference to this or the algorithm itself online. Whatever he was trying to say, one should be wary of such claims without proper public disclosure. --Amit 00:48, 23 July 2006 (UTC)

[edit] Optimal solution for 15,112 cities

According to this link, [2], an optimal solution has been found for the 15,112 city problem, not just an approximate solution. --Petero2 16:33 Jan 31, 2003 (UTC)

-- The fact remains that this is an NP hard problem, and as such an exact method cannot solve the problem in polytime. This is just one instance of a TSP that has been solved. ---Smremde 11:58, 25 July 2006 (UTC)

[edit] Princeton proof?

The Princeton link refers to a "proof" of the TSP problem for a specific configuration of cities in Germany. The "proof" relies on a computer program, the associated network of computers, and the computer hardware. It is perfectly possible that there exists a verifiable proof that the computer program is correct but there is a finite, non-zero probability of undetected failure of any one of the hardware components.

Another comparable effort is the verification of Goldbach's conjecture for very large numbers. As Ian Paisley, a prominent Northern Irish politician might have said - "If you believe that you'll believe anything".

Colin M Davidson

How fast are the best known deterministic algorithms?


"Given a number of cities and the costs of travelling from one to the other, what is the cheapest roundtrip route that visits each city and then returns to the starting city?"

Shouldn't it be "... that visits each city once ..."?

Yes. Thanks. Mikkalai 20:37, 16 Nov 2004 (UTC)

a) only yes/no problems are NP etc. The TSP "finding the route" etc. is BPP (prob'y the reference easiest to access is Papadimitriou's 1998 textbook, in the part(s) where he presents the complexity classification for non-yes/no probs.)

you mean FNP not BPP right? it is usually believed dthat BPP = P Nr9 08:14, 8 April 2006 (UTC)

[edit] General Case

Shouldn't the ATSP be cast as the general case of the TSP, with the equal-cost-in-both-directions constraint relaxed over some subset of the edges?

I agree. Asymmetric TSP: "The special case where the distance from A to B is not equal to the distance from B to A" is not a special case but a generalized case. I'll remove the word "special". Bo Jacoby 10:20, 6 March 2006 (UTC)

[edit] TSP with triangle inequality

"the distance between A and C must be at most the distance from A to B plus the distance from B to C. "

This is easy to understand when we talk about points in some space like Euclidian or a sphere.

But when we talk about graphs, it's confusing because in any graph that contains the path {A,B,C}, the distance between A and C is never greater than the distance between A and B plus the one between B and C. This is true even for graphs that doesn't conform to triangle inequality!!!

I think something like this would be clearer to most readers: "the shortest distance between A and C not passing through B must be at most the distance from A to B plus the distance from B to C. "

what about the word direct? I.E. lenght of the road connecting the two cities. A direct route might not be the easiest/shortest.

But I'm not sure if it's matematically right!

It's not. First, it's not true that in any graph that contains the path {A, B, C}, the distance between A and C is never greater than the distance between A and B plus the one between B and C. For example, take the complete graph on 3 vertices with edge weights 3, 1, and 1. In this case, we have the distance between A and C being 3 and the distance from A to B plus the distance from B to C being 2. Note that the distance between two vertices in the graph is the weight of the edge between them, not the shortest distance in the graph. I hope that clears up your confusion. Cgray4 09:51, 4 April 2006 (UTC)

[edit] Question

it is easily seen that in the planar case an optimal tour visits cities only once (otherwise, by the triangle inequality, a shortcut that skips a repeated visit would decrease the tour length).

Okay, so . . . what if three cities are colinear? In particular, what if we consider a case with the home city and two other cities, and all three are colinear? Do we just figure that the intervening city is a point and can be circumvented with arbitrarily low expenditure of distance, so call it zero? —Simetrical (talk • contribs) 02:07, 20 June 2006 (UTC)

Going directly from A to C isn't considered stopping at B, even if A, B, and C are colinear. If they are colinar then there's no difference between stopping at B and going directly from A to C. This all comes from looking at the problem as an abstract graph rather than a surface with cities. CRGreathouse (t | c) 06:56, 21 September 2006 (UTC)

[edit] a proposed algorithm

How would this incremental algorithm work well (in terms of solution quality):

-start with tree looped cities

-for each new city:

--consider each existing edge

---get its current lenght

---get the total distance from the city being added to the edge's endpoints

---substract these two values

--connect the city through the shortest detour

?

It is quadratic in terms of running time but how good solutions does it produce? It always produces solutions with no crossings. Another possibility might be to run the algorithm a few times with randomized order of the cities. Honnza 10:23, 22 July 2006 (UTC)

This is the greedy algorithm. It performs reasonably well in the Euclidian case (not as well as the advanced approximation schemes), an in fact should be subquadratic in that case. In the general case where the triangle inequality is not valid, this method can be arbitrarily bad. CRGreathouse (t | c) 06:53, 21 September 2006 (UTC)

[edit] Political Correctness

Should this be Traveling Salesperson Problem? I seem to remember it being changed

--143.53.132.154 10:56, 25 July 2006 (UTC)

Nonsense (IMHO). In practically all scientific publications dealing with it, it's called Travel(l)ing SalesMAN Problem. It's simply how it's called. Period.

--85.127.5.34 13:35, 29 April 2007 (UTC)

It is usually called TSP, whether that means Travelling Salesman Problem or Travelling Sales Person (and the "problem" is added later as TSP problem) or Travelling Salesperson Problem. Either way, the use of "person" rather than "man" is becoming more widespread.

[edit] subexp time for euclidian TSP ?

Although the problem still remains NP-hard, it is known that there exists a subexponential time algorithm for it.

Where can I find that algorithm ?


  • As far as I know, a "subexponential" time algorithm means a polynomial time algorithm (e.g., 2^O(sqrt(log N)) is something like O(sqrt N)). Since Euclidean TSP is NP-hard and the corresponding decision problem is NP-complete, wouldn't finding a polynomial time algorithm for Euclidean TSP would prove P=NP? Therefore, I suspect the quoted statement is incorrect. --68.61.203.204 18:47, 26 November 2006 (UTC)

[edit] two questions on higher-dimensional TSPs

Currently, this article doesn't have much discussion on TSPs in more than two dimensions. Would different approaches be required in order to solve TSPs in higher dimensions?

Also, consider this three-point TSP with the following conditions:

  • d(a,b) = 5
  • d(a,c) = 7
  • d(b,c) = 150

As we can see, this (arbitrary) system isn't possible in normal Euclidean spaces unless higher dimensions are involved.

Again, do we need to use different approaches in solving TSPs of this type? --Ixfd64 21:36, 10 November 2006 (UTC)

  • the triangle inequality is true in any number of dimensions. It is true for any metric space.

[edit] "Human performance"

These works are so naive. If strip away the psychobabble,

  • the first hypothesis says that people can quickly solve the TSP because they can quickly find a partridge in a pear tree (bad link here. This is a reference to a centuries old puzzle, where you must find various figures among random drawings, e.g. a contour of a bird or a hare created by branches of a bush ).
  • the second one says that people solve the TSP because they are smart, since the smarter they are, the faster they solve it.

What a waste of taxpayers' and grant money. `'mikka 16:32, 2 January 2007 (UTC)

[edit] What about the ants?

Shouldn't there be a reference on this page to the experiments done with ants which have found that random searching combined with weak pheromone trails result in a much quicker solution to the problem than is possible through mathematics. I realise this doesn't solve the mathematical problem but I think there should at least be a link to an article about the ant approach. 81.156.221.243 16:35, 3 February 2007 (UTC)Sabita Banerji

[edit] Polytime solution in progress?

From "Computational Complexity" section:

"Though see this work-in-progress attempt at a proof of polynomial time calculation for the 2-D undirected graph."

It looks as though the page linked to just claims that TSP is in NP, then presents the details of an approximation algorithm. Should this perhaps not belong here? 140.247.40.63 09:16, 4 February 2007 (UTC)

[edit] Spelling

The first line coins the term "traveling salesman problem" and has a note saying that the American spelling is "traveling salesman problem." ...Am I missing something? I glanced at the history to see if it looked like any British-American edit wars occurred, but didn't notice anything in my 5 seconds of searching. I suspect this relates to the difference in spelling between the introductory paragraph and the article, where there are one or two "L"'s in "traveling / travelling"? I suggest we standardise the article in some manner. Personally, I'm a one-L person; but I could care less as long as it's consistent. --Thisisbossi 22:42, 7 February 2007 (UTC)

There are two ls in travelling. The verb is "to travel", not "to travele". Paul Silverman 19:41, 8 February 2007 (UTC)
One L as per Merriam-Webster. [3] --Thisisbossi 22:12, 8 February 2007 (UTC)
Miriam Webster is rubbish Oxford spells it properly. Paul Silverman 21:38, 9 February 2007 (UTC)
Thank you for the link, which answered my initial question; but instead of mocking lingual differences it may have been simpler for you to simply say that one spelling is British and another is American. My initial comment is maintained, however: the spelling should remain consistent throughout the article and including the article's name, and/or the link referring to the American spelling should be modified. I will leave it to the more regular editors of this article to decide how best to pursue this. --Thisisbossi 03:43, 12 February 2007 (UTC)
I saw that too and had to switch back and forth between the text and footnote for a while to see if I was missing something. I've clarified the footnote. -SpuriousQ (talk) 01:05, 15 February 2007 (UTC)

I believe that the footnote had disappeared, which IMO is a bad thing - the article is titled using double-L, but the first paragraph (and the subsequent text) describes the notion using single-L... Where can we add back the fact that the british and american spelling differs? I mean, besides letting the reader discover that the references section actually contains both spellings? :-D -- Jokes Free4Me 06:52, 17 June 2007 (UTC)

Looking at the external links, this what the georgia tech page had to say about it... http://www.tsp.gatech.edu/history/travelling.html Looks like the problem's title is a proper noun. Should be one L regardless of the spelling of traveling/travelling. Keep with the problem's original spelling. Psy wombats 14:46, 23 October 2007 (UTC)

[edit] Political Correctness

I agree and accordingly corrected the notes. —The preceding unsigned comment was added by 89.243.66.153 (talk) 16:20, 4 March 2007 (UTC).

[edit] Nearest Neighbour Algorithm cannot find worst possible solution.

I changed the text that said the nearest neighbour algorithm can find the worst possible solution and removed the asociated request for citation.

The worst possible scenario for the NN algorithm is all points strung upon a line, with the shortest distance being at alternating sides from the central point. eg.

E.......C.AB...D........

The nearest neighbour solution A->B->-C->D->E takes 1+3+7+15=26.

An alternate solution A->E->B->C->D is 10+11+3+7 = 31.

There is a worse solution than the worst possible NN solution. Therefore NN cannot result in the worst possible solution.

All that said, maths is not my strongest point, so please point out if there's a flaw in my position. Thanks.

--irrevenant [ talk ] 03:15, 17 March 2007 (UTC)


[edit] Probability question

Is it possible to estimate the probability p(n) of finding a tour without loops at random permutation of n towns uniformly distributed over a square?--Kjells 18:40, 25 April 2007 (UTC)

Consider simulating to get an idea. It seems it should probably be exponentially small.Ninjagecko 12:38, 8 May 2007 (UTC)

[edit] Plagiarism?

Compare:

Mathematical problems related to the traveling salesman problem were treated in the 1800s by the Irish mathematician Sir William Rowan Hamilton and by the British mathematician Thomas Penyngton Kirkman. A discussion of the early work of Hamilton and Kirkman can be found in Graph Theory 1736-1936. The general form of the TSP appears to have been first studied by mathematicians during the 1930s in Vienna and at Harvard, notably by Karl Menger. The problem was later undertaken by Hassler Whitney and Merrill Flood at Princeton. A detailed treatment of the connection between Menger and Whitney as well as the growth in the study of TSP can be found in Alexander Schrijver's 2005 paper "On the history of combinatorial optimization (till 1960)"

with http://www.tsp.gatech.edu/history/index.html

Mathematical problems related to the traveling salesman problem were treated in the 1800s by the Irish mathematician Sir William Rowan Hamilton and by the British mathematician Thomas Penyngton Kirkman. The picture below is a photograph of Hamilton's Icosian Game that requires players to complete tours through the 20 points using only the specified connections. A nice discussion of the early work of Hamilton and Kirkman can be found in the book Graph Theory 1736-1936 by N. L. Biggs, E. K. LLoyd, and R. J. Wilson, Clarendon Press, Oxford, 1976.

The general form of the TSP appears to be have been first studied by mathematicians starting in the 1930s by Karl Menger in Vienna and Harvard. The problem was later promoted by Hassler Whitney and Merrill Flood at Princeton. A detailed treatment of the connection between Menger and Whitney, and the growth of the TSP as a topic of study can be found in Alexander Schrijver's paper ``On the history of combinatorial optimization (till 1960). —The preceding unsigned comment was added by 143.239.1.153 (talk) 19:33, 1 May 2007 (UTC).

Then alert the person at the URL, though it is entirely possibly the author of that page decided to jointly publish that information on Wikipedia. Ninjagecko 12:41, 8 May 2007 (UTC)

[edit] Problems with "Example letting the inversion operator find a good solution" section

Upon reading this twice, it seems to me that it doesn't state its algorithm: you can't simply apply the "inversion" operator over and over again to get to the right solution; there has to be some sort of "guiding" or accept/reject step... the author of that section should state the algorithm used to generate those graphs, or else the section is meaningless and probably should be excised. Ninjagecko 23:16, 8 May 2007 (UTC)

In every generation there is random variation (by inversion) and selection of the shortest tours. The guidance is that the limit of acceptance is slowly lowered. There is no original research in this case. I wrote my algorithm in MATLAB in accordance with the algorithm given by Goldberg.--Kjells 07:28, 10 August 2007 (UTC)

[edit] Reference to MATLAB

Firstly, why is there a reference to MATLAB? It is irrelevant. Secondly why does it say that MATLAB is "the language of technical computing"? This is nonsense. MATLAB isn't just a language and it is not THE language of technical computing. A lot of number crunching is done with FORTRAN or C for example. —The preceding unsigned comment was added by 62.56.77.207 (talk) 15:15, 11 May 2007 (UTC).

[edit] Reference to Marco Dorigo

The style of this reference, with a title bearing a particular person's name, is objectionable and out of line with the rest of the article (and the overall Wikipedia guidelines). Secondly, the contents of this section, if they should be included at all, belong to a previous section, namely on heuristics. Finally and, in my opinion, most importantly, the work is of little substantial value in practice for the TSP, because a computer implementation of the proposed algorithm is vastly inferior to state-of-the-art heuristics (such as the chained Lin Kernighan), both in terms of computational time and quality of solutions. Cngoulimis 11:00, 16 July 2007 (UTC)

I rewrote and moved this section. Dcoetzee 23:02, 7 August 2007 (UTC)

[edit] Contested move request

The following request to move a page has been added to Wikipedia:Requested moves as an uncontroversial move, but this has been contested by one or more people. Any discussion on the issue should continue here. If a full request is not lodged within five days of this request being contested, the request will be removed from WP:RM. —Stemonitis 06:27, 11 August 2007 (UTC)

  • WP:ENGVAR explicitly forbids this kind of switching between US and Commonwealth spellings. --Stemonitis 06:27, 11 August 2007 (UTC)
  • Yes, this should clearly stay where it is, unless a compelling reason to do otherwise is raised. Dcoetzee 13:26, 11 August 2007 (UTC)
  • The article uses a different spelling than its title. I was simply trying to be consistent. If consensus says that we spell it "travelling" then all instances of the word should be spelled that way in the article. —Disavian (talk/contribs) 17:34, 11 August 2007 (UTC)
  • ...Which looks like it was done after I submitted my request. Excellent. —Disavian (talk/contribs) 17:35, 11 August 2007 (UTC)

[edit] Optimization version NP-complete?

Sorry if the answer to this is obvious, but is the optimization version of this problem ("Find a path with minimum cost.") in NP-complete, or just the recognition version? EDIT: come to think of it, that would put the recognition version in NP, right? 77.49.167.219 13:09, 9 November 2007 (UTC)

NP-complete is a decision problem class, and can only contain decision problems (problems with yes/no answers). Optimization problems can be NP-hard, but not NP-complete. Dcoetzee 00:30, 10 November 2007 (UTC)

[edit] TSP in popular culture

It's a pity that there is no article The travelling salesman problem in popular culture. It's probably too offtopic for this one: [4]. --Hans Adler (talk) 20:05, 27 March 2008 (UTC)