Inteligencia Artificial II

Búsqueda y Optimización

Búsqueda global heurística�

Tomado de: Martin Marchetta�martin.marchetta@ingenieria.uncuyo.edu.ar

Hernán Garrido

carloshernangarridoogmail.com

Introducción

Introducción

• Propiedades de un algoritmo de búsqueda
• Completez
• Si existe solución, la encuentra siempre?�
• Optimalidad
• Es la primera solución encontrada la mejor de todas?�
• Complejidad Espacial
• ¿Cuánta memoria necesita, como función de las entradas?
• Complejidad Temporal
• ¿Cuánto tiempo necesita, como función de las entradas?

​

3

Análisis Asintótico

• Tipos de problemas de optimización
• Discretos vs. Continuos
• Objetivo simple vs. Multi-objetivo
• Distintas complejidades��
• Enfoques alternativos
• Búsqueda global vs. Búsqueda local
• Búsqueda no informada vs. Heurística vs Metaheurística
• Búsqueda determinística vs. Búsqueda estocástica
• Objetivo simple vs. Multi-objetivo

4

Introducción

Búsqueda Global Heurística

6

Búsqueda de grafo versus de árbol

- Lista de nodos abiertos

a.k.a. Conjunto frontera

- Lista de nodos abiertos

a.k.a. Conjunto frontera

​

- Lista de nodos cerrados

a.k.a. Conjunto explorado

Recuerda caminos para evitar volver a recorrerlos

Espacio de búsqueda supuesto

Búsqueda global con heurística

• Utilizan información específica del problema para seleccionar el orden de expansión / exploración de los nodos�
• Para seleccionar el siguiente nodo a explorar, utilizan una función f(n) que incluye como componente una �función heurística h(n): una estimación �del costo para llegar desde el nodo n al �objetivo
• Ej: h(n) = distancia en línea recta

​

7

Búsqueda global con heurística

​

• Un algoritmo general: “Búsqueda por lo mejor”
• Siempre explora el nodo con menor valor f(n)�
• Búsqueda avara (Greedy search):
• f(n) = h(n)
• Siempre explora los nodos que se estima están �más cerca de la meta
• Costo de búsqueda vs. Costo de la solución
• Es incompleta y subóptima: ¿Por qué?�

8

Algoritmo A*

​

• Búsqueda A*
• f(n) = g(n) + h(n)� g(n): costo de ruta desde el nodo raíz hasta el nodo n� h(n): costo estimado desde el nodo n al nodo objetivo�
• Si h satisface ciertas propiedades A* es
• Completo
• Óptimo�
• Es similar a la búsqueda de costo uniforme (búsqueda no informada) pero�usa g(n) + h(n) en vez de solo g(n)

​

​

9

Algoritmo A*

• Búsqueda A*�f(n) = g(n) + h(n)

​

​

​

10

f(n) =

h(n)

g(n) +

Algoritmo A*

• Búsqueda A*�f(n) = g(n) + h(n)

​

​

​

11

f(n) =

h(n)

g(n) +

Algoritmo A*

• Búsqueda A*�f(n) = g(n) + h(n)

​

​

​

12

f(n) =

h(n)

g(n) +

Algoritmo A*

• Búsqueda A*�f(n) = g(n) + h(n)

​

​

​

13

.

.

.

.

.

.

Algoritmo A*

​

• Requisitos de las heurísticas para que el algoritmo sea completo y óptimo
• Admisibilidad: No sobre-estimar el costo real h’(n) que resta para llegar a la meta desde n → h(n) <= h’(n)
• Consistencia (a.k.a. monotonicidad): por cada nodo n y cada sucesor n’, �h(n) <= c(n, n’) + h(n’), donde c(n, n’) es el costo real para llegar de n a n’

​

• Consistente => admisible
• La consistencia se requiere sólo para la búsqueda de grafo.�
• ¿Qué significa que una heurística sea “buena”?
• ¿Qué pasa si las propiedades anteriores no se cumplen?

14

n

n’

h(n)

c(n, n’)

h(n’)

¡Cuidado! h(n)=0 es admisible y consistente

Por eso la búsqueda uniforme es completa y óptima (aunque no tan eficiente como A* en el caso promedio)

Algoritmo A*

• A* sólo puede resolver problemas de búsqueda de rutas?
• Es su uso principal
• Pero hay otros casos
• Ej: Knapsack problem
• Problema de optimización combinatoria�
• Dado un conjunto de ítems con peso y valor,�definir la cantidad de cada uno a incluir para�maximizar el valor sin superar el límite de peso

15

Preguntas? �Opiniones?