Talk:Travelling salesman problem

Including distance matrix for presented example (7 city)

Is it possible to include original distance matrix (as it seem all gif animations use either the same or very similar one) for following images? https://en.wikipedia.org/wiki/File:Bruteforce.gif https://en.wikipedia.org/wiki/File:Branchbound.gif https://en.wikipedia.org/wiki/File:Nearestneighbor.gif https://en.wikipedia.org/wiki/File:AntColony.gif

All seem to share author (Saurabh.harsh). If this was done on image descriptions, it wouldn't affect current article's structure and allow this information to be easily shared with other articles them, as it could be just table with numbers, so no real need for translation). — Preceding unsigned comment added by Repnihrefs (talk • contribs) 15:52, 26 March 2022 (UTC)

importance?

I think importance=Top may be an overstatement for all of CS. Thoughts on bumping this down to importance=high? Certainly a hugely important problem in theoretical computer science, especially historically, but not one that seems particularly notable to the rest of CS. Caleb Stanford (talk) 18:17, 30 June 2022 (UTC)

I think high is ok. It's important, but not at the level of the halting problem or the P vs NP problem. —David Eppstein (talk) 19:21, 30 June 2022 (UTC)

The presumption of a route being possible

I have been studying the TSP intermittently for a decade now, and it appears to me that there is an untold controversy occurring in relation to the TSP being solved. I would like a "Controversies" section of the wiki to be opened. I think that a severe fallacy is being made in relation alleged routes computed to display that there are "possible" routes or that one route of the "possible" routes is the shortest: I think this fallacy comes from a belief that the salesman's travel can be preplanned to the point that the salesman can then travel that preplanned route via free will. I would like someone to make a topic on this issue as to whether or not there is a presumption that the salesman of the TSP has free will if but one or more ways to deviate from his fate/destiny/world-line. It appears to me there is often that presumption because there are routes that are argued to be the shortest "possible" route as if the conditions for the salesman to travel that route will be held constant in order for it to be a possible route OR that the salesman has free will to take that alleged shortest route as a possibility. In "the real world," unexpected things might happen that prevent an actual salesman from traveling a route that has been calculated by a computer to be the shortest "possible" route. For instance, if an unavoidable roadblock were to occur, that route would not have been a "possible" route after all. Dennis Blewett (talk) 22:30, 18 May 2023 (UTC)

Proposed solution in example is suboptimal

In the section "Computing a solution", under the subsection "Exact algorithm", the solution proposed is suboptimal. This can be verified visually; You can just replace a long segment with a shorter one:

It is visually very clear that the new, light-blue line segment is shorter than the segment connecting the upper right point to the upper left one.

If we approximate the coordinates of the points according to the scale:

• originally proposed solution faulty segment has a distance squared of: (95-20)² + (80-65)² = 5850
• new solution blue segment squared distance (45 - 60)² + (15-50)² = 1450

MedAnisMessaoudi (talk) 16:55, 12 March 2024 (UTC)

It is the same round trip, with end = start. Uwappa (talk) 17:09, 12 March 2024 (UTC)

You are indeed correct, Thank you MedAnisMessaoudi (talk) 18:23, 12 March 2024 (UTC)

"Equivalent formulation" in terms of Hamiltonian cycle is not quite equivalent

When teaching this topic, we realized that the stated equivalent formulation "find a Hamiltonian cycle with the least weight" is not quite equivalent. The difference amounts to whether an edge can be reused, but in the context of TSP this is very slight, affecting only the case of a two-vertex, one-edge graph K_2.

Specifically, the textual description of the problem "what is the shortest possible route that visits each city exactly once and returns to the origin city?" allows for edge(s) to be reused. Due to the "exactly once" condition, such reuse is possible only in K_2, but this is reasonable to allow: the salesperson goes from the home city to the other city, then returns along the same edge.

By contrast, a Hamiltonian cycle is a cycle, which is a trail, which cannot reuse any edge. So there is no solution in K_2. 141.212.109.160 (talk) 15:43, 25 March 2024 (UTC)

When I cover this topic in my classes, I provide two formulations: one in positively weighted undirected graphs where you're allowed to reuse edges and vertices, and must find a closed walk that visits each vertex at least once, and one in metric spaces where you must find a cyclic order of the points. They are easily equivalent, of course, via all-pairs shortest paths. In any case, this avoids your problem with K₂: in the graph formulation, the single edge can be reused, and in the metric formulation, there is a single cyclic order through the two points. —David Eppstein (talk) 17:39, 25 March 2024 (UTC)

Linking the Ring Star Problem

Dear Wikipedia members, I am a new contributor to this great free encyclopedia and would like to know if you believe linking the Ring star problem into the Traveling Salesman Problem which is a particular case of the former, would be a good idea? Thank you very much for reading me :) Jkhamphousone (talk) 18:27, 12 July 2024 (UTC)

It could be cited in § Related problems which is in § Description section. Jkhamphousone (talk) 18:28, 12 July 2024 (UTC)

That seems like a plausibly relevant problem to mention (disclaimer: I am not an expert). As with any Wikipedia page, feel free to boldly contribute your change. If you can, try to cite a source specifically mentioning the relation between problems. –jacobolus (t) 23:31, 12 July 2024 (UTC)