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

Extending crossed bridge, from d4

We can use the same approach as in part 1 to extend crossed bridge and build some 5-opt non-sequential move.

inOrder(c2, d5, d1, true)

crossed bridge (AB)deC	d6 = t_pred(d5)	AbdeC

Note that AbdeC is the same type of move that we obtained from double bridge in previous part, with different cities order: some cities have different numbers.

inOrder(d2, d5, c3, true)

crossed bridge	d6 = t_pred(d5)	AbEDC

Note that AbEDC is the very same type of move that we obtained from double bridge in previous part, with different cities order: some cities have different numbers.

 

inOrder(c4, d5, d4, true)

crossed bridge	d6 = t_succ(d5)	ADceB

 

inOrder(d3, d5, c1, true)

crossed bridge	d6 = t_succ(d5)	AECdB

So we have:

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 or crossed bridge move
  ## G2a is partial gain from this 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)
  var
    improved: bool
    d5, d6: City_Number    
    d4_pred, d4_succ: City_Number
    d5_pred, d5_succ: City_Number
    G2, G3a, gainFromCloseUp: Length_Gain
    goodSuffix: Suffix
    goodSufficesList: seq[Suffix]
    tourOrder: int
    tried_d5: int = 0
    breadth: int

  improved = false
  d4_succ = t_succ(d4)
  d4_pred = t_pred(d4)
  block find_promising_moves:
    goodSufficesList = @[]  # empty list (sequence)
    for d5 in neighbors(d4):
      if tried_d5 >= 2*Max_Breadth_1:
        break find_promising_moves
      if (d5 == d4_succ) or (d5 == d4_pred):
        continue      
      if (d5 == d1) or (d5 == d2):
        continue

      G2 = G2a - distance(d4, d5)
   
      # choose d6
      case tourOrderPrev
      of TO_ADBC:
        d6 = t_pred(d5)
        if inOrder(d3, d5, c1, true):
          tourOrder = TO_AxdECB     # AdECB
        elif inOrder(c4, d5, d4, true):
          tourOrder = TO_AxcxeDB    # AceDB
        elif inOrder(d2, d5, c3, true):
          tourOrder = TO_AxbxdxeC_1 # AbdeC
        else:
          tourOrder = TO_AxbEDC_1   # AbEDC
      of TO_AxcxdB:
        if inOrder(d3, d5, c1, true):
          d6 = t_succ(d5)
          tourOrder = TO_AECxdB     # AECdB
        elif inOrder(c4, d5, d4, true):
          d6 = t_succ(d5)
          tourOrder = TO_ADxcxeB    # ADceB
        elif inOrder(d2, d5, c3, true):
          d6 = t_pred(d5)
          tourOrder = TO_AxbEDC_2   # AbEDC
        else:
          d6 = t_pred(d5)
          tourOrder = TO_AxbxdxeC_2 # AbdeC
      else:
        discard
      #endcase
      
      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)

      goodSuffix = Suffix(c2iplus1: d5, c2iplus2: d6,
                          tourOrder: tourOrder, Ga: G3a)
      goodSufficesList.add(goodSuffix)
      tried_d5 = tried_d5 + 1
    #end_loop for d5
  #end_block find_promising_moves  

  block evaluate_promising_moves:
    if len(goodSufficesList) == 0:
      break evaluate_promising_moves
    SortSufficesByGain(goodSufficesList)
    breadth = min(len(goodSufficesList), Max_Breadth_1)
    for mve in 0 .. breadth-1:
      goodSuffix = goodSufficesList[mve]
      d5 = goodSuffix.c2iplus1
      d6 = goodSuffix.c2iplus2
      G3a = goodSuffix.Ga
      tourOrder = goodSuffix.tourOrder
      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,
                          tourOrder)
        tourLen = tourLen - gainFromCloseUp
        Set_DLB_off(DontLook, [c1, c2, c3, c4,
                               d1, d2, d3, d4, d5, d6])
        break evaluate_promising_moves
  #end_block evaluate_promising_moves
  result = improved

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 TO_ADxcxeB, TO_AECxdB,
    # c12-d12-c34-d56-d43, c12-d12-c34-d43-d56
    TO_AxbxdxeC_2, TO_AxbEDC_2:
    # 12-d65-d12-c34d-43, c12-d12-d65-c34d-43
    Exchange_Links(d1, d2, d4, d3)
    Exchange_Links(c1, c2, c4, c3) 
    Exchange_Links(d1, d4, d6, d5)
  else:
    discard
  #end_case