Busqueda de coste uniforme y las damas

Algoritmos de búsqueda de coste uniforme

Figura 1:Grafo ponderado dirigido

Este tipo de algoritmos suelen usarse en problemas donde el objetivo es encontrar un camino que minimice o maximice alguna propiedad del sistema estudiado. Para que puedan aplicarse el sistema debe poder modelarse mediante un árbol o un grafo ponderado, de forma que la magnitud de la propiedad estudiada sea función de los nodos recorridos.

Un ejemplo de este tipo es el mostrado en la figura 1. Supongamos que se quiere determinar el camino que permite llegar desde el nodo 1 al 6 minimizando el  atributo "valor". Este atributo se incrementa en la cantidad indicada por la etiqueta de cada arista, por lo que en función del camino seguido para llegar hasta el nodo 6 determina su valor. 

Para solucionar este problema se puede usar un algoritmo de búsqueda uniforme. Para ello se necesitarán como poco las siguientes estructuras de datos:

1. Una clase nodo con un atributo que sea una referencia al nodo "progenitor".
2. Una colección de nodos aun no visitados , o de nodos visitados (visitados), según el enfoque.
3. Una lista de nodos (por_visitar) ordenada de mejor a peor opción según su aporte a la propiedad a optimizar. Si se quiere minimizar estarán primero los que produzcan un menor incremento.

En el siguiente esquema se muestran los pasos básicos que siguen este tipo de algoritmos.

Figura 2: esquema general de los algoritmos de búsqueda de coste uniforme.

Si se aplica este algoritmo para llegar al nodo 6 de la figura 1 con el menor valor posible se obtiene lo siguiente:

1. Se comprueba si nodo 1 es solución, como no lo es se obtienen los hijos que aún no han sido visitados (nodos 2,3 y 6) y se añaden a la lista por_visitar, donde los nodos se posicionan en orden creciente respecto del atributo valor. Nodo 1 se almacena en visitados.
2. Se saca el primer nodo de la lista por_visitar (nodo 3) y se comprueba si es solución, como no lo es se obtienen sus hijos que aún no han sido visitados (nodo 5) y se añaden a la lista por_visitar. Como tiene igual valor que el nodo 2 pero es el último que se ha añadido entrará a la primera posición. Nodo 3 se almacena en visitados.
3. Se saca el primer nodo de la lista por_visitar (nodo 5) y se comprueba si es solución, como no lo es se obtienen sus hijos aún no visitados (nodo 6) y se añaden a la lista por_visitar. Como nodo 6 tiene valor 4 entrará en la segunda posición de la lista. Nodo 5 se almacena en visitados.
4. Se saca el primer nodo de la lista por_visitar (nodo 2) y se comprueba si es solución, como no lo es se obtienen sus hijos aún no visitados (nodo 4) y se añaden a la lista por_visitar a la posición que le corresponda. Nodo 2 se almacena en visitados.
5. Se saca el primer nodo de la lista por_visitar (nodo 6) y como es solución es devuelto.

Para obtener la ruta de mínimo coste a partir del nodo solución es muy fácil, solo se debe consultar de que nodo procede hasta llegar al nodo de partida.

Como la lista de nodos por visitar se ordena de manera que los nodos más prometedores salen primero se sabe que cuando se llegue a una solución será óptima, por lo que no es necesario comprobar las demás rutas.

Ejemplo de las damas

Figura 3: ejemplo de recorrido óptimo.

A continuación se va a exponer una adaptación de este tipo de algoritmos para la obtención del recorrido que permite llegar al lado rival del tablero con el menor número posible de movimientos, suponiendo que todas las fichas menos la que se mueve permanecerán estáticas.

Las reglas del juego son:

1. No está permitido retroceder.
2. No puede haber dos fichas ocupando la misma casilla.
3. El movimiento normal es de una casilla en diagonal a derecha o izquierda.
4. Si hay una casilla contraria en una casilla adyacente en diagonal derecha o izquierda se puede saltar sobre esta hasta la casilla adyacente, pudiéndose enlazar tantos saltos como sea posible en un solo movimiento.
5. No se puede saltar sobre fichas propias.

En la figura se muestra un ejemplo de recorrido óptimo, los números indican el turno en que se  hace el movimiento, las fichas azules son las propias y las verdes las del rival.
En la figura 4 se muestra el esquema UML de las clases utilizadas para resolver el problema, se han puesto muchos comentarios para facilitar la comprensión.

Figura 4. Esquema UML de las clases usadas para resolver el problema de las damas.

En las figuras 5 y 6 se muestran los diagramas de flujo de los métodos calcularRuta y mueve, que son los que implementan el algoritmo de búsqueda uniforme.

Figura 5. Diagrama de flujo del método calcularRuta

Figura 6. Diagrama de flujo del método mueve.

Dada la extensión del código necesario para implementar lo expuesto he preferido colgar un proyecto Java  en NetBeans (comprimido), que resuelve el ejemplo en este enlace , se incluyen casos de prueba.