Talk:3-opt
Add topic | This article is rated Stub-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: 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. User:Nwiggin2 (talk) 05:49, 11 September 2023 (UTC)