Backtracking (Vuelta atrás)

Técnicas de diseño
de algoritmos

Vuelta atrás
(Backtracking)

Definición


El NIST (National Institute of Standards and
Technology) lo define en su Diccionario de
Algoritmos yEstructuras de Datos de la
siguiente manera:

“Encontrar una solución intentándolo con una
de varias opciones. Si la elección es incorrecta,
el cómputo retrocede o vuelve a comenzar
desde el punto dedecisión anterior y lo intenta
con otra opción.”[1]

 En

su forma básica, la idea del algoritmo vuelta
atrás se asemeja a un recorrido en profundidad
dentro de un grafo dirigido. El grafo encuestió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.Origen
 El

término fue acuñado por el
matemático D.H. Lehmer e la década de
los cincuenta y formalizado por Walker,
Golom y Baumert en el siguiente decenio.
 Un lenguaje creado en 1962,SNOBOL, fue
el primero en tener esta estrategia en su
repertorio de herramientas.

Características









Construye soluciones parciales.
El recorrido tiene éxito si se puededefinir por
completo una solución, en este caso el algoritmo
puede detenerse o seguir buscando soluciones
alternativas.
Encontrar la mejor combinación posible, de ahí que
se diga que es unabúsqueda en profundidad.
Está muy relacionado con la búsqueda
combinatoria.
Genera todas las secuencias de forma sistemática y
organizada.
Se usan llamadas a funciones recursivas.

 Elalgoritmo básico de vuelta atrás es el siguiente:
1)

2)

Tomar una opción de entre las posibles.

Para cada elección, considerar toda opción
posible recursivamente.
3)

Devolver la mejor soluciónencontrada

Funcionamiento
Función Backtracking (Etapa i) devuelve: boolean
Inicio
Éxito = falso;
IniciarOpciones(i, GrupoOpciones o);
Repetir
SeleccionarnuevaOpcion(o, Opcion n);
Si...