Talk:3-opt

Latest comment: 1 year ago by Nwiggin2 in topic Article needs rewrite

missing cases?

edit

I think there are missing cases. Could it be? Please check the following: [1]http://tsp-basics.blogspot.com/2017/03/3-opt-move.html GabyEmily (talk) 08:57, 26 February 2023 (UTC)Reply

Article needs rewrite

edit

This article did not have a correct explanation of what a 3-Opt exchange is, and the implementation was also not correct.

Justification: A 3-Opt exchange swaps three existing edges for three new edges. One way to implement this exchange is to execute a sequence of either two or three 2-Opt exchanges. If a given implementation uses a simple array/list data structure to represent the tour, a single 2-Opt exchange may be characterized as a reversal of a segment in the tour. However, is impossible for a single segment reversal to "delete 3 connections" as claimed in the article/example code (one reversal is equivalent to a single 2-Opt exchange, not a 3-Opt exchange).

Additionally I think the article needs to explain 3-Opt more carefully before diving into a naive implementation. For the pseudocode, try a more efficient graph algorithm: for each node, explore a search tree of 6-edge alternating trails starting from that node (with additional rules to prune the search), and then compute the improved tour as the symmetric difference of the trail and the tour[2]. User:Nwiggin2 (talk) 05:49, 11 September 2023 (UTC)Reply