PROBLEMAS Y ESPACIO DE ESTADOS
Un problema típico de la Inteligencia Artificial consiste en buscar un estado concreto entre un conjunto determinado, al que se le llama espacio de estados.
.Muchos de los problemas que pueden ser resueltos aplicando técnicas de inteligencia artificial se modelan en forma simbólica y discreta definiendo las configuraciones posibles del universo estudiado. El problema se plantea entoces en términos de encontrar una configuración objetivo a partir de una configuración inicial dada, aplicando transformaciones válidas según el modelo del universo. La respuesta es la secuencia de transformaciones cuya aplicación succesiva lleva a la configuración deseada
.jpg)
Ejemplo de espacio de estados
Descripción del problema:
Un arriero se encuentra en el borde de un rio llevando un puma, una cabra y una lechuga. Debe cruzar a la otra orilla por medio de un bote con capacidad para dos (el arriero y alguna de sus pertenecias). La dificultad es que si el puma se queda solo con la cabra la devorará, y lo mismo sucederá si la cabra se queda sola con la lechuga. ¿Cómo cruzar sin perder ninguna pertenencia?
Representación de las configuraciones del universo del problema:
Basta precisar la situación antes o después de cruzar. El arriero y cada una de sus pertenencias tienen que estar en alguna de las dos orillas. La representación del estado debe entonces indicar en que lado se encuentra cada uno de ellos. Para esto se puede utilizar un término simbólico con la siguiente sintáxis: estado(A,P,C,L), en que A, P, C y L son variables que representan, respectivamente, la posición del arriero, el puma, la cabra y la lechuga. Las variables pueden tomar dos valores: i y d, que simbolizan respectivamente el borde izquierdo y el borde derecho del rio. Por convención se elige partir en el borde izquierdo. El estado inicial es entoncesestado(i,i,i,i). El estado objetivo es estado(d,d,d,d).
Definición de las reglas de transición:
El arriero tiene cuatro acciones posibles: cruzar solo, cruzar con el puma, cruzar con la cabra y cruzar con la lechuga. Estas acciones están condicionadas a que ambos pasajeros del bote estén en la misma orilla y a que no queden solos el puma con la cabra o la cabra con la lechuga. El estado resultante de una acción se determina intercambiando los valores i y d para los pasajeros del bote.
Generación del espacio de estados
En este ejemplo se puede explicitar todo el espacio de estados (el número de configuraciones está acotado por 24).
Un arriero se encuentra en el borde de un rio llevando un puma, una cabra y una lechuga. Debe cruzar a la otra orilla por medio de un bote con capacidad para dos (el arriero y alguna de sus pertenecias). La dificultad es que si el puma se queda solo con la cabra la devorará, y lo mismo sucederá si la cabra se queda sola con la lechuga. ¿Cómo cruzar sin perder ninguna pertenencia?
Representación de las configuraciones del universo del problema:
Basta precisar la situación antes o después de cruzar. El arriero y cada una de sus pertenencias tienen que estar en alguna de las dos orillas. La representación del estado debe entonces indicar en que lado se encuentra cada uno de ellos. Para esto se puede utilizar un término simbólico con la siguiente sintáxis: estado(A,P,C,L), en que A, P, C y L son variables que representan, respectivamente, la posición del arriero, el puma, la cabra y la lechuga. Las variables pueden tomar dos valores: i y d, que simbolizan respectivamente el borde izquierdo y el borde derecho del rio. Por convención se elige partir en el borde izquierdo. El estado inicial es entoncesestado(i,i,i,i). El estado objetivo es estado(d,d,d,d).
Definición de las reglas de transición:
El arriero tiene cuatro acciones posibles: cruzar solo, cruzar con el puma, cruzar con la cabra y cruzar con la lechuga. Estas acciones están condicionadas a que ambos pasajeros del bote estén en la misma orilla y a que no queden solos el puma con la cabra o la cabra con la lechuga. El estado resultante de una acción se determina intercambiando los valores i y d para los pasajeros del bote.
Generación del espacio de estados
En este ejemplo se puede explicitar todo el espacio de estados (el número de configuraciones está acotado por 24).
| estado | movidas | |||
|---|---|---|---|---|
| cruza solo | con puma | con cabra | con lechuga | |
| estado(i,i,i,i) | problema | problema | estado(d,i,d,i) | problema |
| estado(d,i,d,i) | estado(i,i,d,i) | imposible | estado(i,i,i,i) | imposible |
| estado(i,i,d,i) | estado(d,i,d,i) | estado(d,d,d,i) | imposible | estado(d,i,d,d) |
| estado(d,d,d,i) | problema | estado(i,i,d,i) | estado(i,d,i,i) | imposible |
| estado(d,i,d,d) | problema | imposible | estado(i,i,i,d) | estado(i,i,d,i) |
| estado(i,d,i,i) | problema | imposible | estado(d,d,d,i) | estado(d,d,i,d) |
| estado(i,i,i,d) | problema | estado(d,d,i,d) | estado(d,i,d,d) | imposible |
| estado(d,d,i,d) | estado(i,d,i,d) | estado(i,i,i,d) | imposible | estado(i,d,i,i) |
| estado(i,d,i,d) | estado(d,d,i,d) | imposible | estado(d,d,d,d) | imposible |
| estado(d,d,d,d) | problema | problema | estado(i,d,i,d) | problema |
Este espacio de estados también se puede representar mediante un grafo equivalente.
Solución del problema
El camino que pasa por la siguiente secuencia de estados es una solución del problema:estado(i,i,i,i)
cruza con cabra
estado(d,i,d,i)
cruza solo
estado(i,i,d,i)
cruza con puma
estado(d,d,d,i)
cruza con cabra
estado(i,d,i,i)
cruza con lechuga
estado(d,d,i,d)
cruza solo
estado(i,d,i,d)
cruza con cabra
estado(d,d,d,d)
ejemplo de solución de estados
No hay comentarios:
Publicar un comentario