El lobo, la cabra y la col

Leyendo el otro día la entrada en Microsiervos que citaba la magnífica explicación de Jesús León del problema de Los puentes de Königsberg vino, no sé por qué extraña razón a mi mente, un viejo problema de mi época de estudiante. En concreto era un problema de Inteligencia Artificial sobre resolución de problemas y espacios de búsqueda: El lobo, la cabra y la col. Os transcribo el enunciado del mismo:

Un granjero se encuentra en la orilla de un río junto con un lobo, una cabra y una col. Ademśa dispone de un bote en el que sólo puede transportar una única cosa cada vez. El granjero pretende transportar al lobo, la cabra y la col al otro lado del río utilizando el bote. Sin embargo, debe tener cuidado y no dejar solos en una orilla al lobo y a la cabra porque el lobo se comería a la cabra. Tampoco puede dejar la cabra y la col porque la cabra se comería la col. ¿Cómo conseguiría el granjero trasladar todo a la margen derecha del río?

Este problema que se resuelve fácilmente invirtiendo un ratillo de pensada, nos sirve para explicar métodos de representación de espacios de búsqueda. Para ello utilizaremos el paradigma del espacio de estados que consiste en representar la situación actual de problema en estados.

Sobre el ejemplo presentado, fijaremos primeramente un operador de transición del estado. Representaremos con un tupla los elementos que se transportan en el bote en cada viaje (ida, vuelta). Denominaremos al Lobo con una L, a la cabra con una C y a la col con una X. Debemos de fijar también un estado inicial que en nuestro problema será el listado de los elementos que tengamos en la margen derecha del río (). Y el estado final al que queremos llegar que será (L,C,X), Resumiendo:

Operador: (ida, vuelta) elementos que se transportan en el bote
Estado inicial: () -vacío-
Estado final: (L,C,X)

Asumimos como premisa inicial que si el granjero está en medio de los tres elementos estos no interactúan entre sí, es decir el lobo no se come a la cabra si el pastor está en esa orilla y lo mismo con la cabra y la col.

A continuación se dibuja el espacio de búsqueda de soluciones (perdón por la precariedad):

Los nodos del árbol del espacio de soluciones representan diversos estados del problema. Las líneas que unen los nodos representan los operadores, es decir el viaje del bote.

Como vemos la solución viene dada por 4 viajes (ida y vuelta), hasta llegar al estado final (L,C,X). Por supuesto un ordenador o un procesador no llega directamente a esa solución sino que irá construyendo el espacio de búsqueda según el algoritmo que elijamos. El método que elijamos será el que determine la eficiencia en encontrar la solución. Por ejemplo, no es lo mismo ir construyendo el espacio de búsqueda en profundidad que en anchura… pero los algoritmos ya son otro cantar…

Os dejo un enlace por si queréis probar de manera interactiva a resolverlo.

Technorati Tags: espacio de soluciones, algoritmia, problema,
Site Search Tags: espacio de soluciones, algoritmia, problema,