How does the 3-opt algorithm for TSP work? - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-09-18T03:06:17Z https://cs.stackexchange.com/feeds/question/19808 https://creativecommons.org/licenses/by-sa/4.0/rdf https://cs.stackexchange.com/q/19808 7 How does the 3-opt algorithm for TSP work? u3l https://cs.stackexchange.com/users/12945 2014-01-18T16:42:44Z 2016-10-26T23:09:02Z <p>I understand that the 3-Opt Heuristic for solving the Traveling Salesman problem involves removing three edges from a graph and adding three more to recomplete the tour. However, I've seen many papers that mention that when three edges are removed, there remain only 2 possible ways to recombine the tour - this doesn't make sense to me.</p> <p>For example, I found a paper  that says:</p> <blockquote> <p>The 3-opt algorithm works in a similar fashion, but instead of removing two edges we remove three. This means that we have two ways of reconnecting the three paths into a valid tour1 (ﬁgure 2 and ﬁgure 3). A 3-opt move can actually be seen as two or three 2-opt moves.</p> </blockquote> <p>However, I count 3 different ways to reconnect the tour. What am I missing here?</p> <p>Also, can someone link me to an algorithm for 3-opt if possible? I'm just trying to understand it, but I haven't come across any clear algorithms yet: all resources I find simply say "remove three edges, reconnect them". That's it, which is sort of vague.</p> <p>Here are the 3 tours that seem to me to be 3-opt moves after removing three edges.</p> <p><img src="https://i.stack.imgur.com/KynPB.png" alt="enter image description here"></p> <hr> <ol> <li><a href="http://web.tuke.sk/fei-cit/butka/hop/htsp.pdf" rel="nofollow noreferrer">Heuristics for the Traveling Salesman Problem</a> by C. Nilsson</li> </ol> https://cs.stackexchange.com/questions/19808/how-does-the-3-opt-algorithm-for-tsp-work/19810#19810 6 Answer by Yuval Filmus for How does the 3-opt algorithm for TSP work? Yuval Filmus https://cs.stackexchange.com/users/683 2014-01-18T18:07:14Z 2014-01-18T18:07:14Z <p>You missed the footnote &mdash; these ways are "not including the connections being identical to a single 2-opt move". Indeed, there are only two permutations in $S_3$ without fixed points (also known as <em>derangements</em>), namely $(123)$ and $(132)$. More generally, for a $k$-opt move it is enough to consider permutations without fixed points, since those with $t$ fixed points are $(k-t)$-moves. </p> <p>The algorithm for $k$-opt local search is as follows. Start with some initial solution, say the one produced by Christofides's algorithm. Repeatedly try to improve it by performing a $k$-opt: choose $k$ edges and reconnect them in a different way (this time it's OK if the move is also an $\ell$-move for some $\ell &lt; k$) that results in a shorter tour.</p> <p>The way this is implemented is by going over all sets of $k$ edges and over all ways of reconnecting the edges, perhaps in some intelligent order, and computing the difference in length (there is no need to recompute the length of the entire tour, just the different of length; that takes $O(k)$ instead of $O(n)$); if an improvement is found, we make the switch and repeat from the beginning. We continue like that until we get stuck.</p> <p>A different variant is to always try all possibilities, and use the one that results in the best improvement. There are also other variants which you can probably find in the literature.</p> https://cs.stackexchange.com/questions/19808/how-does-the-3-opt-algorithm-for-tsp-work/22230#22230 0 Answer by matejs for How does the 3-opt algorithm for TSP work? matejs https://cs.stackexchange.com/users/15241 2014-03-03T18:36:23Z 2014-03-03T18:36:23Z <p>Lets say we have 3 points A, B and C. First we swap(A,B) and then we only can swap(B,C) or swap(A,C). This way we only have two different possibilities.</p> https://cs.stackexchange.com/questions/19808/how-does-the-3-opt-algorithm-for-tsp-work/63914#63914 0 Answer by kritinsai for How does the 3-opt algorithm for TSP work? kritinsai https://cs.stackexchange.com/users/58909 2016-09-26T17:26:50Z 2016-09-26T17:26:50Z <p>I could find 4 3-opt moves (which are not 2-opt): <a href="https://i.stack.imgur.com/PAhkl.jpg" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/PAhkl.jpg" alt="enter image description here"></a> If i gave the hexagon tour a numbering of 123456 (starting from the top left vertex), the other tours would have numbers of 125634, 124365, 126534 and 125643, which are a subset of the derangement of 12 (where 3456 is being deranged).</p>