2-opt with Neighbor Lists and Best from given City – alternative

Note

This example of code does not contain any new ideas and can be skipped by a reader.

proc One_City_2_Opt_N_Best_From_City(tour: var Tour_Array;
                                     basePos: Tour_Index;
                                     neighbor: Neighbor_Matrix;
                                     position: var City_Position_In_Tour;
                                     numberOfNeigbors: int): bool =
  ## Makes the best of improving moves starting from given city
  type
    Move2 = object
      i, j: Tour_Index
      gain: Length_Gain
  var
    improved: bool
    i, i_pred, i_succ, j, j_pred, j_succ: Tour_Index
    X0, X0_pred, X0_succ, Y0, Y0_pred, Y0_succ: City_Number
    gainExpected: Length_Gain
    bestMove: Move2

  improved = false
  bestMove.gain = 0
  
  i   = basePos
  X0  = tour[i]
  i_pred = (N + i - 1) mod N
  i_succ = (i + 1) mod N
  X0_pred = tour[i_pred]
  X0_succ = tour[i_succ]

  for neighbor_number in 0 .. numberOfNeigbors-1:
    Y0 = neighbor[X0][neighbor_number]    
    j  = position[Y0]
    j_pred = (N + j - 1) mod N
    j_succ = (j + 1) mod N
    Y0_pred = tour[j_pred]
    Y0_succ = tour[j_succ]

    if (X0_succ != Y0) and (Y0_succ != X0):
      gainExpected  = Gain_From_2_Opt(X0, X0_succ, Y0, Y0_succ)
      if gainExpected > bestMove.gain:
        bestMove = Move2(i: i,  j: j,  gain: gainExpected)
        improved = true
    if (X0_pred != Y0) and (Y0_pred != X0):
      gainExpected = Gain_From_2_Opt(X0_pred, X0, Y0_pred, Y0)
      if gainExpected > bestMove.gain:
        bestMove = Move2(i: i_pred,  j: j_pred,  gain: gainExpected)
        improved = true
  if improved:
    Make_2_Opt_Move(tour, bestMove.i, bestMove.j, position)
  result = improved