Es
un algoritmo general para encontrar todas (o algunas) soluciones
a algunos problemas de cómputo, especialmente los problemas de
satisfacción restringida , que incrementan los candidatos a las soluciones
y abandonan a un candidato ("backtracks") tan pronto como determina
que el candidato no puede Se completará a una solución válida.
El
ejemplo clásico del libro de texto sobre el uso del retroceso es el rompecabezas
de las ocho reinas, que solicita todos los arreglos de ocho reinas de
ajedrez en un tablero de ajedrez estándar para que ninguna
reina ataque a ninguna otra. En el enfoque de retroceso común, los
candidatos parciales son arreglos de k reinas en las primeras k filas
del tablero, todas en diferentes filas y columnas. Cualquier solución
parcial que contenga dos reinas mutuamente atacantes puede ser abandonada.
El
algoritmo de retroceso enumera un conjunto de candidatos parciales que,
en principio, podrían completarse de varias maneras para dar todas
las soluciones posibles al problema dado. La finalización se realiza de
forma incremental, mediante una secuencia de pasos de extensión
candidatos.
Conceptualmente,
los candidatos parciales se representan como los nodos de una estructura
de árbol, el árbol de búsqueda potencial. Cada candidato parcial es
el padre de los candidatos que difieren de él en un solo paso de
extensión; Las hojas del árbol son los candidatos parciales que no se
pueden extender más.
El
algoritmo de retroceso recorre este árbol de búsqueda de forma recursiva,
desde la raíz hacia abajo, en primer orden de profundidad. En cada
nodo c, el algoritmo verifica si c puede completarse para una
solución válida. Si no puede, todo el subárbol enraizado en c se
omite (se recorta). De lo contrario, el algoritmo (1) verifica
si c en sí es una solución válida, y si es así lo informa al
usuario; y (2) enumera recursivamente todos los subárboles de c. Las
dos pruebas y los hijos de cada nodo se definen mediante procedimientos dados
por el usuario.
Por
lo tanto, el árbol de búsqueda real que atraviesa el algoritmo es
solo una parte del árbol potencial. El costo total del algoritmo es el
número de nodos del árbol real por el costo de obtener y procesar cada nodo. Este
hecho debe tenerse en cuenta al elegir el posible árbol de búsqueda e
implementar la prueba de poda.
