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

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

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

Now we look for two links to remove: (d1, d2) and (d3, d4). (We can also say that we look for two pairs of cities adjacent to each other on tour, determining these links.)

In case of 12-34-65 move type one of these pairs should be inside [c2, c3] segment. For the second we should consider two options: it can be inside [c5, c1] segment:

12-34-65	AEcDB	AdCeB

or inside [c4, c6] segment:

12-34-65	ADeCB	AcEdB

But we san simplify our task and treat [c4, c6] and [c5, c1] as one segment of consecutive cities: from c4 to c1, with additional condition that link to remove cannot be the same as (c5, c6).

We can use the same reasoning for 12-43-56 and 12-65-43 move types. Then we would have:

  var
    cFrom, cTo: City_Number  # ends of segment with first link to remove
    canBreakLink: bool
...
  case tourOrder
  of TO_123465:
    if (2 * Segment_Size(cF2,cF3)) <= N:    
      (cFrom, cTo) = (cF2, cF3)
    else:
      (cFrom, cTo) = (cF4, cF1)
  of TO_124356:
    if (2 * Segment_Size(cF6,cF1)) <= N:    
      (cFrom, cTo) = (cF6, cF1)
    else:
      (cFrom, cTo) = (cF2, cF5)
  of TO_126543:
    if (2 * Segment_Size(cF5,cF4)) <= N:    
      (cFrom, cTo) = (cF2, cF3)
    else:
      (cFrom, cTo) = (cF3, cF6)
  else:
    discard
  #end_case
  
  block find_promising_moves:
    goodSufficesList = @[]  # empty list
    d1 = cFrom
    d2 = t_succ(d1)
    while d2 != cTo:
      canBreakLink = true
      if (d1==cF1) and (d2==cF2)  or
         (d1==cF2) and (d2==cF1):
        canBreakLink = false
      if (d1==cF3) and (d2==cF4)  or
         (d1==cF4) and (d2==cF3):
        canBreakLink = false
      if (d1==cF5) and (d2==cF6)  or
         (d1==cF6) and (d2==cF5):
        canBreakLink = false

      if canBreakLink:
        G1a = G0 + distance(d1, d2)
        goodSuffix = Suffix(c2iplus1: d1, c2iplus2: d2,
                            Ga: G1a, tourOrder: tourOrder)
        goodSufficesList.add(goodSuffix)
      d1 = d2
      d2 = t_succ(d1)
    #end_loop while d2 != cTo
  #end_block find_promising_moves
  ...

On the other hand we can simplify the code by taking advantage of the fact that 12-43-56 and 12-65-43 are just rotated versions of 12-34-65. Then we obtain:

proc LK_Bridge_B1(c1, c2, c3, c4, c5, c6: City_Number;
                  G0: Length_Gain;
                  tourOrder: int): bool =
  var
    improved: bool
    fwd: bool
    cF1, cF2, cF3, cF4, cF5, cF6: City_Number
    cFrom, cTo: City_Number  # ends of segment with first link to remove
    d1_is_inside_c2_c3: bool
    d1, d2: City_Number
    Ga, G1a: Length_Gain
    goodSuffix: Suffix
    goodSufficesList: seq[Suffix]
    breadth: int

  improved = false  # rotate all other types of move to use only TO_123465
  fwd = (c2 == t_succ(c1))
  case tourOrder
  of TO_123465:
    if fwd:
      (cF1, cF2, cF3, cF4, cF5, cF6) = (c1, c2, c3, c4, c5, c6)
    else:
      (cF1, cF2, cF3, cF4, cF5, cF6) = (c4, c3, c2, c1, c6, c5)
  of TO_124356:
    if fwd:
      (cF1, cF2, cF3, cF4, cF5, cF6) = (c5, c6, c1, c2, c3, c4)
    else:
      (cF1, cF2, cF3, cF4, cF5, cF6) = (c2, c1, c6, c5, c4, c3)
  of TO_126543:
    if fwd:
      (cF1, cF2, cF3, cF4, cF5, cF6) = (c6, c5, c4, c3, c2, c1)
    else:
      (cF1, cF2, cF3, cF4, cF5, cF6) = (c3, c4, c5, c6, c1, c2)
  else:
    discard
  #end_case

  # we want to scan shorter segment
  if (2 * Segment_Size(cF2,cF3)) <= N:
    (cFrom, cTo) = (cF2, cF3)
    d1_is_inside_c2_c3 = true
  else:
    (cFrom, cTo) = (cF4, cF1)
    d1_is_inside_c2_c3 = false
  #end_if
    
  block find_promising_moves:
    goodSufficesList = @[]  # empty list
    d1 = cFrom
    d2 = t_succ(d1)
    while d1 != cTo and d2 != cTo:
      if (d1==cF5) and (d2==cF6)  or
         (d1==cF6) and (d2==cF5):
        discard
      else:
        G1a = G0 + distance(d1, d2)
        goodSuffix = Suffix(c2iplus1: d1, c2iplus2: d2, Ga: G1a)
        goodSufficesList.add(goodSuffix)
      #end_if
      d1 = d2
      d2 = t_succ(d1)
    #end_loop while d2 != cTo
  #end_block find_promising_moves

  block evaluate_promising_moves:
    if len(goodSufficesList) == 0:
      break evaluate_promising_moves
    SortSufficesByGain(goodSufficesList)
    #breadth = len(goodSufficesList) # NOTE!!!
    breadth = min(len(goodSufficesList), Max_Breadth_1)
    for mve in 0 .. breadth-1:
      goodSuffix = goodSufficesList[mve]
      d1 = goodSuffix.c2iplus1
      d2 = goodSuffix.c2iplus2
      Ga = goodSuffix.Ga
      improved = LK_Bridge_B2(cF1, cF2, cF3, cF4, cF5, cF6,
                              d1, d2, Ga, d1_is_inside_c2_c3)
      if improved:
        break evaluate_promising_moves
  #end_block evaluate_promising_moves

  result = improved

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

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

