BACKTRACKING: EJEMPLOS

Bibliografía: - Fundamentals of Computers Algorithms, Horowitz - Sahni. - Estructuras de Datos y Algoritmos, Aho - Hopcroft - Ullman. - Algorithms in C, Sedgewick.

EJEMPLO 1:

Un problema clásico es el problema del viajante: dadas n ciudades conectadas todas con todas, “encontrar el camino que recorra todas las ciudades con mínimo costo”.
Se parte de una ciudad cualquiera, y se obtiene el siguiente espacio de soluciones:

(1)

(1,2) (1,3) ....... (1,n)

(1,2,3) (1,2,n) .......... (1,n,2) ...... ..................

(1,2,3,4,...,n) En este nivel se tienen …ver más…

Los jugadores alternan sus movimientos, y el estado del juego puede ser representado por la posición del tablero. Se asume que hay un número finito de posiciones en el tablero y que el juego tiene alguna regla que asegure su terminación. Con cada juego asociamos un árbol llamado árbol del juego. Cada nodo en el árbol representa una posición en el tablero. A la raíz le asociamos la posición de comienzo. Si la posición x está asociada con el nodo n, luego los hijos de n corresponden al conjunto de movidas permitidas desde la posición x, y con cada hijo es asociada la posición del tablero resultante. Por ejemplo la siguiente figura muestra parte del árbol del ta-te-ti:

juega A

... . . . . . .

juega A

juega B

juega A

Las hojas de un árbol de juego corresponden a las posiciones del tablero donde no hay mas movimientos, porque uno de los jugadores ha ganado o todos los casilleros están llenos y a ocurrido un empate. Se asocia un valor a cada nodo del árbol. Primero se asignan valores a las hojas planteado desde el punto de vista de uno de los jugadores, tomemos A. Los valores serán -1, 0 o 1, si A pierde, gana o empata respectivamente. Los valores se propagan hacia arriba en el árbol de acuerdo a la siguiente regla:
Si un nodo corresponde a la posición del tablero donde le toca jugar a A, luego el valor con el que se rotura este nodo es el máximo de los valores