Algorithms For Dummies

 

»

Allows use of a pejorative solution for a few times to see whether moving 

away from the local solution can help the search find a better path to the 

best solution.

 

»

Remembers the solutions that the search tries and forbids it from using them 

anymore, thus assuring that the search doesn’t loop between the same 

solutions around the local solution without finding an escape route.

 

»

Creates a long-term or short-term memory of Tabu solutions by modifying the 

length of the queue used to store past solutions. When the queue is full, the 

heuristic drops the oldest Tabu to make space for the new one.

You can relate Tabu Search to caching and memoization (see Chapter 16) because 

it requires the algorithm to track its steps to save time and avoid retracing previ-

ously used solutions. In the TSP, it can help when you try optimizing your solution 

by swapping the visit order of two or more cities by avoiding repeat solution sets.