Talk:2-opt

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Computer science (Rated Start-class)
WikiProject icon This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Start-Class article Start  This article has been rated as Start-Class on the project's quality scale.
 ???  This article has not yet received a rating on the project's importance scale.
 
Note icon
This article has been automatically rated by a bot or other tool because one or more other projects use this class. Please ensure the assessment is correct before removing the |auto= parameter.
WikiProject Mathematics (Rated Start-class, Low-priority)
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
Start Class
Low Priority
 Field: Analysis

Currently intending to add some more in depth explanations and decent images to this article to improve it. Would appreciate any extra articles / books on the matter other than just those quoted in External Links. Mpdehnel (talk) 12:15, 30 January 2013 (UTC)

One basic piece of info...[edit]

...is missing: a route that crosses over itself cannot be the shortest route. This needs a geometric explanation: I suppose that's because the four points form a quadrilateral, and its diagonals cannot be shorter than its sides. GregorB (talk) 20:04, 3 April 2016 (UTC)

It's not strictly relevant; 2-opt can improve routes that don't cross themselves, routes in Euclidean 3-space or many other metric spaces rarely cross themselves, and TSP can be run on problems that don't even have an underlying metric space.--Prosfilaes (talk) 19:37, 22 October 2016 (UTC)

Better code?[edit]

Instead of what the article has for 2optSwap(route, i, k), why not just "val newOrder = order.slice (0, i) ++ order.slice (i, k + 1).reverse ++ order.slice (k + 1, end)"? (Or (1, i-1) if we want to stay 1-based, but few modern languages are.) I'm not going to rewrite the whole thing right now, but that's a pretty good example of where modern languages are terser and clearer than old-school languages.--Prosfilaes (talk) 19:33, 22 October 2016 (UTC)