Implementación del problema de las Jarras

Share:


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).

No hay comentarios