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