jueves, 19 de mayo de 2016

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).
banner
Previous Post
Next Post

Hola, me llamo Andrés.Soy egresado de la carrera de Ingeniería Informática en la Universidad Nacional de Trujillo (Perú).Me considero autodidacta de corazón ,amante del mundo de la programación, software libre y hacking ético

0 comentarios: