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

Extending double bridge, from d4

We already know how to build sequential moves, that is how to extended sequential 3-opt move to sequential 4-opt move or 4-opt move to 5-opt move. We can use the same approach to extend non-sequential 4-opt move, for example double bridge, to built some 5-opt non-sequential move.

The first option is to extend the second submove and can be made as follows:

1. Step 0
   1. Start from tour after considered double bridge move.
2. Step 1
   1. Remove last link added in the second submove of double bridge, that is: from d4 to d1.
   2. Add link between d4 and the some other city d5.
3. Step 2
   1. Remove link between d5 and its tour neighbor d6.
   2. Add link between d6 and the first city of submove, d1, to close the tour.

inOrder(c2, d5, d1, true)

double bridge (AB)EDC	d6 = t_pred(d5)	AbEDC

Note that we should make sure we have chosen this d6, tour neighbor of d5, that linked with d1 closes the tour. For example in the above case we should not use alternative d6, because it disjoins tour into two cycles:

inOrder(c2, d5, d1, true)

double bridge	d6 = t_succ(d5)	disjoining move

The first set of diagrams shows that when d5 is between c2 and d1, then for c6 we can use tour predecessor of c5. The second set of diagrams shows that when d5 is between c2 and d1, then for c6 we should not use tour successor of c5.

But what if d5 happens to be not in the upper-right segment, not between c2 and d1?

Then it can be between d2 and c3, or between c4 and d3, or between d4 and c1. Relevant diagrams for these cases are given below:

inOrder(d2, d5, c3, true)

double bridge AED(BC)	d6 = t_pred(d5)	AbdeC

 

inOrder(c4, d5, d3, true)

double bridge AE(CD)B	d6 = t_pred(d5)	AceDB

 

inOrder(d4, d5, c1, true)

double bridge A(DE)CB	d6 = t_pred(d5)	AdECB

So in this kind of extending double bridge move, for d6 we should always take the tour predecessor of d5. It is easy to check that in each case using tour successor results in disjoining move.

Aditionally, we should check check whether d5 and d6 meet the restrictions: city d5 should not be the same as d1, nor d2, nor a tour neighbor of d4 (one of these neigbors is d3). Link (d5, d6) to remove should not be the same as link (c1, c2) nor (c3, c4), already removed in the first submove.

Then discussed algorithm can be implemented as follows:

proc LK_Bridge_A3(c1, c2, c3, c4,
                  d1, d2, d3, d4: City_Number;
                  G2a: Length_Gain; tourOrderPrev: int): bool =
  ## c1..c4, d1..d4 define valid double bridge move
  ## G2a is partial gain from this double bridge,
  ## without cost of the last, closing link (d4, d1),
  ## that is:
  ##   d(c1,c2) - d(c2,c3) + d(c3,c4) - d(c4,c1) +
  ##   d(d1,d2) - d(d2,d3) + d(d3,d4)
...
  if not (tourOrderPrev == TO_ADBC):
    return false

  d4_succ = t_succ(d4)
  d4_pred = t_pred(d4)
  block find_move:
    for d5 in neighbors(d4):
      if (d5 == d4_succ) or (d5 == d4_pred):
        continue      
      if (d5 == d1) or (d5 == d2):
        continue

      G2 = G2a - distance(d4, d5)
   
      # choose d6 as predecessor of d5:
      d6 = t_pred(d5)
      if (d5 == c1) and (d6 == c2) or
         (d5 == c2) and (d6 == c1):
        continue
      if (d5 == c3) and (d6 == c4) or
         (d5 == c4) and (d6 == c3):
        continue
        
      G3a = G2 + distance(d5, d6)
      gainFromCloseUp = G3a - distance(d6, d1)
      if gainFromCloseUp > 0: # improving move found      
        improved = true
        Make_5opt_NS_Move(c1, c2, c3, c4,
                          d1, d2, d3, d4, d5, d6,
                          TO_AxbEDC) # NOTE this tourOrder is exemplary
        tourLen = tourLen - gainFromCloseUp
        Set_DLB_off(DontLook, [c1, c2, c3, c4,
                               d1, d2, d3, d4, d5, d6])
        break find_move
  #end_block find_move

  result = improved

It may not be obvious, but all four considered move types has one more common feature: all of them can be applied using exactly the same procedure: first we apply initial double bridge move, and then we apply simple 2-opt move, the very same in each case. This 2-opt (segment reversing) is equivalent to link exchange: links (d4, d1) and (d5, d6) are exchanged for (d4, d5) and (d6, d1).

proc Make_5opt_NS_Move(c1, c2, c3, c4,
                       d1, d2, d3, d4, d5, d6: City_Number;
                       tourOrder: int) =
  case tourOrder
  of TO_AxbEDC_1,  TO_AxbxdxeC_1,
     # c12-d65-d12-c34-d34, c12-d12-d65-c34-d34,
     TO_AxcxeDB, TO_AxdECB:
     # c12-d12-c34-d65-d34, c12-d12-c34-d34-d65
    Exchange_Links(d1, d2, d4, d3)
    Exchange_Links(c1, c2, c4, c3)
    Exchange_Links(d1, d3, d4, d2)  
    Exchange_Links(d1, d4, d6, d5)
  of ...:
    ...

For example type AbEDC is obtained from double bridge (AB)EDC by reversing segment B, which in this case is the segment from d5 to d1. Type AbdeC is obtained from double bridge AED(BC) by reversing joined segments EDB, which in the same as reversing joined segments CA, in this case also from d5 to d1. And so on...

Schemes of non-sequential pure 5-opt moves

There are exactly 60 pure non-sequential 5-opt move types. As in the case of non-sequential pure 4-opt move types they form two distinct groups. The first group contains 20 moves that consists of completely independent 2-opt and 3-opt moves, changing non-overlaping ranges (for example AbCde, AbcDe). We can see similar types of non-sequential moves among all k-opts where k>=4.

The remaining move types can be divided into two sub-groups, each containing 20 types. All move types in the first sub-group (II.A) have easily noticeable trait. They contain two parallel links close to each other, the same characteristic pattern which occurs in double bridge. This suggests that moves of at least some of these types can be obtained by some simple modifications of double bridge (or crossed bridge). Move types in the second sub-group (II.B) does not have this kind of connections and their possible origin is not so obvious.

All non-sequential pure 5-opt moves

Group I
AbCde	AbcDe	AbCED
AbCEd	AbCeD	AbeDc
ACBDe	ACbDe	AcBDe
ACdEB	ACdEb	AdCbe
AEBcD	AeBcD	AeCdb
AecDb	Aecdb	AEdCb
AeDCb	AeDcB
Group II.A
AbEDC	AbdeC	Acdeb
AceDB	ADbce	ADCBe
ADCeb	ADceB	ADebc
AdebC	ADeCB	AdECB
Aebcd	AEbdC	AebDC
AECbd	AECdB	AEcDB
AEDBc	AEDbC
Group II.B
AbEcd	AcdBe	ACeBd
ACebd	AcEBd	AcEbD
AcebD	AcEDb	AcEdB
ADBec	ADbeC	AdBec
AdbEC	AdbEc	AdCeB
AdEbc	AdeBc	AEbDc
AEcBd	AeCBd