For obtaining a code for this kind of 5-opt non-sequential moves we can modify a proc for non-sequential 4-opt moves this way:

proc LK_2NS_Move(c1, c2: City_Number;
                 G1a: Length_Gain): bool =
  var
    improved: bool
    c3, c4: City_Number
    c2_pred, c2_succ: City_Number
    c3_pred, c3_succ: City_Number
    c4_A, c4_B: City_Number
    fwd: bool
    G1, G2a, Ga: Length_Gain
    gainFromCloseUp: Length_Gain
    goodSuffix: Suffix
    goodSufficesList: seq[Suffix]    
    tourOrder: int
    tried_c3: int = 0
    breadth: int

  improved = false
  fwd = (c2 == t_succ(c1))
  c2_succ = t_succ(c2)
  c2_pred = t_pred(c2)
  block find_promising_moves:
    goodSufficesList = @[]  # empty list (sequence)
    for c3 in neighbors(c2):
      if tried_c3 >= 2*Max_Breadth_1:
        break find_promising_moves
      if (c3 == c2_succ) or (c3 == c2_pred):
        continue
      G1 = G1a - distance(c2, c3)
      if G1 <= 0:
        break

      # if G1 > 0:
      c3_succ = t_succ(c3)
      c3_pred = t_pred(c3)
      if fwd:
        c4_A = c3_succ
        c4_B = c3_pred
      else:
        c4_A = c3_pred
        c4_B = c3_succ
      for c4 in [c4_A, c4_B]:
        if c4 == c1:  # NOTE
          continue
        G2a = G1 + distance(c3, c4)
        if G2a > 0:
          goodSuffix = Suffix(c2iplus1: c3, c2iplus2: c4,
                              Ga: G2a)
          goodSufficesList.add(goodSuffix)
          tried_c3 = tried_c3 + 1
      #end_loop for c4
    #end_loop for c3
  #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]
      c3 = goodSuffix.c2iplus1
      c4 = goodSuffix.c2iplus2
      Ga = goodSuffix.Ga
      gainFromCloseUp = Ga - distance(c4, c1)
      if gainFromCloseUp > 0:
        if fwd and (c4 == t_succ(c3))  or
           not fwd and (c4 == t_pred(c3)):
          # disconnecting 2-move (||)
          if LK_Bridge_A1(c1, c2, c3, c4, gainFromCloseUp):
            improved = true
            break evaluate_promising_moves
        else:
          # connecting 2-move (X)
          improved = true
          Make_2opt_Move(c1, c2, c3, c4)
          tourLen = tourLen - gainFromCloseUp
          Set_DLB_off(DontLook, [c1, c2, c3, c4])
          break evaluate_promising_moves
      #end_if gainFromCloseUp > 0

      # improving move has not been found;
      # extend current 2-move ('X' or '||') to 3-move
      # (disconnecting or connecting) and keep trying
      if fwd and (c4 == t_succ(c3))  or
         not fwd and (c4 == t_pred(c3)):
        tourOrder = TO_1234
      else:
        tourOrder = TO_1243
      #end_if
      if LK_3NS_Move(c1, c2, c3, c4, Ga, tourOrder):
        improved = true
        break evaluate_promising_moves

  #end_block evaluate_promising_moves
  result = improved

