Talk:Travelling salesman problem

From Wikipedia, the free encyclopedia

This article is part of a WikiProject to improve Wikipedia's articles related to Computer science. For guidelines see WikiProject Computer science and Wikipedia:Contributing FAQ.

[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 eaasiest 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

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

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

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

[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)