Introduccion Busqueda

Resolución de problemas

Introducción

Resolución de Problemas

La resolución de problemas es una capacidad que consideramos
inteligente
Somos capaces de resolver problemas muy diferentes
Encontrar el camino en un laberinto
Resolver un crucigrama
Jugar a un juego
Diagnosticar una enfermedad
Decidir si invertir en bolsa
...

El objetivo es que un programa también sea capaz deresolverlos

c b e a (LSI-FIB-UPC)

Introducción a la Inteligencia Artificial

Curso 2011/2012

1 / 28

Resolución de problemas

Introducción

Resolución de Problemas

Deseamos definir cualquier tipo de problema de manera que se pueda
resolver automáticamente
Necesitamos:
Una representación común para todos los problemas
Algoritmos que usen alguna estrategia para resolver problemasdefinidos en esa representación común

c b e a (LSI-FIB-UPC)

Introducción a la Inteligencia Artificial

Curso 2011/2012

2 / 28

Resolución de problemas

Introducción

Definición de un Problema

Si abstraemos los elementos de un problema podemos identificar:
Un punto de partida
Un objetivo a alcanzar
Acciones a nuestra disposición para resolver el problema
Restricciones sobre elobjetivo
Elementos que son relevantes en el problema definidos por el tipo de
dominio

c b e a (LSI-FIB-UPC)

Introducción a la Inteligencia Artificial

Curso 2011/2012

3 / 28

Resolución de problemas

Introducción

Representación de problemas

Existen diferentes formas de representar problemas para resolverlos de
manera automática
Representaciones generales
Espacio deestados: un problema se divide en un conjunto de pasos
de resolución desde el inicio hasta el objetivo
Reducción a subproblemas: un problema se puede descomponer en
una jerarquía de subproblemas

Representaciones para problemas específicos
Resolución de juegos
Satisfacción de restricciones

c b e a (LSI-FIB-UPC)

Introducción a la Inteligencia Artificial

Curso 2011/2012

4 / 28Resolución de problemas

Introducción

Representación de problemas: Estados

Podemos definir un problema por los elementos que intervienen y sus
relaciones
En cada instante de la resolución de un problema esos elementos
tendrán unas características y relaciones específicas
Denominaremos Estado a la representación de los elementos que
describen el problema en un momento
Distinguiremos dos estadoespeciales el Estado Inicial (punto de
partida) y el Estado Final (objetivo del problema)
¿Que incluir en el estado?

c b e a (LSI-FIB-UPC)

Introducción a la Inteligencia Artificial

Curso 2011/2012

5 / 28

Resolución de problemas

Introducción

Modificación del estado: operadores

Para poder movernos entre los diferentes estados necesitamos
operadores de transformaciónOperador: Función de transformación sobre la representación de un
estado que lo convierte en otro estado
Los operadores definen una relación de accesibilidad entre estados
Representación de un operador:
Condiciones de aplicabilidad
Función de transformación

¿Que operadores? ¿Cuantos? ¿Que granularidad?

c b e a (LSI-FIB-UPC)

Introducción a la Inteligencia Artificial

Curso 2011/2012

6 /28

Resolución de problemas

Espacio de estados

Espacio de estados

Los estados y su relación de accesibilidad conforman lo que se
denomina espacio de estados
Representa todos los caminos que hay entre todos los estados posibles
de un problema
Podría asimilarse con un mapa de carreteras de un problema
La solución de nuestro problema esta dentro de ese mapa

c b e a (LSI-FIB-UPC)Introducción a la Inteligencia Artificial

Curso 2011/2012

7 / 28

Resolución de problemas

Espacio de estados

Solución de un problema en Espacio de Estados

Solución: Secuencia de pasos que llevan del estado inicial al final
(secuencia de operadores) o también el estado final
Tipos de solución: una cualquiera, la mejor, todas
Coste de una solución: Gasto en recursos de la...