Talk:2-opt

Comments

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)

Maybe the text example ("A B C ...") could be adjusted so it corresponds to the picture in the article. Indexing convention starts from 1? Is that a good idea? Be explicit about what indices i, k mean. The nodes after the crossed edges, not before it.

One basic piece of info...

...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?

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)

Efficient implementation is not actually efficient

The efficient implementation uses the function reverse(begin(begin(path)+i, begin(path)+j) as if it was O(1), but actually in most (if not all) modern programming lenguages it's an O(n) operation, making the worst case performance of the efficient implementation as inefficient as the inefficient one. --SergioDA1 (talk • contribs) 10:29, 16 June 2022 (UTC)

Hey I am the original author of the Efficient Implementation.

And you are right, the function to construct the route is O(n).

What I was porposing is that you dont always have to perform this O(n) operation. It can be skipped sometimes by performing an O(1) check, which increasees the real world runtime of the algorithm. DollarAkshay (talk) 19:32, 27 June 2022 (UTC)

Using squared distances

An edit on 3 May 2022‎ adds that using squared distances can be quicker since it avoids a sqrt operation because "we only care about comparing two distances and not the exact distance" and the following code sample shows how squared distances are being used.

This does not work.

Yes, if $dist_{1}^{2}<dist_{2}^{2}$ then $dist_{1}<dist_{2}$, but it doesn't work when you add values together $dist_{1}^{2}+dist_{2}^{2}<dist_{3}^{2}$ does not imply $dist_{1}+dist_{2}<dist_{3}$. The usage of squared distances is wrong and should be removed. — Preceding unsigned comment added by Andrewborrell (talk • contribs) 22:48, 29 September 2022 (UTC)

Hey @Andrewborrell I realized that the implementation has left out a lot of the functions used in the code. Here the function pathLengthSq is actually the squared distance between each vertex and not the lenth of the whole path squared. I am to blame because the comment I wrote implies the latter. I will now be including a full example with all the missing functions to clarify the ambiguity in the efficient implementation DollarAkshay (talk) 09:32, 17 December 2022 (UTC)

The full code still seems incorrect to me: pathLengthSq is the sum of squares, exactly as in the example Andrew points out.

As a simple example, consider a right triangle ABC (BC is the diagonal).

B

A C

AB + AC > BC

AB² + AC² = BC²

So, pathLengthSq(BA, AC) == pathLengthSq(BC) but BC is actually smaller. Glebm1 (talk) 17:43, 13 February 2023 (UTC)

I believe you are right. Comparing squared distance only works when you are not summing up the values. I have replaced the `dist2` function with `dist` which should calculate the correct eucledian distance DollarAkshay (talk) 23:15, 5 May 2024 (UTC)