Problema: Acertijo del lobo, la cabra y la col

Acertijo.
Hace mucho tiempo un granjero fue al mercado y compró un lobo, una cabra y una col. Para volver a su casa tenía que cruzar un río. El agricultor dispone de una barca para cruzar a la otra orilla, pero en la barca solo caben él y una de sus compras.

Si el lobo se queda solo con la cabra se la come, si la cabra se queda sola con la col se la come.

El reto del granjero era cruzar él mismo y dejar sus compras a la otra orilla del río, dejando cada compra intacta. ¿Cómo lo hizo?

Resolución del problema en el espacio de estados         
v  Espacio de estados: granjero, cabra, lobo, col; izquierda y derecha.

Numero de estados: 13

v  Estado inicial : izquierda

v  Estado final (único) : pasar todos a  la derecha

v  Operadores :

·         Pasa el granjero solo

·         Pasa el granjero con el lobo

·         Pasa el granjero con la cabra

·         Pasa el granjero con la col

v  Solución :

Ø    Deja a la cabra al otro lado

Ø  Vuelve

Ø  Deja al lobo en el otro lado

Ø  Regresa con la cabra

Ø  Deja la col o al lobo en el otro lado

Ø  Vuelve

Ø  Deja la cabra al otro lado

Generación de espacios de estados.

G

D   Donde  B,C,D,E son las 4 grandes transiciones, pero la que sola sirve para la solución del acertijo es la C por eso de ahí nacen los siguiente sucesores.



Algoritmo en pseudocódigo:

• Algoritmo: Busqueda General
• Est_abiertos.insertar(Estado inicial)
• Actual← Est_abiertos.primero()
• mientras no es_final?(Actual) y no Est_abiertos.vacia?() hacer
• Est_abiertos.borrar_primero()
• Est_cerrados.insertar(Actual)
• Hijos ← generar_sucesores(Actual)
• Hijos ← tratar_repetidos(Hijos, Est_cerrados, Est_abiertos)
• Est_abiertos.insertar(Hijos)
• Actual ← Est_abiertos.primero()
• fin

Búsqueda en Anchura

  

• Los nodos se visitan y generan por niveles
• La estructura para los nodos abiertos es una cola (FIFO)
• Un nodo es visitado cuando todos los nodos de los niveles superiores y sus hermanos precedentes han sido visitados

Búsqueda en Profundidad

• Los nodos se visitan y generan buscando los nodos a mayor profundidad y retrocediendo cuando no se encuentran nodos sucesores
• La estructura para los nodos abiertos es una pila (LIFO)
• Para garantizar que el algoritmo acaba debe imponerse un límite en la profundidad de exploración

Adjunto Algoritmos de Búsqueda Anchura y Profundidad