Talk:3-opt
 | This article is rated List-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | ||||||||||
| |||||||||||
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)
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)