RE:8 REINAS Y JARRAS DE AGUA
Publicado por
Patricio (1 intervención) el 06/10/2007 16:45:14
Problema de las jarras de agua
Se tienen dos jarras de agua, una de 4l y otra de 3l sin escala de medición.
Se desea tener 2l de agua en la jarra de 4l. Las siguientes operaciones son válidas: llenar las jarras, tirar agua de las jarras, pasar agua de una jarra a otra.
Solución:
* El espacio de estados se define como
{ (X,Y)/ X son los litros en la jarra de 4l con 0<=X<=4 AND Y son los litros de la jarra de 3l con 0<=Y<=3 }
* El estado inicial es (0,0)
* El estado final es (2,0). El estado final podría ser (2,N) en caso de que no importen los litros de la segunda jarra.
* Las reglas que se pueden aplicar son:
1. Llenar la jarra de 4l: Si (X,Y) AND X<4 => (4,Y)
2. Llenar la jarra de 3l: Si (X,Y) AND Y<3 => (X,3)
3. Vaciar la jarra de 4l: Si (X,Y) AND X>0 => (0, Y)
4. Vaciar la jarra de 3l: Si (X,Y) AND Y>0 => (X, 0)
5. Pasar agua de la jarra de 4l a la jarra de 3l hasta llenarla: Si (X,Y) AND X>0 AND X+Y>=3 => (X-(3-Y),3)
6. Pasar agua de la jarra de 3l a la jarra de 4l hasta llenarla: Si (X,Y) AND Y>0 AND X+Y>=4 => (4, Y-(4-X))
7. Pasar toda el agua de la jarra de 4l a la jarra de 3l: Si (X,Y) AND X>0 AND X+Y<3 => (0,X+Y)
8. Pasar toda el agua de la jarra de 3l a la jarra de 4l: Si (X,Y) AND Y>0 AND X+Y<4 => (X+Y,0)
El programa debería encontrar un pasaje de estados para ir del estado (0,0) al estado (2,0). Puede existir más de un pasaje de estados hacia la solución, por ejemplo:
(0,0) => (0,3) => (3,0) => (3,3) => (4,2) => (0,2) => (2,0)
en la cual, a partir del estado inicial, se aplicaron las reglas 2, 8, 2, 6, 3 y 8, hasta conseguir el estado objetivo.
Otro pasaje de estados hacia la solución es la siguiente
(0,0) => (4,0) => (1,3) => (1,0) => (0,1) => (4,1) => (2,3) => (2,0)
en la cual se aplicaron las reglas 1, 5, 4, 7, 1, 5 y 4
Con respecto a las reglas se puede concluir que:
* Las condiciones que se establecen en la parte izquierda a veces no son altamente necesarias pero restringen la aplicación de la regla a estados más adecuados. Esto incrementa la eficiencia del programa que utiliza las reglas. En el ejemplo anterior, la regla
1. Llenar la jarra de 4l: Si (X,Y) AND X<4 => (4,Y)
contiene la condición (X<4), especificando que la jarra no se encuentra llena. Si esta condición no se incluye, se puede aplicar la regla aún cuando la jarra está llena. Dado que en este caso el estado del problema no cambia la aplicación de la regla se considera inútil
* Las reglas no sólo deben describir el problema sino también algún tipo de conocimiento sobre su solución. Si en el ejemplo anterior se considera la siguiente nueva regla:
Vaciar "un poco" la jarra de 4l: Si (X,Y) AND X>0 => (X-Q, Y)
es decir, tirar agua sin cuantificar, intuitivamente se concluye que la aplicación de esta regla nunca nos acercará a la solución del problema.
* A veces, cuando se alcanzan algunos estados resulta obvio cómo se debe continuar hacia la solución. Es posible agregar reglas de propósito especial que capturen el conocimiento sobre casos especiales que conducen a la resolución del problema. En el ejemplo anterior, se pueden agregar las siguientes reglas de propósito especial:
Si (X,2) => (2,0)
Si (2,Y) AND Y>0 => (2,0)
Estas reglas no añaden más potencia al sistema ya que las operaciones que describen las proporcionan otras reglas más generales. En el ejemplo, la primera regla agregada es equivalente a la aplicación de las reglas generales 3 y 8; y la segunda regla agregada es equivalente a la aplicación de la regla general 4. Dependiendo de la estrategia de control que se utilice para seleccionar reglas durante la resolución del problema se puede mejorar el rendimiento si se les da preferencia a las reglas de casos especiales.
