Heuristicas

Solución de Problemas Mediante Búsqueda (2)
Carlos Hurtado Depto de Ciencias de la Computación, Universidad de Chile

Recapitulando: Estrategias de Búsqueda • Búsqueda de Costo Uniforme
– Casoparticular: Búsqueda Primero en Anchura

• Búsqueda Primero el Mejor
– Caso particular: Búsqueda Primero en Profundidad

Algoritmo A*
• [Hart, Nilsson and Raphael, 1968] • Combina aspectos deBúsqueda Costo Uniforme y Búsqueda Primero el Mejor • Calidad de cada nodo en la frontera está dado por: f(n) = g(n) + h’(n) • Los nodos son ordenados en FRONTERA de menor a mayor f(n)

• Input:(V,E), s, G • Variables:

Algoritmo A*

– FRONTERA: lista de nodos a visitar, inicialmente s – Tr: árbol de búsqueda, originalmente contiene un nodo etiquetado con s

• While (FRONTERA no es vacío)do
– – – – Sacar primer nodo n de FRONTERA Si n está en G entregar solución Agregar al final de FRONTERA nodos P apuntados por n Para cada nodo agregado computar f(n) = g(n) + h’(n) – Por cada nodo ren P, agregar un nuevo nodo a Tr, etiquetarlo con r y conectarlo desde el nodo de Tr asociado a n

– Reordenar FRONTERA de acuerdo a función f

Manhattan Bike Curier (Acíclico) Ref. Curso IA U.of Toronto

A*: mo - slb

Análisis de A*
• En el ejemplo A* llega rápidamente al objetivo (slb)
– Expande sólo 7 nodos que no llegan a la solución

• A* encuentra el camino de costo mínimo •Combina lo mejor de
– Búsqueda de Costo Uniforme: encuentra el mejor camino – Búsqueda Primero Mejor: se dirige rápidamente al objetivo

Propiedades de A*
• ¿A* siempre encuentra el mejor camino?Propiedades de A*
• ¿A* siempre encuentra el mejor camino?
– No necesariamente: – Supongamos que h(al) =17 – El nodo al no será expandido antes de del camino por ls

Heurística Admisible
•Teorema: Supongamos que existe una solución (solución = camino de menor costo). Entonces A* la encuentra si:
1. Cada nodo del grafo tiene un número finito de sucesores. 2. El costo de cada nodo en...