2 BH1 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 de resolverlos

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 problemas
definidos en esa representacióncomú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 el objetivo
Elementos que son relevantes en el problemadefinidos 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 de estados: un problema se divide en un conjunto de pasos
de resolución desde elinicio 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 definirun 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 estado especiales el Estado Inicial (punto de
partida) y el Estado Final (objetivo del problema)
¿Queincluir 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ón
Operador: Función de transformación sobre la representación de un
estado que lo convierte en otro estado
Los operadoresdefinen 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 loque 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 enEspacio 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 aplicación de los
operadores a los estados. Puede ser importante o no según el
problema y que tipo de solución busquemos

c b e a (LSI-FIB-UPC)

Introducción a...