Post on 07-Jul-2015
Utilizan conocimiento específico del problema, más allá de la definición del problema en sí mismo
Pueden encontrar la solución de manera más eficiente
Introducción
Búsquedas Informadas (Heurísticas)
•Búsqueda Primero El Mejor
•Búsqueda voraz primero el mejor
•Búsqueda A*
Búsqueda Primero el Mejor
-Caso particular del algoritmo general de búsqueda en Árboles en la cual se selecciona el siguiente nodo a expandir en base a una función de evaluación f(n)
-La evaluación mide la “distancia” al objetivo
-Se expande el nodo con la evaluación más baja
Búsqueda Primero el Mejor (cont…)
-La función de evaluación nos brinda el nodo que “parece” ser el mejor y por tanto el que se debe expandir
-Familia de algoritmos basados en una función heurística h(n)
h(n) = costo estimado del camino más barato desde el nodo n hasta el Objetivo
Búsqueda Voraz (Avara) Primero el Mejor
-Expande el nodo más cercano al Objetivo, asumiendo que probablemente conduzca más rápidamente a la solución.
-La función de evaluación f(n) sería la función heurística h(n)
f(n) = h(n)
h(n) = costo estimado del camino más barato desde el nodo n hasta el Objetivo
Búsqueda Voraz (Avara) Primero el Mejor
-El término Voraz ó Avara es porque en cada paso trata de ponerse tan cerca del objetivo como pueda, seleccionando el nodo con menor función de evaluación f(n)
-No necesariamente brinda la solución óptima
-Al igual que los otros métodos estudiados es necesario verificar los “callejones sin salidas” (no exapandir estados repetidos)
Ejemplo. Objetivo: ir de Arad a Bucarest
Oradea
Neamt
Iasi
Vaslui
Eforie
Hirsova
SibiuFagaras
Mehadia
Dobreta
Urziceni
Rimnicu Vilcea
Craiova
Pitesti
Giurgiu
Zerind
Arad
Timisoara
Lugoj
Bucharest
87
92
142
98
86
85
90
211
101
138
97
146
120
99
75
70
111
118
75
71
151
140
80
Consideraremos como función de evaluación (función heurística):
Distancia en Línea Recta
hDLR(n) = Distancia en Línea Recta desde la ciudad n hasta Bucharest
Figura 4.1 Valores de hDLR. Distancias en línea recta a Bucarest
Etapas de una búsqueda avara para llegar a Bucarest. Se utiliza la distancia en línea recta a Bucarest y la función heurística hDLR . Los nodos se identifican con sus valores h correspondientes.
Solución de Búsqueda Voraz (Primero el Mejor):
Arad – Sibiu – Fagaras – Bucharest
Costo total: (140+99+211) = 450
Sin embargo:
Arad – Sibiu – Rimmicu – Pitesti – Bucharest
Costo total: (140+80+97+101) = 418
Similar a BPP
- No es completa◦ Puede colgarse en algún bucle◦ (p.ej., Iasi ⇒ Neamt ⇒ Iasi ⇒ Neamt ⇒ …)◦ Pasa a ser completa en espacio finito si se sujeta
a una verificación de estado repetido
- No es óptima◦ lo vimos en el ejemplo
- Complejidad espacial y temporal es O(bm) -
Mantiene todos los nodos en memoria Si h es buena la complejidad disminuye
Búsqueda A* Primero el Mejor: Minimizar el costo estimado total de la solución:
-Evalúa los nodos combinando g(n) y h(n)
g(n): costo de haber alcanzado n
h(n): costo para llegar desde n hasta el objetivo
f(n) = g(n) + h(n) Costo más barato estimado de la solución a través de n
f(n) Combina el costo del camino para llegar a n y el costo estimado para llegar desde n al objetivo.
- En cada paso se expande el nodo con el valor más bajo de f(n), ó sea, de g(n)+h(n)
- La búsqueda A* es óptima siempre y cuando la función heurística h(n) se una heurística admisible.
-Significa que la función nunca sobreestime el costo de alcanzar el objetivo
-Son funciones optimistas
-En el ejemplo hDLR es admisible ya que la distancia en línea recta entre dos puntos es el camino más corto.
Es un algoritmo sencillo recursivo que intenta imitar la operación de la búsqueda primero el mejor estándar, pero utilizando sólo un espacio lineal.
Su estructura es similar a la búsqueda primero en profundidad recursiva.
Mantiene la pista del f-valor del mejor camino alternativo disponible desde cualquier antepasado del nodo actual.
La recursividad vuelve atrás, la BRPM sustituye los f-valores de cada nodo a lo largo del camino con el mejor f-valor de su hijo.
La BRPM recuerda el f-valor de la mejor hoja en el subárbol olvidado y por lo tanto puede decidir si merece la pena expandir el subárbol más tarde.
La BRPM es algo más eficiente que A*PI, pero todavía sufre de la regeneración excesiva de nodos
Existen dos algoritmos:
◦ A*M (A*con memoria acotada)◦ A*MS (A*M simplificada)
A*MS avanza expandiendo la mejor hoja hasta que la memoria este llena. En este punto, no se puede añadir un nuevo nodo al árbol de búsqueda sin retirar uno viejo
Como en la BRPM, A*MS devuelve hacia atrás, a su padre, el valor del nodo olvidado. De este modo, el antepasado de un subárbol olvidado sabe la calidad del mejor camino en el subárbol
A*MS bien podría ser el mejor algoritmo de uso general para encontrar soluciones óptimas, en particular cuando el espacio de estados es un grafo, los costos no son uniformes, y la generación de un nodo es costosa
¿Podría un agente aprender a buscar mejor? El método se apoya sobre un concepto
importante llamado el espacio de estados metanivel.
Cada estado es un espacio de estados metanivel captura el estado interno (computacional) de un programa que busca en un espacio de estados a nivel de objeto.
Un algoritmo de aprendizaje metanivel puede aprender de estas experiencias para evitar explorar subárboles no prometedores.
El objetivo del aprendizaje es reducir al mínimo el coste total de resolver el problema, compensar el costo computacional y el coste del camino.