Non-sequential 5-opt moves – part 4 of 7

Disjoining 3-exchanges as base for 5-opt non-sequential moves, part 1

So far we have considered 5-opt non-sequential moves obtained by extending double bridge or crossed bridge move. Double bridge and crossed bridge themselves are obtained from disjoining 2-exchange submove, that is from 2-exchange starting with 12-34. But they are other disjoining k-exchanges that we can start from to built an 5-opt non-sequential move.

Among eight possible types of 3-exchanges there are four disjoining 3-exchange moves. We have already considered them, though in a different context, namely while examining 3-exchanges during constructing a sequential move. These disjoining 3-exchanges are:

        ... TO_123456 # disconnecting...
        ... TO_123465 # disconnecting...
        ... TO_124356 # disconnecting...
        ... TO_126543 # disconnecting...

12-34-56
12-34-65	12-43-56	12-65-43

The first of these disjoining 3-exchanges, 12-34-56, breaks tour into three separated cycles. It is not possible to join them into feasible tour by any additional single 2-exchange (to have then 5 exchanges in total). So we would skip this case and take a closer look at the remaining three 3-exchanges, each breaking tour into two cycles only.

General idea of construction of 5-opt non-sequential moves from disjoining 3-exchange is similar to the idea of construction of 4-opt non-sequential moves from disjoining 2-exchange and is shown on diagrams for four descentants of 12-34-65 below:

12-34-65	AEcDB	AdCeB
12-34-65	ADeCB	AcEdB

Note that while from one disjoining 2-exchange (12-34) we have obtained two 4-opt non-sequential move types: double bridge (ADBC) and crossed vertical bridge (AcdB), but any of the three disjoining 3-exchanges gives us four 5-opt non-sequential move types. For example 12-34-65 gives: AEcDB, AdCeB, ADeCB, AcEdB.