jueves, 19 de mayo de 2016

Implementación del problema del granjero

Este acertijo es un forma parte de los denominados “puzzles de cruzar el río”, en los que el objetivo es mover una serie de objetos al otro lado del río siguiendo una serie de normas.
La aparición más temprana de este problema es en el manuscrito medieval Propositiones ad Acuendos Juvenes, los tres objetos son un lobo, una cabra y una col. Existen variaciones de este acertijo siendo los objetos una cabra, una oveja y un repollo; un zorro, una gallina y unas semillas; Un zorro, un ganso y una mazorca de maíz y una pantera, un cerdo y unas gachas.La lógica del acertijo sigue siendo la misma.
Este acertijo era uno de los favoritos de Lewis Carroll, y ha sido incluido en varios libros de matemática recreativa.


Planteamiento del problema:

Un granjero fue al mercado y compró un zorro una gallina y un maíz. Para volver a su casa tenía que cruzar un río. El granjero dispone de una barca para cruzar a la otra orilla, pero en la barca solo caben él y una de sus compras. Además, si el lobo se queda solo con la gallina se la come y si la gallina se queda sola con el maíz 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?

Solución Teórica:

El primer paso el llevar la gallina a través del río, ya que de otro modo la gallina o el maíz serían devoradas. Cuando el granjero vuelve a la orilla original, puede elegir entre llevar al zorro o al maíz al otro lado. Si lleva al lobo, deben volver luego para llevar la al maíz, entonces el lobo se comería a la gallina. Si lleva al maíz al otro lado, necesitará volver para coger al zorro, entonces la gallina sería comida. Aquí se encuentra el dilema, se resuelve llevando el zorro (o el maíz) en la barca y trayendo de vuelta a la gallina. Ahora podemos llevar la el maíz (o el zorro), dejando la gallina y, finalmente, volver a buscar la gallina.
  • La solución se resume de la siguiente manera:
  • Deja a la gallina al otro lado
  • Vuelve
  • Deja al zorro en el otro lado
  • Regresa con la gallina
  • Deja el maíz en el otro lado
  • Vuelve
  • Deja la gallina al otro lado
De modo, que hay siete pasos: cuatro hacia la derecha y tres hacia la izquierda.

Implementación:


%accion(estado(Gra,Zorro,Gall,Maiz),estado(1,Z,1,M)).

estadoMalo(estado(0,1,1,_)).
estadoMalo(estado(0,_,1,1)).
estadoMalo(estado(1,0,0,_)).
estadoMalo(estado(1,_,0,0)).

accion(estado(0,0,G,M), estado(1,1,G,M), 'Llevar al zorro').
accion(estado(1,1,G,M), estado(0,0,G,M), 'Traer al zorro').
accion(estado(0,Z,0,M), estado(1,Z,1,M), 'Llevar la gallina').
accion(estado(1,Z,1,M), estado(0,Z,0,M), 'Traer la gallina').
accion(estado(0,Z,G,0), estado(1,Z,G,1), 'Llevar el maiz').
accion(estado(1,Z,G,1), estado(0,Z,G,0), 'Traer el maiz').
accion(estado(1,Z,G,M), estado(0,Z,G,M), 'Regresa solo').
accion(estado(0,Z,G,M), estado(1,Z,G,M), 'Ir solo').

pertenece(X,[X|_]):-!.
pertenece(X,[_|L]):-pertenece(X,L).

camino(estado(1,1,1,1),V,V).
camino(Estado,Visitado,R):-accion(Estado,NuevoEstado,A), not(estadoMalo(NuevoEstado)),
                   not(pertenece(NuevoEstado,Visitado)),
                   writeln(A),
                   camino(NuevoEstado,[NuevoEstado|Visitado],R).

solucion(L):-camino(estado(0,0,0,0),[estado(0,0,0,0)],L).

Implementación del problema de las Jarras



Es un problema que ayuda a desarrollar la destreza intelectual del usuario.
Al resolver este problema, no solo implica obtener el resultado, sino comprender la importancia de usar La
Teoría de Grafos y el algoritmo de Recorrido en Profundidad y Anchura en la solución de los problemas lógicos y algoritmos actuales, ya que nos permite hacerlo de forma ordenada y se pueden usar técnicas como el Backtracking.


Planteamiento del Problema:
  • Se tienen dos jarras, una de 4 litros de capacidad y otra de 3.
  • Ninguna de ellas tiene marcas de medición.
  • Se tiene una bomba que permite llenar las jarras de agua.
  • Averiguar cómo se puede lograr tener exactamente 2 litros de agua en la jarra de 4 litros de capacidad.
  • Enfocar este ejercicio en un área de trabajo como la agricultura, para ver su importancia y aplicación.

Análisis del problema:

Problema como el anterior es resuelto con un simple algoritmo de búsqueda; pero lo que hay que tener claro primero es cuáles son los elementos del diseño del algoritmo.
En este caso son 4 los elementos:
  • Estado inicial
  • Estado final
  • Acciones
  • Función de costo
