This is the
talk page for discussing improvements to the
Travelling salesman problem article. This is not a forum for general discussion of the article's subject. |
Article policies
|
Find sources: Google ( books · news · scholar · free images · WP refs) · FENS · JSTOR · TWL |
Archives:
1,
2Auto-archiving period: 365 days
![]() |
![]() | This ![]() It is of interest to multiple WikiProjects. | ||||||||||||||||||||||||||||||||||||||||
|
![]() | Text and/or other creative content from Travelling salesman problem was copied or moved into Christofides algorithm. The former page's history now serves to provide attribution for that content in the latter page, and it must not be deleted as long as the latter page exists. |
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? /info/en/?search=File:Bruteforce.gif /info/en/?search=File:Branchbound.gif /info/en/?search=File:Nearestneighbor.gif /info/en/?search=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)
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 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)
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:
MedAnisMessaoudi ( talk) 16:55, 12 March 2024 (UTC)
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)
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)