R2D2 contra las reinas caníbales y la ciudades de nombres raros.

Lo sé, el título esta medio bizarro, pero de lo que hablaremos aquí es resolver problemas de búsqueda en un árbol. Como ya sabrán los instruidos en el tema los clásicos problemas de ejemplo son:las ciudades (buscar un camino de 'x' ciudad a 'y' ciudad), los caníbales (3 caníbales, 3 misioneros, una lancha, 2 mujeres y un camino), las 8 reinas (reinas neuróticas que no se pueden ver ni en diagonal).

El problema que nos gustaría abordar es el de los caníbales, el problema completo es masomenos algo así:

En una apartada orilla del planeta Rigel VII existe un hermoso río cuántico cuyo brioso caudal no puede ser atravesado a menos que se haga uso de una lancha. En la orilla derecha del río hay 3 caníbales y 3 misioneros que necesitan cruzar al otro lado. Sólo que hay condiciones para que esto se pueda lograr, en la lancha antes mencionada sólo caben una o dos personas y para cruzarla de lado a lado forzosamente alguien debe de conducirla, al mismo tiempo de que si en cualquier lado hay más caníbales que misioneros, éstos ultimos serán cruelmente devorados.
Usted es mediador de la guerra intergaláctica de los caníbales Rigelianos y los Misioneros de Marte, debe de transportar hacia la embajada de las Galaxias Unidas en el lado izquierdo del río a todos los individuos sin causar ningún incidente político que desate la peor de las guerras de la galaxia, pero no está solo, oh no, tiene el poder de la programación y los algoritmos de búsqueda de su lado. Así que, ¡manos a la obra!

Tan simpatico que se ve

El primer paso para una misión exitosa, antes de abordar el algoritmo de búsqueda es la definición formal del problema, aquí yacen los cimientos de lo que será la resolución.


Primero se tienen que definir cuatro cosas:
-Un estado válido del problema.
-Operadores que marcan un cambio de estado.
-El estado inicial del problema.
-El estado objetivo del problema (a dónde queremos llegar).



Estado válido del problema.
Un estado válido es aquél que refleja la situación actual del problema, en éste caso debe definir la cantidad de caníbales y misioneros en cada lado así como la posición de la lancha, o en que orilla está. Esto lo podemos definir con:

# caníbales orilla izquierda
# caníbales orilla derecha
# misioneros orilla izquierda
# misioneros orilla derechaposición de la lancha

Como sabemos la cantidad total de caníbales y misioneros, que no varía, podemos obviar una orilla y remitirnos a simples restas para calcular la otra orilla y entonces el estado válido se resume a:
# caníbales
# misioneros
# lanchas en un lado


Operadores.
Dado el estado que definimos los posibles operadores que hacen un cambio de estado son:

-movimiento de lancha con un misionero
-movimiento de lancha con un caníbal-movimiento de lancha con dos misioneros
-movimiento de lancha con dos caníbales
-movimiento de lancha con un caníbal y un misionero


Estado inicial.
El estado incial es:
(1,3,3)

Donde 1 indica que en el lado presente está la lancha (derecho, si fuse un 0 la lancha estáen el lado ziquierdo), el primer 3 indica que hay 3 caníbalesen el lado derecho y el segundo 3 que hay 3 misioneros. (Si queremos saber cuántos caníbales o misioneros hay en el lado izquierdo simplemente hacemos la operación aritmética de resta para saberlo, dado que sabe que siempre existen 3 misioneros y 3 caníbales).


Estado Objetivo.

(0,0,0)

Dado que aquí la lancha está del otro lado, no hay caníbales ni misioneros en el lado derecho(todos están en el izquierdo).

BÚSQUEDA.

Ya que hemos definido formalmente el problema solo basta seguir este pseudo-algoritmo para encontrar la solución. Nótese que este algoritmo es capaz de resolver cualquier problema similar (8 reinas, ciudades,etc) siempre y cuando la definicion formal del problema sea correcta.
Además, mientras mas detalles tenga la formalizacion de los estados, la obtención de la busqueda sera mas facil, pero hayq ue observar un equilibrio pues estados muy grandes podrian agotar los recursos.


Algoritmo de búsqueda.

1.- Generar cola de Estados.
2.- Meter raíz (Estado inicial) en cola.
3.- Ciclo.
3.1.- Visitar siguiente Estado en la cola.
3.1.1.- Sacar el nodo de la cola.
3.1.2.- Prueba de objetivo.
Si el nodo es objetivo, regresar solucion.
Si no:
Generar todos los nodos hijos del nodo actual.
Meter hijos a la cola.
3.1.3.- Regresar a 3.


Este algoritmo no es el unico que existe, en la siguiente entrada se cubriran distintos tipos de algoritmos, sus características y definiciones.




Enhorabuena, hemos salvado la galaxia una vez mas ;)

Tuuutututututtutururrurtuuuuuuu (musiquilla triunfal)