Wednesday, December 27, 2017

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)EDCd6 = t_pred(d5)AbEDC
c1 c2 c3 c4 d1 d2 d3 d4 d4 d5 d6 d1 d1 d4 d5 d6

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 bridged6 = t_succ(d5)disjoining move
s c1 c2 c3 c4 d1 d2 d3 d4 d4 d6 d5 d1 d1 d4 d6 d5

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
c1 c2 c3 c4 d3 d4 d1 d2 d4 d1 d6 d5 d4 d1 d6 d5

 

inOrder(c4, d5, d3, true)
double bridge AE(CD)Bd6 = t_pred(d5)AceDB
c1 c2 c3 c4 d1 d2 d3 d4 d1 d4 d6 d5 d1 d4 d6 d5

 

inOrder(d4, d5, c1, true)
double bridge A(DE)CBd6 = t_pred(d5)AdECB
c1 c2 c3 c4 d1 d2 d3 d4 d1 d4 d5 d6 d1 d4 d5 d6

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

Friday, December 15, 2017

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
AbCdeAbcDeAbCED
AbCEdAbCeDAbeDc
ACBDeACbDeAcBDe
ACdEBACdEbAdCbe
AEBcDAeBcDAeCdb
AecDbAecdbAEdCb
AeDCbAeDcB
Group II.A
AbEDCAbdeCAcdeb
AceDBADbceADCBe
ADCebADceBADebc
AdebCADeCBAdECB
AebcdAEbdCAebDC
AECbdAECdBAEcDB
AEDBcAEDbC
Group II.B
AbEcdAcdBeACeBd
ACebdAcEBdAcEbD
AcebDAcEDbAcEdB
ADBecADbeCAdBec
AdbECAdbEcAdCeB
AdEbcAdeBcAEbDc
AEcBdAeCBd