Monday, April 17, 2017

Alternative for DLB

Instead of don't look bits speedup we can use an array indexed by city numbers, in which each element contains length of tour after improving from given city. The algorithm using has the following scheme:

var
    tourLen: tourLen  # current length of tour
    tourLenArr: array[City_Number, tourLen]

  # 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])

  # initialise array of tour lengths with some arbitrary
  # value different from current value of 'tourLen'
  for city in 0 .. N-1:
    tourLenArr[city] = 1 # 

  # main loop
  for pos in 0 .. N-1:
    baseCity = tour[pos]
    if (tourLen == tourLenArr[baseCity]):
       continue

    improved = Improve(baseCity)  # MUST update 'tourLen' value!

    tourLenArr[baseCity] = tourLen
  #end_for

No comments:

Post a Comment