El algoritmo de backtracking 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 por un solo paso de extensión; las hojas del árbol son las candidatas parciales que no se pueden extender más.
El algoritmo de retroceso atraviesa este árbol de búsqueda recursivamente, desde la raíz hacia abajo, en primer orden de profundidad. En cada nodo c, el algoritmo comprueba si c se puede completar con una solución válida. Si no puede, todo el subárbol enraizado en c se salta (poda). De lo contrario, el algoritmo (1) comprueba si c en sí es una solución válida, y si es así, la informa al usuario; y (2) enumera recursivamente todos los subarboles 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 multiplicado por el costo de obtener y procesar cada nodo. Este hecho debe tenerse en cuenta al elegir el árbol de búsqueda potencial e implementar la prueba de poda.
PseudocodeEdit
Para aplicar el retroceso a una clase específica de problemas, se deben proporcionar los datos P para la instancia particular del problema que se va a resolver, y seis parámetros de procedimiento, raíz, rechazo, aceptación, primero, siguiente y salida. Estos procedimientos deben tomar los datos de instancia P como parámetro y deben hacer lo siguiente:
- root (P): devuelve el candidato parcial en la raíz del árbol de búsqueda.
- reject (P, c): devuelve true solo si no vale la pena completar el candidato parcial c.
- aceptar (P, c): devuelve true si c es una solución de P, y false en caso contrario.
- first (P, c): genera la primera extensión del candidato c.
- next(P,s): genera la siguiente extensión alternativa de un candidato, después de la extensión s.
- output(P,c): usa la solución c de P, según corresponda a la aplicación.
El algoritmo de backtracking reduce el problema a la llamada backtrack (raíz (P)), donde backtrack es el siguiente procedimiento recursivo:
procedure backtrack(c) is if reject(P, c) then return if accept(P, c) then output(P, c) s ← first(P, c) while s ≠ NULL do backtrack(s) s ← next(P, s)
Consideraciones de Usoeditar
El procedimiento de rechazo debe ser una función con valor booleano que devuelve true solo si es seguro que ninguna extensión posible de c es una solución válida para P. Si el procedimiento no puede llegar a una conclusión definitiva, debe devolver false. Un resultado verdadero incorrecto puede hacer que el procedimiento bt pierda algunas soluciones válidas. El procedimiento puede asumir que reject (P,t) devuelve false para cada ancestro t de c en el árbol de búsqueda.
Por otro lado, la eficiencia del algoritmo de retroceso depende de que rechace devuelva true para candidatos que estén lo más cerca posible de la raíz. Si reject siempre devuelve false, el algoritmo aún encontrará todas las soluciones, pero será equivalente a una búsqueda de fuerza bruta.
El procedimiento accept debe devolver true si c es una solución completa y válida para la instancia del problema P, y false en caso contrario. Puede suponer que el candidato parcial c y todos sus ancestros en el árbol han pasado la prueba de rechazo.
El pseudocódigo general anterior no asume que las soluciones válidas sean siempre hojas del árbol de búsqueda potencial. En otras palabras, admite la posibilidad de que una solución válida para P se pueda extender aún más para obtener otras soluciones válidas.
El algoritmo backtracking utiliza el primer y el siguiente procedimiento para enumerar los hijos de un nodo c del árbol, es decir, los candidatos que difieren de c por un solo paso de extensión. La llamada first (P,c) debe dar lugar al primer hijo de c, en algún orden; y la llamada siguiente (P, s) debe devolver al siguiente hermano del nodo s, en ese orden. Ambas funciones deben devolver un candidato «NULO» distintivo, si el hijo solicitado no existe.
Juntas, las funciones raíz, primera y siguiente definen el conjunto de candidatos parciales y el árbol de búsqueda potencial. Deben elegirse para que cada solución de P ocurra en algún lugar del árbol, y ningún candidato parcial ocurra más de una vez. Además, deben admitir un predicado de rechazo eficiente y eficaz.
Variantes de parada tempranaeditar
El pseudo-código anterior llamará a la salida para todos los candidatos que son una solución para la instancia dada P. El algoritmo se puede modificar para detenerse después de encontrar la primera solución, o un número especificado de soluciones; o después de probar un número especificado de candidatos parciales, o después de gastar una cantidad determinada de tiempo de CPU.