Saturday, March 18, 2017

2-opt with DLB

type
  DLB_Array = array [City_Number, bool]
  Orientation = enum forward, backward
proc isDLB_on(DontLook: DLB_Array,
              city: City_Number): bool =
  return DontLook[city]

proc Set_DLB_on(DontLook: var DLB_Array,
                city: City_Number) =
  DontLook[city] = true

proc Set_DLB_off(DontLook: var DLB_Array,
                 city: City_Number) =
  DontLook[city] = false

proc Set_DLB_off(DontLook: var DLB_Array,
                 cities: openArray[City_Number]) =
  # turns off DLB for given cities
  for city in 0 .. len(cities)-1:
    DontLook[cities[city]] = false
proc One_City_2_Opt_DLB(tour: var Tour_Array,
                        basePos: Tour_Index,
                        DontLook: var DLB_Array): bool =
  var
    improved: bool
    i, j: Tour_Index
    X1, X2, Y1, Y2: City_Number

  improved = false
  block two_loops:
    for direction in [forward, backward]:  # NOTE: both tour neighbors
      # consider link between t[i] and t[i+1],
      # then between t[i-1] and t[i]
      if direction == forward:
        i  = basePos
      else:
        i  = (N + basePos - 1) mod N
      X1 = tour[i]
      X2 = tour[(i+1) mod N]

      for counter_2 in 0 .. N-1:
        j = counter_2
        Y1 = tour[j]
        Y2 = tour[(j+1) mod N]

        if (X1 == Y1) or (X2 == Y1) or (Y2 == X1):
          continue

        if Gain_From_2_Opt(X1, X2, Y1, Y2) > 0:
          Set_DLB_off(DontLook, [X1, X2, Y1, Y2])
          Make_2_Opt_Move(tour, i, j)
          improved = true
          break two_loops
  result = improved
proc LS_2_Opt_DLB(tour: var Tour_Array) =
  ## Optimizes the given tour using 2-opt with Don't Look Bits (DLB)
  var
    locallyOptimal: bool = false
    improved: bool
    DontLook: DLB_Array
    baseCity: City_Number

  Set_DLB_off(DontLook, tour)

  while not locallyOptimal:
    locallyOptimal = true
    for basePos in 0 .. N-1:
      baseCity = tour[basePos]
      if isDLB_on(DontLook, baseCity):
        continue
      improved = One_City_2_Opt_DLB(tour, basePos, DontLook)
      if not improved:
        Set_DLB_on(DontLook, baseCity)
      else:
        locallyOptimal = false

No comments:

Post a Comment