Experto

Tipos de Problemas
Deterministas, completamente observables – un solo estado
El agente sabe exactamente en que estado estará después de aplicar la solución (una secuencia)
No observable El agente tal vez no sabe donde está; la solución (si existe) es una secuencia
No determinista y/o parcialmente observables
Las percepciones proporcionan nueva información sobre estado actual
Lasolución es un árbol o una política de acción
A menudo mezclan búsqueda de la solución con ejecución
Frontera: colección de nodos generados pero no expandidos
todavía
Dimensiones:
* completitud
* complejidad en tiempo (número de nodos generados)
* complejidad en espacio (máximo número de nodos mantenidos en memoria)
* optimalidad
La complejidad en tiempo y espacio se miden enfunción de
b – factor máximo de ramificación del árbol de búsqueda
d – profundidad de la sol de menor costo
m – profundidad máxima del espacio de estados (puede ser ∞)
Tres familia de busqueda
Búsqueda a ciegas (o “no informada)
no hay info sobre el problema excepto la definición del mismo
Búsqueda heurística (o “informada”)
info adicional: qué estado intermedio (de frontera) es el másprometedor hacia la meta
Búsqueda en juegos (o con adversario o multiagente)
Primero en amplitud Propiedades
Completa:
Sí (si el máx núm de hijos b de cada nodo es finito)
Si la solución está a profundidad d, la encontrará tras expandir todos los nodos que tengan menor profundidad
Tiempo: 1+b+b2+b3+ … +bd + (bd+1-b)= O(bd+1) i.e., exponencial en d (profundidad de la solución de menor costo)Espacio: O(bd+1)
mantiene todos los nodos en memoria)
todos los nodos, o están en la frontera o son antecesores de un nodo de la frontera
Optimal: Sí, si el costo por paso es 1. En general no lo es.
Costo uniforme
Expande el nodo de menor costo todavía no expandido
Implementación: frontera es una cola ordenada por el costo del camino hasta el nodo
Equivale a primero en amplitud sitodos los costos son eguales
Completa Sí, si el costo del paso >=ε
Optimal Sí—se expanden nodos en orden creciente de g(n)
Primero en profundidad
Completa: No: falla en espacios con profundidad infinita, con bucles de estados.
Modificarla para evitar estados repetidos en el camino
Completa en espacios finitos
Optimal: No
Si el nodo J fuera una meta, se detendría sin encontrar G, quees mejor
Espacio: O(bm) lineal (muy bueno)
sólo almacena:
- un camino del estado inicial al nodo actual y
- los hermanos todavía no expandidos de cada nodo
Una vez que un nodo ha sido expandido, puede eliminarse de la memoria una vez que sus descendientes hayan sido totalmente explorados
Tiempo: O(bm):
en el peor caso, si G es la meta
terrible si m es mucho mayor que d
- puedeexplorar un largo camino (hasta profundidad m) que no lleve a la meta
Pero si hay gran densidad de soluciones, puede ser mucho más rápida que primero en amplitud
Descenso interactivo
Propiedades
Completa: Sí
Tiempo (d+1)b0 + d b1 + (d-1)b2 + … + bd = O(bd)
Espacio: O(bd)
Optimal: Sí, si el costo de cada op es 1
Se puede modificar para utilizar costo uniforme
La búsqueda voraz expande elnodo que parece más cercano a la meta
Propiedades
Completa: No—puede trabarse en bucles.
E.g. si Oradea es una meta, bucle Iasi -- Neamt -- Iasi -- Neamt --
Completa si el espacio de estados es finito y detectamos estados repetidos
Tiempo: O(bm), m: max profundidad del espacio de búsqueda (caso peor)
Una buena heurística puede mejorarlo tremendamente
Espacio: O(bm) ---hay que mantenertodos los nodos en memoria
Optimal: No
Busqueda A*
Idea: evitar la expansión de caminos que ya son costosos
Función de evaluación f(n) = g(n) + h(n)
g(n) = costo hasta ahora de llegar hasta n (desde el estado inicial)
h(n) = costo estimado del camino de n a una meta
f(n) = estimación total del costo de un camino desde el estado inicial a una meta pasando por n
Teorema: La búsqueda A*...