proc LK_3NS_Move(c1, c2, c3, c4: City_Number;
                 G2a: Length_Gain;
                 tourOrderPrev: int): bool =
  var
    improved: bool
    c5, c6: City_Number
    c4_pred, c4_succ: City_Number
    c5_pred, c5_succ: City_Number
    fwd: bool
    G2, Ga: Length_Gain
    G3a, gainFromCloseUp: Length_Gain
    goodSuffix: Suffix
    goodSufficesList: seq[Suffix]
    tried_c5: int = 0
    breadth: int
    tourOrder: int

  improved = false
  fwd = (c2 == t_succ(c1))
  c4_succ = t_succ(c4)
  c4_pred = t_pred(c4)

  block find_promising_moves:
    goodSufficesList = @[]  # empty list (sequence)
    for c5 in neighbors(c4):
      if tried_c5 >= 2*Max_Breadth_2:
        break find_promising_moves
      if (c5 == c4_succ) or (c5 == c4_pred):
        continue
      G2 = G2a - distance(c4, c5)
      if G2  <= 0:
        break

      # if G2 > 0:
      c5_succ = t_succ(c5)
      c5_pred = t_pred(c5)
      for c6 in [c5_succ, c5_pred]:
        # testing available variants
        case tourOrderPrev

        of TO_1234:
          if inOrder(c2, c5, c3, fwd):
             if (c6 == c1):
                continue
             if inOrder(c2, c6, c5, fwd):
                tourOrder = TO_126534
             else:
                tourOrder = TO_125634
          else:
             if (c6 == c2):
                continue
             if inOrder(c4, c5, c6, fwd):
                tourOrder = TO_123456 # disconnecting
             else:
                tourOrder = TO_123465 # disconnecting

        of TO_1243:
          if inOrder(c2, c5, c4, fwd):
             if inOrder(c2, c6, c5, fwd):
                tourOrder = TO_126543 # disconnecting
             else:
                if (c5 == c1) and (c6 == c2) or
                   (c5 == c2) and (c6 == c1):
                   continue
                tourOrder = TO_125643
          else:
             if inOrder(c3, c6, c5, fwd):
                tourOrder = TO_124365
             else:
                if (c5 == c1) and (c6 == c2) or
                   (c5 == c2) and (c6 == c1):
                   continue
                tourOrder = TO_124356 # disconnecting
        else:
          continue # no more possibilities
        #end_case tourOrderPrev

        tried_c5 = tried_c5 + 1
        G3a = G2 + distance(c5, c6)
        goodSuffix = Suffix(c2iplus1: c5, c2iplus2: c6,
                            Ga: G3a, tourOrder: tourOrder)
        goodSufficesList.add(goodSuffix)
      #end_loop for c6
    #end_loop for c5
  #end_block find_promising_moves

  block evaluate_promising_moves:
    if len(goodSufficesList) == 0:
      # no promising moves
      break evaluate_promising_moves
    SortSufficesByGain(goodSufficesList)
    # pass promising moves, one by one, to next level
    # to check them there
    breadth = min(len(goodSufficesList), Max_Breadth_2)
    for mve in 0 .. breadth-1:
      goodSuffix = goodSufficesList[mve]
      c5 = goodSuffix.c2iplus1
      c6 = goodSuffix.c2iplus2     
      Ga = goodSuffix.Ga
      tourOrder = goodSuffix.tourOrder
      gainFromCloseUp = Ga - distance(c6, c1)
      if gainFromCloseUp > 0:
        case tourOrder
        of TO_125634, TO_126534, TO_125643, TO_124365:
          # pure 3-opt move
          improved = true
          Make_3opt_Move(c1, c2, c3, c4, c5, c6, tourOrder)
          tourLen = tourLen - gainFromCloseUp
          Set_DLB_off(DontLook, [c1, c2, c3, c4, c5, c6])
          break evaluate_promising_moves

        of TO_123465, TO_124356, TO_126543:
          # disconnecting into 2 parts, use 2-exchange to connect
          ...
          if LK_Bridge_B1(...):
            improved = true
            break evaluate_promising_moves

        else: # TO_123456
          continue
        #end_case

  #end_block evaluate_promising_moves
  result = improved

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.

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