Solución Teórica:
  • Llenar la jarra de 4 litros completamente (para ello, la jarra de 4 litros no debe estar completamente llena).
  • Llenar la jarra de 3 litros completamente (para ello, la jarra de 3 litros no debe estar completamente llena).
  • Vaciar la jarra de 4 litros (para ello, la jarra debe contener algo de líquido).
  • Vaciar la jarra de 3 litros (para ello, la jarra debe contener algo de líquido).
  • Verter el contenido de la jarra de 4 litros en la jarra de 3 litros (para ello, la jarra de 4 litros debe contener algo de líquido y la de 3 litros no estar completamente llena).
  • Verter el contenido de la jarra de 3 litros en la jarra de 4 litros (para ello, la jarra de 3 litros debe contener algo de líquido y la de 4 litros no estar completamente llena).


Implementación:


%llenar A
accion(e(X,Y),e(4,Y)):- X < 4.

%llenar B
accion(e(X,Y),e(X,3)):- Y < 3.

%vaciar A
accion(e(X,Y),e(0,Y)):- X > 0.

%vaciar B
accion(e(X,Y),e(X,0)):- Y > 0.

%vertir A en B : jarra A se queda vacia
accion(e(X,Y),e(0,Z)):- X > 0,
                        Y < 3,
                        Z is X + Y,
                        Z =< 3.
                        
%vertir A en B : jarra B se queda llena
accion(e(X,Y),e(Z,3)):- X > 0,
                        Y < 3,
                        Z is X+Y-3,
                        Z =< 4.
                        
%vertir B en A : jarra B se queda vacia
accion(e(X,Y),e(Z,0)):- Y > 0,
                        X < 4,
                        Z is X + Y,
                        Z =< 4.

%vertir B en A : jarra A se queda llena
accion(e(X,Y),e(4,Z)):- Y > 0,
                        X < 3,
                        Z is X+Y-4,
                        Z =< 3.

menu:-siguiente(e(4,0),[e(4,0)],R),
      procesa(R).

procesa([]):- !.
procesa(H|C):- procesa(C),
               writeln(H).
                        
pertenece(E,[E|_]):- !.
pertenece(E,[_|C]):- pertenece(E,C).
siguiente(e(2,_),V,V):- !.
siguiente(e(_,2),V,V):- !.
siguiente(e(X,Y),V,R):- accion(e(X,Y), e(Xs,Ys)),
                    %format('estado(~W,~W)',[Xs,Ys]),
                    not(pertenece(e(Xs,Ys), V)),
                    siguiente(e(Xs,Ys), [e(Xs,Ys)|V],R).

Métodos de Busqueda

Búsquedas por profundidad

La búsqueda en profundidad, llamada DepthFirstSearch en inglés, es un algoritmo usado para recorrer o buscar elementos en un árbol o un grafo y pertenece al grupo de las búsquedas no informadas (sin heurísticas). Su procedimiento consiste en visitar todos los nodos de forma ordenada pero no uniforme en un camino concreto, dejando caminos sin visitar en su proceso. Una vez llega al final del camino vuelve atrás hasta que encuentra una bifurcación que no ha explorado, y repite el proceso hasta acabar el árbol (esto se conoce como Backtracking). En la siguiente figura mostramos el orden de visita, siendo los números en naranja dicho orden:



En cada llamada recursiva marcaremos el nodo actual como visitado y luego verificamos si es el nodo buscado para salir de la recursión, este será nuestro caso base. De no ser el nodo requerido, se hace la llamada recursiva con todos los nodos hijos del nodo actual, pero en este caso, a diferencia del recorrido BFS, no se visitarán todos los hijos de forma consecutiva, sino que el algoritmo recorrerá en profundidad hasta llegar a un nodo extremo o nodo hoja, antes de retornar al ambiente de recursión en donde se encuentran los otros nodos hijos. El orden en que se eligen las ramas en un recorrido DFS está determinado por el tipo de recorrido de procesamiento de árbol que se haya elegido, estos pueden ser:

  • Pre-orden: Se procesa primero la raíz, luego la rama izquierda y luego las ramas siguientes hasta llegar a la que se encuentra más a la derecha.
  • Post-orden: Se procesa el árbol desde las ramas izquierdas hasta la que se encuentra más a la derecha. Finalmente se procesa el nodo raíz
  • Simétrico o In-orden: Se procesa la rama de la izquierda, luego el nodo raíz y luego la rama derecha.
Aplicado al caso del Problema de las jarras: 
En el caso del problema de las jarras, se genera el siguiente grafo de búsqueda en profundidad:


Este grafo de búsqueda por profundidad nos denota la siguiente tabla de búsqueda en profundidad:


Estados de la solución:  ((2 3) (4 1) (0 1) (1 0) (1 3) (4 0) (0 0))


Búsquedas por anchura

La búsqueda en anchura (o búsqueda en amplitud), llamada BreadthFirstSearch en inglés, es un algoritmo usado para recorrer o buscar elementos en una estructura de datos como los árboles y los grafos.Pertenece al grupo de las búsquedas no informadas(sin heurísticas). Su procedimiento consiste en ir visitando todos los nodos de un nivel antes de proceder con el siguiente nivel tal y como mostramos en la siguiente figura (los números en naranja indican el orden de exploración de los nodos):



De modo que lo primero que hará será visitar la raíz, luego los hijos de la raíz, luego los hijos de cada uno de estos hijos y así sucesivamente. 
Aplicado al caso del Problema de las jarras: 
En el caso del problema de las jarras, se genera el siguiente grafo de búsqueda en anchura:

Este grafo de búsqueda por anchura nos denota la siguiente tabla de búsqueda en anchura: