Arbol de Búsqueda
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.
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:
Los
parámetros son el nodo actual y, posiblemente, todas las decisiones anteriores
tomadas
La
función hace múltiples llamadas a si misma (si fuera una sóla, el algoritmo
sería voraz). La
función incluye una condición donde se prueba si desde este nodo podríamos
llegar a una solución legal (según las restricciones del problema)
Si
no se puede llegar a una solución legal, se acota la búsqueda y se termina la
llamada recursiva (dando vuelta atrás al nodo anterior)
Un
algoritmo por fuerza bruta se puede ver como un caso particular de un algoritmo
de backtracking donde se omiten los últimos dos componentes.
Enrique Rodriguez
No comments:
Post a Comment