Vuelta atrás

Vuelta atrás (Backtracking) es una estrategia para encontrar soluciones a problemas que satisfacen restricciones. El término "backtrack" fue acuñado por primera vez por el matemático estadounidense D. H. Lehmer en la década de 1950.

Ejemplo de árbol de búsqueda. Nótese que el árbol no tiene por qué ser binario.

Concepto

En su forma básica, la idea de backtracking se asemeja a un recorrido en profundidad dentro de un grafo dirigido. El grafo en cuestión suele ser un árbol, o por lo menos no contiene ciclos. Sea cual sea su estructura, existe sólo implícitamente. El objetivo del recorrido es encontrar soluciones para algún problema. Esto se consigue construyendo soluciones parciales a medida que progresa el recorrido; estas soluciones parciales limitan las regiones en las que puede encontrar una solución completa. El recorrido tiene éxito si, procediendo de esta forma, se puede definir por completo una solución. En este caso el algoritmo puede, o bien detenerse (si lo único que se necesita es una solución del problema) o bien seguir buscando soluciones alternativas (si deseamos examinarlas todas). Por otra parte, el recorrido no tiene éxito si en alguna etapa la solución parcial construida hasta el momento no se puede completar. En tal caso, el recorrido vuelve atrás exactamente igual que en un recorrido en profundidad, eliminando sobre la marcha los elementos que se hubieran añadido en cada fase. Cuando vuelve a un nodo que tiene uno o más vecinos sin explorar, prosigue el recorrido de una solución.

Algoritmo de Backtracking
proc Backtracking (↕X[1 . . . i ]: TSolución, ↑ok: B)
                        variables L: ListaComponentes
                        inicio
                           si EsSolución (X) entonces
                              ok   CIERTO
                           de lo contrario
                              ok   FALSO
                              L=Candidatos (X)
                              mientras ¬ok ^ ¬Vacía (L) hacer
                                 X[i + 1]   Cabeza (L); L   Resto (L)
                                 Backtracking (X, ok)
                              fin mientras
                            fin si
                        fin

Podemos visualizar el funcionamiento de una técnica de backtracking como la exploración en profundidad de un grafo.

Cada vértice del grafo es un posible estado de la solución del problema. Cada arco del grafo representa la transición entre dos estados de la solución (i.e., la toma de una decisión).

Típicamente el tamaño de este grafo será inmenso, por lo que no existirá de manera explícita. En cada momento sólo tenemos en una estructura los nodos que van desde el estado inicial al estado actual. Si cada secuencia de decisiones distinta da lugar a un estado diferente, el grafo es un árbol (el árbol de estados).

Other Languages
čeština: Backtracking
Deutsch: Backtracking
English: Backtracking
français: Retour sur trace
italiano: Backtracking
한국어: 퇴각검색
Nederlands: Backtracking
norsk bokmål: Tilbakesporing
português: Backtracking
română: Backtracking
српски / srpski: Бектрекинг
українська: Пошук з вертанням
中文: 回溯法