Una introducción a la Inteligenca Artificial (IA)


- Formulación de Problemas



Descargar 2.01 Mb.
Página16/29
Fecha de conversión20.03.2018
Tamaño2.01 Mb.
Vistas515
Descargas0
1   ...   12   13   14   15   16   17   18   19   ...   29

3.2.- Formulación de Problemas

Solución de problemas mediante el método espacio estado

Una forma de representar los problemas es a través del método de espacio-estado. Un espacio de estados es una representación de un problema en la que los nodos representan estados y los enlaces representan transiciones entre estados. Para capturar formalmente un problema como un espacio de estados se necesita definir:


  1. El estado inicial. El estado a partir del cual buscaremos la solución del problema

  2. El conjunto de acciones. El conjunto de las posibles acciones que se pueden realizar para pasar de un estado a otro.

  3. La prueba de metas. Que se aplica a un estado para saber si se trata de un estado meta.


Espacio de estados: el conjunto de todos los estados que pueden alcanzarse a partir del estado inicial mediante cualquier secuencia de acciones.

  • Estado inicial

  • El conjunto de acciones.


Solución del problema. La solución del problema se representa por medio de un estado meta.

El proceso de la resolución del problema consiste en encontrar una sucesión de transiciones que conduzca del estado inicial al estado meta.






Figura 3.1. Representación gráfica del método espacio-estado

La figura 3.1 muestra en forma gráfica el método de espacio-estado. Los círculos representan los diferentes estados y las flechas las acciones o transiciones de un estado a otro. Todos los nodos forman el espacio de estados y los nodos y flechas no punteados indican la trayectoria elegida para alcanzar el estado meta.


La representación de espacio-estado forma la base de casi todos los métodos de I.A. Sus principales ventajas se numeran a continuación


  1. Permite definir formalmente un problema como la necesidad de convertir una situación dada en una serie de situaciones deseadas usando un conjunto de situaciones permisibles.




  1. Nos permite definir el proceso de solución de un problema concreto como una combinación de técnicas conocidas.


3.3 Ejemplos


Los juegos como el ajedrez, el gato, el 8-puzzle, las damas inglesas, etc., se pueden representar fácilmente con el método de espacio-estados.
Por ejemplo, el juego del ajedrez se representaría de la siguiente forma
Estado inicial  la posición inicial de cada una de las piezas

Estado meta  cualquier posición de las piezas en la cual el rey contrario esté en jaque y no tenga ningún otro movimiento legal

Espacio de estados  Todas las posiciones posibles de las piezas que se puedan lograr a partir del estado inicial

Acciones o transacciones  Todos lo movimientos legales de cada una de las piezas
Ejercicio 3.1.


Forma un equipo de cuatro personas máximo y Trata de resolver el juego de las 8 fichas, aplicando diagramas de estados.






Estado Origen Estado Meta


Enfoque:

  • Estados: ubicación de cada una de las 8 placas, se debe incluir tambien el vacio.

  • Operadores: el espacio vacio puede moverse a la derecha, izquierda, arriba o abajo.

  • Prueba de Meta: el estado debe coincidir con el de la figura de la derecha

  • Costo de ruta: cada paso cuesta 1.


Observacion: El espacio de estados para este problema es de 9!, es decir 362,880 estados o configuraciones distintas





Unicio del árbol.


Los acertijos también se pueden representar fácilmente con el método de espacio-estado. Por ejemplo, considere el siguiente acertijo:

Ejercicio 3.2


Se tienen dos jarras de agua con capacidad de 3 y 4 litros respectivamente, ninguna de las cuales tiene marcas de medición ¿Cómo obtener exactamente 2 litros de agua en la jarra de 4 litros?




S

4 L

olución:

3 L

La primera pregunta que nos debemos hacer es cómo representar un estado en el problema, es decir, como representar un momento determinado en el problema. Específicamente en este caso un estado prodría ser que la jarra de agua de cuatro litros tuviera dos litros de agua y la de tres estuviera llena, otro estado podría ser que las dos jarras de agua estuvieran llenas o que estuvieran vacias.


La representación de los estados depende de quien formaliza el problema y debe tratar de contener únicamente la información relevante al problema.
En este caso, representaremos un estado como un par ordenado de números (x, y) en donde x representa los litros de agua que tiene la cubeta de cuatro litros y y los litros de agua que tiene la cubeta de tres litros. Bajo esta representación, el estado (2, 1) significa que la cubeta de cuatro litros tiene dos litros de agua y la cubeta de tres uno, el estado (0,0) significa que ambas cubetas están vacias y el estado (4,3) que ambas están llenas.
El segundo paso es formalizar las operaciones permisibles que conduzcan de un estado a otro. Si la jarra de cuatro litros está vacia, una operación permisible sería llenarla. Esta operación transfiere el estado (0, x) al estado (4, x). Nótese que para aplicar esta operación es irrelavante los litros de agua que contenga la jarra de tres litros, por lo que los representamos como una variable. En la tabla 3.1 se enlistan todas las operaciones permisibles en este problema:


Lenguaje Natural

Representación x=4l, y=3l

RegNo

Operación

Condiciones

Transición de estados

Condiciones

1

Llenar la jarra de 4 lts

Que no esté llena

(x,y)  (4,y)

x < 4

2

Llenar la jarra de 3 lts

Que no esté llena

(x,y)  (x,3)

y < 3

3

Vaciar la jarra de 4 lts

Que no esté vacia

(x,y)  (0,x)

x > 0

4

Vaciar la jarra de 3 lts

Que no esté vacia

(x,y)  (y,0)

y > 0

5

Verter agua de la jarra de 3 lts a la jarra de 4 lts hasta que esta última esté llena

Que la jarra de 3 lts tenga agua y que la jarra de 4 lts no esté llena, además que la suma de los lts de las dos jarras sea mayor o igual a 4

(x,y)

(4, y-(4-x))



x < 4,

y > 0 y

x + y  4

6

Verter agua de la jarra de 4 lts a la jarra de 3 lts hasta que esta última esté llena

Que la jarra de 4 lts tenga agua y que la jarra de 4 lts no esté llena, además que la suma de los lts de las dos jarras sea mayor o igual a 3

(x,y)

(x-(3-y),3)



x > 0,

y < 3 y

x + y  3

7

Verter toda el agua de la jarra de 3 lts a la jarra de 4 lts

Que la jarra de 3 lts tenga agua y que la suma de las dos sea menor o igual a 4

(x,y)

(x+ y,0)



y > 0 y

x + y  4

8

Verter toda el agua de la jarra de 4 lts a la jarra de 3 lts

Que la jarra de 4 lts tenga agua y que la suma de las dos sea menor o igual a 3

(x,y)

(0,y+x)



x > 0 y

x + y  3





Compartir con tus amigos:
1   ...   12   13   14   15   16   17   18   19   ...   29


La base de datos está protegida por derechos de autor ©psicolog.org 2019
enviar mensaje

enter | registro
    Página principal


subir archivos