Informática Aplicada

El problema de las Jarras de Agua con CLIPS.
Búsqueda primero en profundidad.

1. Planteamiento del problema

El problema de las jarras de agua es un pequeño pasatiempos que consiste en lo siguiente:

Tenemos dos jarras de agua, una de 4 litros y otra de 3 litros, sin marcas que nos permitan conocer la cantidad de agua que tenemos, salvo que la jarra esté llena o vacía. El objetivo es conseguir que la jarra de 4 litros contenga exactamente 2 litros de agua, usando para ello la jarra de tres.

Las operaciones que podemos realizar para conseguir nuestro objetivo son 6:

Se plantea diseñar un algoritmo de búsqueda con CLIPS que trate de resolver este problema, empleando el método denominado búsqueda primero en profundidad.

2. Busqueda primero en profundidad

Un algoritmo de búsqueda se basa en la construcción de un árbol, cuyo nodo raíz representa el estado inicial, es decir, la situación desde la cual partimos (en el caso de las Jarras de Agua, el estado inicial es que las dos jarras están vacías). Cada uno de los nodos hijos del raíz representarán los estados posibles a los que se puede cambiar desde el estado inicial, y así sucesivamente.

En la búsqueda primero en profundidad, partiendo del estado inicial, el algoritmo comienza a examinar cada uno de las trancisiones posibles, construyendo el árbol de estados, pero no abandona una rama hasta haber agotado todas las posibilidades, o haber llegado a la solución (denominada estado final o estado meta). Por tanto, su funcionamiento sería el siguiente: Parte del estado inicial y examina la primera de las posiblidades de transición, a continuación, pasa a examinar la primera de las posibilidades del nuevo estado, y así sucesivamente, va bajando de nivel en el árbol. Una vez que ha alcanzado el estado meta o un estado ya repetido (lo cual indica que por esa rama no va a ninguna parte), examina la siguiente posibilidad del último nodo explorado, y así hasta completar el árbol.

3. Implementación del algoritmo con CLIPS

Lo primero que se tiene claro a la hora de implementar este algoritmo en CLIPS es que tenemos que tener 6 reglas, una para cada una de las acciones que podemos realizar. En realidad se van a implementar 8, ya que las reglas para verter el contenido de una jarra sobre otras se desdoblarán para considerar dos casos:

  1. Que la jarra de origen tenga más agua de la que le cabe a la de destino.
  2. Que la jarra de destino tenga más capacidad que agua la de origen

Obviamente, cada una de estas reglas se activarán cuando exista un estado previo que permita la acción a realizar por la regla. Este estado previo se convertirá en el padre del nuevo estado recién creado.

Se creará una plantilla, denominada estado, que va a ser cada uno de los nodos del árbol de búsqueda.

3.1. Deftemplate estado

Esta plantilla contendrá los siguientes campos:

3.2. Diseño de reglas

Además de las reglas necesarias para crear las transiciones de estados que hemos descrito en el punto 1, y que se puede ver en el código del programa se han de implementar otra serie de reglas, que vemos a continuación:

regla inicial
Es la primera en activarse, con el hecho inicial. Su cometido es crear el estado inicial, en el que las dos jarras de agua están vacías, e inicializar el contador de nodos, que nos servirá para saber cuantos estados distintos se han evaluado.
regla contador-nodos
Actualiza el contador de nodos. Tiene una prioridad mayor que las reglas que generan nuevos estados, y se activa cuando hay un estado cuyo número de nodo es 0 (lo que quiere decir que está recién creado).
reglas elimina-estados-repetidos
Su función es detectar si hemos creado un estado que ya existía previamente y eliminarlo. Esta regla se ha implementado en dos versiones, para detectar dos situaciones diferentes: que el nodo recién creado sea de mayor profundidad que el que ya existía, en cuyo caso lo eliminamos sin más; o que el nodo recién creado sea de menor profundidad, con lo que nos interesará dejarlo, ya que si conduce a una solución, ésta será más corta. Esta última regla en realidad lo que hace es "desenganchar" el nodo más profundo y "engancharlo" en el lugar del nodo recién creado. Esto obligará a rehacer de nuevo el árbol a partir de ese nodo, ya que la información acerca de la profundidad de los hijos que puediera tener debe ser actualizada. De esto se encargará la regla siguiente.
Hay que hacer notar que la implementación de esta última versión de elimina-estados-repetidos rompe la filosofía del algoritmo de búsqueda en profundidad, además de que, si el nodo en cuestión condujera a una solución, lo único que ocurre es que el programa repetirá la solución para el nodo de menor profundidad, aunque en esta segunda solución, eliminará algunos estados redundantes. Esto se puede comprobar ejecutando el programa y examinando las soluciones primera y tercera que ofrece. La tercera solución es igual que la primera pero elimina dos estados innecesarios. En cualquier caso, la búsqueda en profundidad NO pasa por cambiar de sitio los nodos en el árbol. Aquí se ha diseñado así para ofrecer una nueva posibilidad y comprobar sus efectos.
Regla rehace-arbol
Su función es reconstruir la información relativa a la profundidad de un nodo y sus hijos que haya sido cambiado de nivel de profundidad con la regla anterior. Tiene una prioridad máxima, ya que esta información debe actualizarse antes de que sea utilizada por cualquier otra regla.
Regla meta-conseguida
Se dispara cuando existe un estado meta (la jarra de 4 litros tiene 2 litros). Su función es inicializar el recorrido hacia atrás, desde el estado meta hasta el inicial, para construir la secuencia que nos lleva a la solución. Para ello, guarda en un hecho, llamado recorre, el estado meta recién alcanzado, y crea un hecho, denominado camino, que es el que va a ir acumulando la secuencia de acciones.
Regla construye-camino
Esta regla se ira ejecutando mientras exista el hecho camino (con o sin secuencia detrás), que indica que se está construyendo el camino desde el estado meta hasta el inicial, y en el hecho recorre exista un estado que tenga padre (si no lo tuviera, querría decir que hemos alcanzado el nodo raiz, y hemos terminado la secuencia). En el hecho camino se van insertando los mensajes de texto del slot s-estado, siempre al principio, ya que el camino se recorre de atrás hacia adelante, pero la solución, obviamente deberá ofrecerse en sentido inverso.
Regla terminado
Se activa cuando hemos terminado de construir un camino desde un estado meta, y su objetivo es precisamente mostrar ese camino. Una vez hecho esto, eliminará los hechos camino y recorre, para continuar, si procede, con la búsqueda de nuevas soluciones
Regla informa-nodos
Esta regla es la última en ejecutarse, una vez que ya no quedan más estados que explorar, y su función es únicamente informar de cuantos nodos se han explorado.

[Código del programa] [Siguiente Ejercicio] [Indice General]

Práctica realizada por Juan José Cruz Jiménez
e-mail: i42crjij@uco.es