Extending crossed bridge or double bridge 'from d3'

If we take a closer look at diagram for AdebC move type, we can notice that it cannot be made by extending double bridge or crossed bridge from the last city (d4) in move, if the second submove starts from d1-d2:

On the other hand, if we denoted the city we want to extend move from as d3, then there would be no consistency in the numbering:

Note that so far we used only d1-d2 ordering. Instead we can use the first two cities in the reverse order:

proc LK_Bridge_A1(...) =
...
      improved = LK_Bridge_A2(cF1, cF2, cF3, cF4, d1, d2, Ga)
      if not improved:
        improved = LK_Bridge_A2(cF1, cF2, cF3, cF4, d2, d1, Ga) # NOTE

and get

Using the same approach we obtain:

proc LK_Bridge_A3(...) = 
...
  fwd = (d2 == t_succ(d1))
...
      # choose d6
      case tourOrderPrev
      of TO_ADBC:
        if fwd:
          d6 = t_pred(d5)
          if inOrder(d3, d5, c1, true):
            tourOrder = TO_AxdECB_1   # AdECB
          elif inOrder(c4, d5, d4, true):
            tourOrder = TO_AxcxeDB_1  # AceDB
          elif inOrder(d2, d5, c3, true):
            tourOrder = TO_AxbxdxeC_1 # AbdeC
          else:
            tourOrder = TO_AxbEDC_1   # AbEDC
        else:  # not fwd
          d6 = t_succ(d5)
          if inOrder(d3, d5, c1, true):
            tourOrder = TO_ADxcxeB_3  # ADceB
          elif inOrder(c4, d5, d4, true):
            tourOrder = TO_AECxdB_3   # AECdB
          elif inOrder(d1, d5, c3, true):
            tourOrder = TO_AEDxbC_3   # AEDbC
          else:
            tourOrder = TO_AxdxexbC_3 # AdebC
        #end_if fwd
      of TO_AxcxdB:
        if fwd:
          if inOrder(d3, d5, c1, true):
            d6 = t_succ(d5)
            tourOrder = TO_AECxdB_2   # AECdB
          elif inOrder(c4, d5, d4, true):
            d6 = t_succ(d5)
            tourOrder = TO_ADxcxeB_2  # 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:  # not fwd
          if inOrder(d4, d5, c1, true):
            d6 = t_pred(d5)
            tourOrder = TO_AEDxbC_4   # AEDbC
          elif inOrder(c4, d5, d3, true):
            d6 = t_pred(d5)
            tourOrder = TO_AxdxexbC_4 # AdebC
          elif inOrder(d1, d5, c3, true):
            d6 = t_succ(d5)
            tourOrder = TO_AxdECB_4   # AdECB
          else:
            d6 = t_succ(d5)
            tourOrder = TO_AxcxeDB_4  # AceDB
        #end_if fwd
...

and

proc Make_5opt_NS_Move(...) =
  case tourOrder
  of TO_AxbEDC_1, TO_AxbxdxeC_1, TO_AxcxeDB_1, TO_AxdECB_1:
    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_AxbxdxeC_2, TO_AxbEDC_2, TO_ADxcxeB_2, TO_AECxdB_2:
    Exchange_Links(d1, d2, d4, d3)
    Exchange_Links(c1, c2, c4, c3)
    Exchange_Links(d1, d4, d6, d5)

  of TO_ADxcxeB_3, TO_AECxdB_3, TO_AEDxbC_3, TO_AxdxexbC_3:
    Exchange_Links(d2, d1, d4, d3)
    Exchange_Links(c1, c2, c4, c3)
    Exchange_Links(d2, d3, d4, d1)
    Exchange_Links(d1, d4, d6, d5)
  of TO_AEDxbC_4, TO_AxdxexbC_4, TO_AxdECB_4, TO_AxcxeDB_4:
    Exchange_Links(d2, d1, d4, d3)
    Exchange_Links(c1, c2, c4, c3)
    Exchange_Links(d1, d4, d6, d5)
  ...

Adding these additional types for "backward" second submove requires more code, as can be seen above, slightly changes running times, but makes resulting tours less than 0.1% better, so it may or may be not worth introducing.

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