3
$\begingroup$

This seems intuitive and is likely correct, but I'm looking for a paper or perhaps a more thorough proof on how a K-OPT move is equivalent to a sequence of 2-OPT moves. Or if this is wrong, something that shows why this is wrong with a counter example.

For reference, there's a blog post on how a 3-OPT is a sequence of 2-OPT moves here

$\endgroup$
3
  • 1
    $\begingroup$ In your definition of a 2-opt move is it fine to accept a worse solution when doing a 2-opt move or is a 2-opt move also allowed that (temporarily) results in a worse solution? $\endgroup$
    – PeterD
    Commented Jun 15, 2022 at 21:09
  • $\begingroup$ *...is it only allowed to accept a better solution when doing a 2-opt move or... $\endgroup$
    – PeterD
    Commented Jun 15, 2022 at 21:47
  • $\begingroup$ In this context, a worse solution is fine. I was asking in the context of perhaps a look ahead algorithm. $\endgroup$
    – jkschin
    Commented Jun 16, 2022 at 17:25

1 Answer 1

3
$\begingroup$

If you consider 2-opt moves that (temporarily) result in a worse solution, then it is possible. Lets say you have a route:

A → B → E → D → C → F → G → H → A

A 2-opt move can be seen as reversal of a part of the tour. For example the 2-opt move that results from removing the link B→E and C→F reverses all stops between B and F.

E → D → C becomes C → D → E and the tour becomes: A → B → C → D → E → F → G → H → A

We also know that, if two sequence 1 and 2 consist of the same elements, then there exists a way to transform sequence 1 into sequence 2 by solely reversing orders within sequence 1. This is called the inversion distance and there exist polynomial solutions to it. Please checkout the following references for more information on the inversion distance:

Kececioglu, J. and Sankoff, D. (1993). Exact and approximation algorithms for the inversion distance between two chromosomes. In Proc. of 4th Conference on Combinatorial Pattern Matching (CPM’93)

Bergeron, A., Mixtacki, J., & Stoye, J. (2007). The inversion distance problem.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.