Quizás la estructura de memoria más importante usada para determinar las soluciones permitidas a un
En su forma más simple, una lista tabú es una memoria de corto plazo que contiene las soluciones que fueron visitadas en el pasado reciente (menos de
es el número de soluciones previas que van a ser almacenadas (
Una variación de la lista tabú prohíbe soluciones que tienen ciertos atributos (i.e., soluciones al problema del viajante de comercio (TSP) que incluyen aristas no deseadas) o prevenir ciertos movimientos (i.e., un arco que fue agregado a un recorrido del TSP no puede ser eliminado en los siguientes
Los atributos seleccionados de las soluciones recientemente visitadas son denominados "tabú-activos."
Las posibles soluciones que contengan elementos tabú-activos son "tabú".
El problema del viajante (TSP), es comúnmente utilizado para mostrar la funcionalidad de la búsqueda tabú.
El TSP requiere buscar un orden en el cual viajar entre ciudades, tal que la distancia recorrida sea minimizada.
Por ejemplo, si las ciudades A y B están una al lado de la otra, mientras que la ciudad C está más lejos, la distancia total recorrida será más corta si las ciudades A y B son visitadas una después de la otra, antes de visitar C. Como encontrar un orden óptimo para visitar las ciudades en el TSP es un problema NP-difícil.
los métodos de aproximación basados en heurísticas son útiles para lograr la optimalidad.
Primero, la búsqueda tabú comienza con una solución inicial, que puede ser generada con el algoritmo del vecino más cercano.
Para crear nuevas soluciones, el orden en que dos ciudades son visitadas es intercambiado.
La distancia total recorrida entre todas las ciudades es utilizada para juzgar cuánto mejor es una solución que otra.
Para prevenir ciclos y para salir de los óptimos locales, una solución es agregada a la lista tabú si es que es aceptada en N*(x), el vecindario de soluciones.