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

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

The last part is looking for such pair (d3, d4) that constructed move improves the tour:

proc LK_Bridge_B2(c1, c2, c3, c4, c5, c6, d1, d2: City_Number;
                  G1a: Length_Gain,
                  d1_is_inside_c2_c3: bool): bool =
  var
    improved: bool
    d3, d4: City_Number
    d2_pred, d2_succ: City_Number
    d3_pred, d3_succ: City_Number
    G1, G2a, gainFromCloseUp: Length_Gain
    goodSuffix: Suffix
    goodSufficesList: seq[Suffix]
    tourOrder: int
    tried_c3: int = 0
    breadth: int
    
  improved = false
  d2_succ = t_succ(d2)
  d2_pred = t_pred(d2)
  block find_promising_moves:
    # find d3 as a candidate for end of link (d2,d3) to add
    goodSufficesList = @[]  # empty list 
    for d3 in neighbors(d2):
      if tried_c3 >= 2*Max_Breadth_1:
        break find_promising_moves
      if (d3 == d2_succ) or (d3 == d2_pred):
        continue
      if inOrder(c2, d3, c3, true) == d1_is_inside_c2_c3:
        continue

      G1 = G1a - distance(d2, d3)
      # choose d4 as one of the two tour neighbors of d3:
      d3_succ = t_succ(d3)
      d3_pred = t_pred(d3)
      for d4 in [d3_succ, d3_pred]:
        if d4 == d2:
          continue
        if (d3 == c1) and (d4 == c2)  or
           (d3 == c2) and (d4 == c1):
          continue
        if (d3 == c3) and (d4 == c4)  or
           (d3 == c4) and (d4 == c3):
          continue          
        if (d3 == c5) and (d4 == c6)  or
           (d3 == c6) and (d4 == c5):
          continue

        G2a = G1 + distance(d3, d4)

        if inOrder(c4, d1, c6, true) or
           inOrder(c4, d3, c6, true):
           if inOrder(d1, d3, d4, true):
             tourOrder = TO_AExcDB   # AEcDB
           else:
             tourOrder = TO_AdCxeB   # AdCeB
        else:
           # inOrder(c5, d1, c1, true) or
           # inOrder(c5, d3, c1, true)
           if inOrder(d1, d3, d4, true):
             tourOrder = TO_ADxeCB   # ADeCB
           else:
             tourOrder = TO_AxcExdB  # AcEdB

        goodSuffix = Suffix(c2iplus1: d3, c2iplus2: d4,
                            Ga: G2a, tourOrder: tourOrder)
        goodSufficesList.add(goodSuffix)
        tried_c3 = tried_c3 + 1
      #end_loop for d4
    #end_loop for d3
  #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]
      d3 = goodSuffix.c2iplus1
      d4 = goodSuffix.c2iplus2
      G2a = goodSuffix.Ga
      tourOrder = goodSuffix.tourOrder
      gainFromCloseUp = G2a - distance(d4, d1)
      if gainFromCloseUp > 0: # improving move found
        improved = true
        Make_5opt_NS_MoveB(c1, c2, c3, c4, c5, c6,
                           d1, d2, d3, d4,
                           tourOrder)
        tourLen = tourLen - gainFromCloseUp
        Set_DLB_off(DontLook, [c1, c2, c3, c4, c5, c6,
                               d1, d2, d3, d4])
        break evaluate_promising_moves
  #end_block evaluate_promising_moves

  result = improved

Finally we need a proc for actually making the move we have found:

proc Make_5opt_NS_MoveB(c1, c2, c3, c4, c5, c6,
                        d1, d2, d3, d4: City_Number;
                        tourOrder: int) =

  case tourOrder
  of TO_AExcDB, TO_AxcExdB:
    Exchange_Links(c1, c2, c5, c6)
    Exchange_Links(d1, d2, d4, d3)
    Exchange_Links(c3, c4, c5, c2)
    Exchange_Links(d1, d3, d2, d4)

  of TO_ADxeCB, TO_AdCxeB:
    Exchange_Links(c1, c2, c5, c6)
    Exchange_Links(d1, d2, d3, d4)
    Exchange_Links(c3, c4, c5, c2)

  else:
    echo "Unknown 5-opt non-sequential move: ", tourOrder
    quit 1