Wednesday, December 6, 2017

Scheme of LK with non-sequential moves

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

  position = Create_Position_In_Tour(tour)
  Set_DLB_off(DontLook, tour)  
  # calculate initial length of tour
  tourLen = distance(tour[N-1], tour[0])
  for pos in 0 .. N-2:
    tourLen = tourLen + distance(tour[pos], tour[pos+1])

  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()
      # non-sequential moves:
      if not improved:
        improved = LK_1NS_Move(baseCity)

      if improved:
        locallyOptimal = false
      else:
        Set_DLB_on(DontLook, baseCity)
      tourLenArr[baseCity] = tourLen

    #end_loop for baseCity
  #end_while not locallyOptimal

No comments:

Post a Comment