LK – alternative calling subsequent moves

Used with bigger values for breadths (eg. 24, 24, 24, 24, 24, Max_Breadth_K=3) gives similar results, but is up to two times faster than the code showed previously. Some people find this approach also simpler and more convincing.

type
  PromisingMove = object
    c1, c2, c3, c4, c5, c6, c7, c8, c9, c10: City_Number
    Ga: Length_Gain
    moveType: int
    tourOrder: int

const
  HalfListSize = 20
var
  promisingMoves: array[0..2*HalfListSize, PromisingMove]
  emptyListPos: int

proc ClearPromisingMoves() =
  for i in 0 .. len(promisingMoves)-1:
    promisingMoves[i].Ga = 0
  emptyListPos = 0

proc SortPromisingMoves() =
  sort(promisingMoves) do (x,y: PromisingMove) -> int:
       result = cmp(y.Ga, x.Ga)

proc AddToPromisingMoves(move: PromisingMove) =
  promisingMoves[emptyListPos] = move
  emptyListPos = emptyListPos + 1
  if emptyListPos > 2*HalfListSize:
    # sort list by gain, then treat worse half as not filled
    SortPromisingMoves()
    emptyListPos = HalfListSize + 1

proc GetAllPromisigMoves(): seq[PromisingMove] =
  var
    allMoves: seq[PromisingMove]
  allMoves = @[]  # empty list (sequence)
  SortPromisingMoves()
  for i in 0 .. min(emptyListPos, HalfListSize)-1:
    allMoves.add(promisingMoves[i])
  result = allMoves

proc LK_5Move(c1, c2, c3, c4, c5, c6, c7, c8: City_Number;
              G4a: Length_Gain;
              tourOrderPrev: int): bool =
  var
    ...
    move: PromisingMove
...    
  move.c1 = c1
  move.c2 = c2
  move.c3 = c3
  move.c4 = c4
  move.c5 = c5
  move.c6 = c6
  move.c7 = c7
  move.c8 = c8
...
  block find_promising_moves:
    ...
  #end_block find_promising_moves
    
  block evaluate_promising_moves:
    ...
      if moveType != move_type_0: # connecting move
        gainFromCloseUp = Ga - distance(c10, c1)
        if gainFromCloseUp > 0:
          # improving move found
          improved = true
          Make_5opt_Move(c1, c2, c3, c4, c5, c6, c7, c8, c9, c10,
                         tourOrder)
          tourLen = tourLen - gainFromCloseUp
          Set_DLB_off(DontLook,
                      [c1, c2, c3, c4, c5, c6, c7, c8, c9, c10])
          break evaluate_promising_moves
          
      when true: # not OPT_6_IMPLEMENTED
        move.c9  = c9 
        move.c10 = c10
        move.Ga  = Ga
        move.moveType  = moveType
        move.tourOrder = tourOrder
        AddToPromisingMoves(move)
    #end_loop for mve
  #end_block evaluate_promising_moves
  result = improved

proc LK_1SubsequentMoves():bool =
  var
    improved: bool
    promisingMovesList: seq[PromisingMove]
    breadth: int
    c1, c2, c3, c4, c5, c6, c7, c8, c9, c10:  City_Number
    Ga: Length_Gain
    tourOrder: int
    moveType: int
    searching: bool
    c2subseq, cLast:  City_Number

  improved = false
  block evaluate_promising_moves:
    # here we should try to use general subsequent move
    # after temporary applying 5-opt move
    promisingMovesList = GetAllPromisigMoves()
    breadth = min(len(promisingMovesList), Max_Breadth_K)  ## NOTE
    if breadth == 0:
      break evaluate_promising_moves

    Save_Tour()
    Save_DLB()
    for mve in 0 .. breadth-1:
      c1  = promisingMovesList[mve].c1
      c2  = promisingMovesList[mve].c2
      c3  = promisingMovesList[mve].c3
      c4  = promisingMovesList[mve].c4
      c5  = promisingMovesList[mve].c5
      c6  = promisingMovesList[mve].c6
      c7  = promisingMovesList[mve].c7
      c8  = promisingMovesList[mve].c8
      c9  = promisingMovesList[mve].c9
      c10 = promisingMovesList[mve].c10
      Ga  = promisingMovesList[mve].Ga
      #moveType = promisingMovesList[mve].moveType
      tourOrder = promisingMovesList[mve].tourOrder

      c2subseq = c10
      cLast = c10
      LinksAddedClear()
      AddtoLinksAdded(c2, c3)
      AddtoLinksAdded(c4, c5)
      AddtoLinksAdded(c6, c7)
      AddtoLinksAdded(c8, c9)
      Make_5opt_Move(c1, c2, c3, c4, c5, c6, c7, c8, c9, c10,
                     tourOrder)
      Set_DLB_off(DontLook,
                  [c1, c2, c3, c4, c5, c6, c7, c8, c9, c10])
      searching = true
      SubseqLvl = 0
      while searching:
        improved = LK_Subsequent3Move(c1, c2subseq, Ga, cLast)
        if improved:
          break evaluate_promising_moves
        else:
          if c2subseq == cLast: # end of promising moves
            Restore_Tour()
            Restore_DLB()
            searching = false
          else:
            c2subseq = cLast
        if SubseqLvl >= Max_Depth:
          searching = false
          Restore_Tour()
          Restore_DLB()
    #end_loop log mve
  #end_block evaluate_promising_moves
  result = improved

proc LK_scheme() =
  var
    locallyOptimal: bool = false
    improved: bool
    baseCity: City_Number

  position = Create_Position_In_Tour(tour)
  Set_DLB_off(DontLook, tour)

  while not locallyOptimal:
    locallyOptimal = true
    for baseCity in 0 .. N-1:
      if isDLB_on(DontLook, baseCity):
        continue 

      ClearPromisingMoves()
      # first move:
      improved = LK_1Move(baseCity)
      # subsequent moves:
      if not improved:
        improved = LK_1SubsequentMoves()

      if improved:
        locallyOptimal = false
      else:
        Set_DLB_on(DontLook, baseCity)

    #end_loop for baseCity
  #end_while not locallyOptimal