Backtracking

Muchos problemas se pueden modelar como una secuencia de decisiones. Podemos representar este tipo de problemas con un árbol, donde la raíz es la situación inicial y cada arista corresponde a una decisión.

Por ejemplo, considera el problema de formar palabras a partir de letras. Podemos modelar este problema por una secuencia de decisiones, donde cada decisión corresponde a seleccionar la siguiente letra. Para poder ilustrar el correspondiente árbol sólo consideraremos cuatro letras: a, e, r y s.

árbol de búsqueda

A continuación se describen tres clases de algoritmos para resolver problemas de este tipo. El algoritmo más apropiado en cada caso depende del problema en concreto por resolver.

Algoritmos voraces

Un algoritmo voraz (o "greedy" en inglés) siempre toma la decisión más prometedora, ignorando todas las otras posibles decisiones. Por ejemplo, considera el problema de formar la palabra más larga cuyas letras están en orden lexicográfico. Podemos resolver este problema siempre escogiendo la siguiente letra más pequeña: primero escogemos la a, después la e, etc. Esta estrategia corresponde al siguiente camino (marcado en rojo) del árbol:

solución voraz

La principal ventaja de un algoritmo voraz es el tiempo de ejecución: al tomar siempre la decisión más prometedora, la complejidad es lineal en el número total de decisiones. La desventaja es que muchos problemas no se pueden resolver de manera óptima siempre considerando la mejor decisión.

Fuerza bruta

Un algoritmo por fuerza bruta, en cambio, considera todas las posibles combinaciones de tomar decisiones. Por ejemplo, considera el problema de imprimir por pantalla todas las palabras de longitud menor o igual a 10 que se pueden formar por las cuatro letras. (En este problema ignoramos si una palabra existe en el diccionario o no, por lo que todas las palabras son válidas, como por ejemplo "aaaers".) La única manera de resolver este problema es pasar por todo el árbol de profundidad 10.

La ventaja de un algoritmo por fuerza bruta es que siempre procesa todas las posibles soluciones por lo que siempre encontrará la solución óptima. La desventaja es que el algoritmo es lento: con M posibles decisiones y N decisiones por tomar, la complejidad es MN, o sea exponencial en N.

Backtracking

Un algoritmo de backtracking representa un punto intermedio entre un algoritmo voraz y un algoritmo por fuerza bruta. Es decir, no sólo considera una sóla manera de tomar decisiones, pero tampoco considera todas las posibles combinaciones de tomar decisiones.

Por ejemplo, considera el problema de imprimir por pantalla todas las palabras de longitud menor o igual a 10 que se pueden formar por las cuatro letras, con la siguiente restricción: no podría haber ni dos consonantes ni dos vocales seguidos. Es decir, después de cada consonante debería haber un vocal, y después de cada vocal un consonante.

Debido a esta restricción adicional, podemos descartar algunas de las alternativas en el momento de tomar una decisión. Por ejemplo, si primero hemos escogido la letra a, la siguiente decisión no podría ser ni a ni e. De este modo podemos acotar la búsqueda de soluciones, ya que nunca exploraremos los nodos descendentes de estos nodos. En la siguiente figura están tachados todos los nodos que llevarían a una palabra inválida.

solución de backtracking

Implementar un algoritmo de backtracking

Tal y como indica el nombre, un algoritmo de backtracking da "vuelta atrás" cuando se encuentra en un camino sin salida. La manera más fácil de implementar este comportamiento es por recursividad. Al finalizar una llamada recursiva, ya nos encontramos de vuelta en el nodo anterior, por lo que podemos directamente probar una decisión diferente sin tener que buscar explícitamente el último punto donde hemos tomado una decisión.

Normalmente un algoritmo de backtracking se implementa por medio de una función recursiva con los siguientes componentes:

Un algoritmo por fuerza bruta se puede ver como un caso particular de un algoritmo de backtracking donde se omiten los últimos dos componentes.

Ejemplos de código

Algoritmo voraz: greedy.cpp
Algoritmo por fuerza bruta: fuerzabruta.cpp
Algoritmo de backtracking: backtrack.cpp

Problemas para resolver esta semana:

Sencillos:

UVa logo 167 - The Sultan's Successors
UVa logo 729 - The Hamming Distance Problem
UVa logo 750 - 8 Queens Chess Problem
OIE logo Ceros y unos
OIE logo Cortar a tiempo
OIE logo Consonantes y vocales
OIE logo Torres pacíficas

Avanzados:

UVa logo 331 - Mapping the Swaps
UVa logo 10094 - Place the Guards
UVa logo 10950 - Bad Code
OIE logo Puzzle genético
OIE logo Sudoku!
OIE logo Tabla de Fútbol