Post on 18-Feb-2018
Resolución de problemas Introducción
Resolución de Problemas
La resolución de problemas es una capacidad que consideramosinteligenteSomos capaces de resolver problemas muy diferentes
Encontrar el camino en un laberintoResolver un crucigramaJugar a un juegoDiagnosticar una enfermedadDecidir si invertir en bolsa...
El objetivo es que un programa también sea capaz de resolverlos
cbea (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 puedaresolver automáticamenteNecesitamos:
Una representación común para todos los problemasAlgoritmos que usen alguna estrategia para resolver problemasdefinidos en esa representación común
cbea (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 partidaUn objetivo a alcanzarAcciones a nuestra disposición para resolver el problemaRestricciones sobre el objetivoElementos que son relevantes en el problema definidos por el tipo dedominio
cbea (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 demanera automáticaRepresentaciones generales
Espacio de estados: un problema se divide en un conjunto de pasosde resolución desde el inicio hasta el objetivoReducción a subproblemas: un problema se puede descomponer enuna jerarquía de subproblemas
Representaciones para problemas específicosResolución de juegosSatisfacción de restricciones
cbea (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 susrelacionesEn cada instante de la resolución de un problema esos elementostendrán unas características y relaciones específicasDenominaremos Estado a la representación de los elementos quedescriben el problema en un momentoDistinguiremos dos estado especiales el Estado Inicial (punto departida) y el Estado Final (objetivo del problema)¿Que incluir en el estado?
cbea (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 necesitamosoperadores de transformaciónOperador: Función de transformación sobre la representación de unestado que lo convierte en otro estadoLos operadores definen una relación de accesibilidad entre estadosRepresentación de un operador:
Condiciones de aplicabilidadFunción de transformación
¿Que operadores? ¿Cuantos? ¿Que granularidad?
cbea (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 sedenomina espacio de estadosRepresenta todos los caminos que hay entre todos los estados posiblesde un problemaPodría asimilarse con un mapa de carreteras de un problemaLa solución de nuestro problema esta dentro de ese mapa
cbea (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 finalTipos de solución: una cualquiera, la mejor, todasCoste de una solución: Gasto en recursos de la aplicación de losoperadores a los estados. Puede ser importante o no según elproblema y que tipo de solución busquemos
cbea (LSI-FIB-UPC) Introducción a la Inteligencia Artificial Curso 2011/2012 8 / 28
Resolución de problemas Espacio de estados
Descripción de un problema en Espacio de Estados
Definir el conjunto de estados del problema (explícita oimplícitamente)Especificar el estado inicialEspecificar el estado final o las condiciones que cumpleEspecificar los operadores de cambio de estado (condiciones deaplicabilidad y función de transformación)Especificar el tipo de solución:
La secuencia de operadores o el estado finalUna solución cualquiera, la mejor (definición de coste), . . .
cbea (LSI-FIB-UPC) Introducción a la Inteligencia Artificial Curso 2011/2012 9 / 28
Resolución de problemas Espacio de estados
Ejemplo: 8 puzzle
7 8
65
321
4
cbea (LSI-FIB-UPC) Introducción a la Inteligencia Artificial Curso 2011/2012 10 / 28
Resolución de problemas Espacio de estados
Ejemplo: 8 puzzle
Espacio de estados: Configuraciones de 8 fichas en el tableroEstado inicial: Cualquier configuraciónEstado final: Fichas en orden específicoOperadores: Mover hueco
Condiciones: El movimiento está dentro del tableroTransformación: Intercambio entre el hueco y la ficha en la posición delmovimiento
Solución: Qué pasos + El menor número
cbea (LSI-FIB-UPC) Introducción a la Inteligencia Artificial Curso 2011/2012 11 / 28
Resolución de problemas Espacio de estados
Ejemplo: N reinas
cbea (LSI-FIB-UPC) Introducción a la Inteligencia Artificial Curso 2011/2012 12 / 28
Resolución de problemas Espacio de estados
Ejemplo: N reinas
Espacio de estados: Configuraciones de 0 a n reinas en el tablero consólo una por fila y columnaEstado inicial: Configuración sin reinas en el tableroEstado final: Configuración en la que ninguna reina se mata entre siOperadores: Colocar una reina en una fila y columna
Condiciones: La reina no es matada por ninguna ya colocadaTransformación: Colocar una reina mas en el tablero en una fila ycolumna determinada
Solución: Una solución, pero no nos importan los pasos
cbea (LSI-FIB-UPC) Introducción a la Inteligencia Artificial Curso 2011/2012 13 / 28
Resolución de problemas Búsqueda en el espacio de estados
Búsqueda en el espacio de estados
La resolución de un problema con esta representación pasa porexplorar el espacio de estadosPartimos del estado inicial evaluando cada paso hasta encontrar unestado finalEn el caso peor exploraremos todos los posibles caminos entre elestado inicial del problema hasta llegar al estado final
cbea (LSI-FIB-UPC) Introducción a la Inteligencia Artificial Curso 2011/2012 14 / 28
Resolución de problemas Búsqueda en el espacio de estados
Estructura del espacio de estados
Primero definiremos una representación del espacio de estados parapoder implementar algoritmos que busquen soluciones
Estructuras de datos: Árboles y GrafosEstados = NodosOperadores = Arcos entre nodos (dirigidos)Árboles: Solo un camino lleva a un nodoGrafos: Varios caminos pueden llevar a un nodo
cbea (LSI-FIB-UPC) Introducción a la Inteligencia Artificial Curso 2011/2012 15 / 28
Resolución de problemas Búsqueda en el espacio de estados
Algoritmo Básico
El espacio de estados puede ser infinitoEs necesaria una aproximación diferente par buscar y recorrer árbolesy grafos (no podemos tener la estructura en memoria)La estructura la construimos a medida que hacemos la búsqueda
cbea (LSI-FIB-UPC) Introducción a la Inteligencia Artificial Curso 2011/2012 16 / 28
Resolución de problemas Búsqueda en el espacio de estados
Algoritmo Básico
Función: Búsqueda en espacio de estados()Datos: El estado inicialResultado: Una soluciónSeleccionar el primer estado como el estado actualmientras estado actual 6= estado final hacer
Generar y guardar sucesores del estado actual (expansión)Escoger el siguiente estado entre los pendientes (selección)
fin
La selección del siguiente nodo determinará el tipo de búsqueda(orden de selección o expansión)Es necesario definir un orden entre los sucesores de un nodo (orden degeneración)
cbea (LSI-FIB-UPC) Introducción a la Inteligencia Artificial Curso 2011/2012 17 / 28
Resolución de problemas Búsqueda en el espacio de estados
Algoritmo Básico
Nodos abiertos: Estados generados pero aún no visitadosNodos cerrados: Estados visitados y que ya se han expandidoTendremos una estructura para almacenar los nodos abiertosLas diferentes políticas de inserción en la estructura determinarán eltipo de búsquedaSi exploramos un grafo puede ser necesario tener en cuenta losestados repetidos (esto significa tener una estructura para los nodoscerrados). Merece la pena si el número de nodos diferentes espequeño respecto al número de caminos
cbea (LSI-FIB-UPC) Introducción a la Inteligencia Artificial Curso 2011/2012 18 / 28
Resolución de problemas Búsqueda en el espacio de estados
Características de los algoritmos
Características:Completitud: ¿Encontrará una solución?Complejidad temporal: ¿Cuanto tardará?Complejidad espacial: ¿Cuanta memoria gastará?Optimalidad: ¿Encontrará la solución óptima?
cbea (LSI-FIB-UPC) Introducción a la Inteligencia Artificial Curso 2011/2012 19 / 28
Resolución de problemas Búsqueda en el espacio de estados
Algoritmo General de Búsqueda
Algoritmo: Busqueda GeneralEst_abiertos.insertar(Estado inicial)Actual← Est_abiertos.primero()mientras no es_final?(Actual) y no Est_abiertos.vacia?() hacer
Est_abiertos.borrar_primero()Est_cerrados.insertar(Actual)Hijos ← generar_sucesores(Actual)Hijos ← tratar_repetidos(Hijos, Est_cerrados, Est_abiertos)Est_abiertos.insertar(Hijos)Actual ← Est_abiertos.primero()
fin
Variando la estructura de abiertos variamos el comportamiento del algoritmo(orden de visita de los nodos)La función generar_sucesores seguirá el orden de generación de sucesoresdefinido en el problemaEl tratamiento de repetidos dependerá de cómo se visiten los nodos
cbea (LSI-FIB-UPC) Introducción a la Inteligencia Artificial Curso 2011/2012 20 / 28
Resolución de problemas Búsqueda en el espacio de estados
Tipos de algoritmos
Algoritmos de búsqueda ciegaNo tienen en cuenta el coste de la solución en la búsquedaSu funcionamiento es sistemático, siguen un orden de visitas ygeneración de nodos establecido por la estructura del espacio debúsquedaAnchura prioritaria, Profundidad prioritaria, Profundidad iterativa
Algoritmos de búsqueda heurísticaUtilizan una estimación del coste de la solución para guiar la búsquedaNo siempre garantizan el óptimo, ni una soluciónHill-climbing, Branch and Bound, A∗, IDA∗
cbea (LSI-FIB-UPC) Introducción a la Inteligencia Artificial Curso 2011/2012 21 / 28
Búsqueda ciega Búsqueda en anchura y profundidad
Búsqueda en Anchura Prioritaria
Los nodos se visitan y generan por nivelesLa estructura para los nodos abiertos es una cola (FIFO)Un nodo es visitado cuando todos los nodos de los niveles superiores ysus hermanos precedentes han sido visitadosCaracterísticas:
Completitud: El algoritmo siempre encuentra una soluciónComplejidad temporal: Exponencial respecto al factor de ramificación yla profundidad de la solución O(rp)Complejidad espacial: Exponencial respecto al factor de ramificación yla profundidad de la solución O(rp)Optimalidad: La solución que se encuentra es óptima en número deniveles desde la raíz
cbea (LSI-FIB-UPC) Introducción a la Inteligencia Artificial Curso 2011/2012 22 / 28
Búsqueda ciega Búsqueda en anchura y profundidad
Búsqueda en Profundidad Prioritaria
Los nodos se visitan y generan buscando los nodos a mayorprofundidad y retrocediendo cuando no se encuentran nodos sucesoresLa estructura para los nodos abiertos es una pila (LIFO)Para garantizar que el algoritmo acaba debe imponerse un límite en laprofundidad de exploraciónCaracterísticas
Completitud: El algoritmo encuentra una solución si se impone unlímite de profundidad y existe una solución dentro de ese límiteComplejidad temporal: Exponencial respecto al factor de ramificación yla profundidad del límite de exploración O(rp)Complejidad espacial: En el caso de no controlar los nodos repetidos elcoste es lineal respecto al factor de ramificación y el límite deprofundidad O(rp). Si tratamos repetidos el coste es igual que enanchura. Si la implementación es recursiva el coste es O(p)Optimalidad: No se garantiza que la solución sea óptima
cbea (LSI-FIB-UPC) Introducción a la Inteligencia Artificial Curso 2011/2012 23 / 28
Búsqueda ciega Búsqueda en anchura y profundidad
Búsqueda en Profundidad Limitada
Procedimiento: Busqueda en profundidad limitada (limite: entero)Est_abiertos.insertar(Estado inicial)Actual ← Est_abiertos.primero()mientras no es_final?(Actual) y no Est_abiertos.vacia?() hacer
Est_abiertos.borrar_primero()Est_cerrados.insertar(Actual)si profundidad(Actual) ≤ limite entonces
Hijos ← generar_sucesores (Actual)Hijos ← tratar_repetidos (Hijos, Est_cerrados, Est_abiertos)Est_abiertos.insertar(Hijos)
finActual ← Est_abiertos.primero()
fin
La estructura de abiertos es ahora una pilaSe dejan de generar sucesores cuando se llega al límite de profundidadEsta modificación garantiza que el algoritmo acabaSi tratamos repetidos el ahorro en espacio es nulo
cbea (LSI-FIB-UPC) Introducción a la Inteligencia Artificial Curso 2011/2012 24 / 28
Búsqueda ciega Búsqueda en profundidad iterativa
ID (iterative deepening): profundidad iterativa
Intenta combinar el comportamiento espacial del DFS con laoptimalidad del BFSEl algoritmo consiste en realizar búsquedas en profundidad sucesivascon un nivel de profundidad máximo acotado y creciente en cadaiteraciónAsí se consigue el comportamiento de BFS pero sin su coste espacial,ya que la exploración es en profundidad, y además los nodos seregeneran a cada iteraciónAdemás esto permite evitar los casos en que DFS no acaba (existenramas infinitas)En la primera iteración la profundidad máxima será 1 y este valor iráaumentando en sucesivas iteraciones hasta llegar a la soluciónPara garantizar que el algoritmo acaba si no hay solución, se puededefinir una cota máxima de profundidad en la exploración
cbea (LSI-FIB-UPC) Introducción a la Inteligencia Artificial Curso 2011/2012 25 / 28
Búsqueda ciega Búsqueda en profundidad iterativa
ID (iterative deepening)
Iteracion 1: 1
Iteracion 2: 2,3,4,5
1,2,6
3,7
8 9 10 11
4,12
13 14 15 16
5,17
18 19 20 21
Iteracion 3: 6,7,8,9,...21
cbea (LSI-FIB-UPC) Introducción a la Inteligencia Artificial Curso 2011/2012 26 / 28
Búsqueda ciega Búsqueda en profundidad iterativa
Búsqueda en profundidad iterativa
Procedimiento: Búsqueda en profundidad iterativa (limite: entero)prof ← 1Actual ← Estado inicialmientras no es_final?(Actual) y prof<limite hacer
Est_abiertos.inicializar()Est_abiertos.insertar(Estado inicial)Actual ← Est_abiertos.primero()mientras no es_final?(Actual) y no Est_abiertos.vacia?() hacer
Est_abiertos.borrar_primero()Est_cerrados.insertar(Actual)si profundidad(Actual) ≤ prof entonces
Hijos ← generar_sucesores (Actual)Hijos ← tratar_repetidos (Hijos, Est_cerrados, Est_abiertos)Est_abiertos.insertar(Hijos)
finActual← Est_abiertos.primero()
finprof ← prof+1
fin
cbea (LSI-FIB-UPC) Introducción a la Inteligencia Artificial Curso 2011/2012 27 / 28
Búsqueda ciega Búsqueda en profundidad iterativa
Profundidad Iterativa
Completitud: El algoritmo siempre encontrará la soluciónComplejidad temporal: La misma que la búsqueda en anchura. Elregenerar el árbol en cada iteración solo añade un factor constante ala función de coste O(rp)Complejidad espacial: Igual que en la búsqueda en profundidadOptimalidad: La solución es óptima igual que en la búsqueda enanchura
cbea (LSI-FIB-UPC) Introducción a la Inteligencia Artificial Curso 2011/2012 28 / 28