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