Saturday, February 17, 2018

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

No comments:

Post a Comment