PDF de programación - 2 BH2 Busqueda heuristica

Búsqueda Heurística

Búsqueda Heurística

Introducción

Supone la existencia de una función de evaluación que debe medir la
distancia estimada al (a un) objetivo (h(n))
Esta función de evaluación se utiliza para guiar el proceso haciendo
que en cada momento se seleccione el estado o las operaciones más
prometedores
No siempre se garantiza encontrar una solución (de existir ésta)
No siempre se garantiza encontrar la solución más próxima (la que se
encuentra a una distancia, número de operaciones menor)
Existen múltiples algoritmos:

Branch and Bound, Best First Search
A, A∗
IDA∗
Búsqueda local (Hill climbing, Simulated annealing, Alg. Genéticos)

c b e a (LSI-FIB-UPC)

Inteligencia Artificial

Curso 2011/2012

1 / 30

Branch and Bound

Búsqueda Heurística

Introducción

Ramificación y acotación
Generaliza BFS, DFS
Se guarda para cada estado el coste (hasta el momento) de llegar
desde el estado inicial a dicho estado. Guarda el coste mínimo global
hasta el momento
Deja de explorar una rama cuando su coste es mayor que el mínimo
actual
Si el coste de los nodos es uniforme equivale a una búsqueda por
niveles

c b e a (LSI-FIB-UPC)

Inteligencia Artificial

Curso 2011/2012

2 / 30

Greedy Best First

Búsqueda Heurística

Introducción

Algoritmo: Greedy Best First
Est_abiertos.insertar(Estado inicial)
Actual← Est_abiertos.primero()
mientras no es_final?(Actual) y no Est_abiertos.vacía?() 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

La estructura de abiertos es una cola con prioridad
La prioridad la marca la funcion de estimación (coste del camino que falta
hasta la solucion)
En cada iteración se escoge el nodo mas cercano a la solucion (el primero de
la cola), esto provoca que no se garantice la solucion optima

c b e a (LSI-FIB-UPC)

Inteligencia Artificial

Curso 2011/2012

3 / 30

Importancia del estimador

Búsqueda Heurística

Heurísticos

Operaciones:
- situar un bloque libre en la mesa
- situar un bloque libre sobre otro bloque libre

Heurístico 1:
- sumar 1 por cada bloque que esté colocado sobre
el bloque que debe
- restar 1 si el bloque no está colocado sobre el que
debe

Heurístico 2:
- si la estructura de apoyo es correcta sumar 1 por
cada bloque de dicha estructura
- si la estructura de apoyo no es correcta restar 1
por cada bloque de dicha estructura

c b e a (LSI-FIB-UPC)

Inteligencia Artificial

Curso 2011/2012

4 / 30

AHGFEDCBEstado InicialH1=4H2=−28AHGFEDCBEstado FinalH1=8H2= 28 (= 7+6+5+4+3+2+1)Importancia del estimador

Búsqueda Heurística

Heurísticos

c b e a (LSI-FIB-UPC)

Inteligencia Artificial

Curso 2011/2012

5 / 30

GFEDCBAHH1=4H2=−14GFEDCBAHH1=4H2=−16HGFEDCBAH1=6H2=−21AHGFEDCBH1=4H2=−28Estado InicialHeurísticos

Búsqueda Heurística

Heurísticos

Posibles heurísticos (estimadores del coste a la solución)

h(n) = w (n) = #desclasificados
h(n) = p(n) = suma de distancias a la posición final
h(n) = p(n) + 3 · s(n)
donde s(n) se obtiene recorriendo las posiciones no centrales y si una
ficha no va seguida por su sucesora sumar 2, si hay ficha en el centro
sumar 1

c b e a (LSI-FIB-UPC)

Inteligencia Artificial

Curso 2011/2012

6 / 30

28345716Estado Inicial34571268Estado FinalCostes

Búsqueda Heurística

Heurísticos

Coste de un arco

Coste de un camino

c(ni , nj ) > 0

C =Pj−1

x =i c(nx , nx +1)

Coste del camino mínimo K (ni , nj ) = minl

k=1Ck

Si nj es un nodo terminal
Si ni es un nodo inicial
Si existen varios nodos terminales T = {t1, . . . , tl}
Si existen varios nodos iniciales S = {s1, . . . , sl}

h∗(ni ) = K (ni , nj )
g∗(nj ) = K (ni , nj )
h∗(ni ) = minl
g∗(nj ) = minl

k=1K (ni , tk )
k=1K (sk , nj )

c b e a (LSI-FIB-UPC)

Inteligencia Artificial

Curso 2011/2012

7 / 30

injninjnjninCCC...12lBúsqueda A∗

Búsqueda Heurística

Búsqueda A∗

La función de evaluación tiene dos componentes:

1 coste para ir desde el (un) inicio al nodo actual
2 coste (estimado) para ir desde el nodo actual a una solución

f (n) = g(n) + h(n)

f es un valor estimado del coste total del camino que pasa por n
h (heurístico) es un valor estimado de lo que falta para llegar desde n
al (a un) objetivo
g es un coste real (lo gastado por el camino más corto conocido hasta
n)

La preferencia es siempre del nodo con menor f , en caso de empate, la
preferencia es del nodo con menor h.

c b e a (LSI-FIB-UPC)

Inteligencia Artificial

Curso 2011/2012

8 / 30

Búsqueda A∗

Búsqueda Heurística

Búsqueda A∗

c b e a (LSI-FIB-UPC)

Inteligencia Artificial

Curso 2011/2012

9 / 30

g(n)h(n)f(n)=g(n)+h(n)nnnBúsqueda A∗

Búsqueda Heurística

Búsqueda A∗

Con esta función podemos variar el comportamiento del algoritmo

Si ∀n h(n) = 0, todo estará controlado por g (estaremos en presencia
de un algoritmo de Branch & Bound)
Si ∀n h(n) = 0 y además el coste de todos los arcos es 1 estaremos
realizando una búsqueda en anchura. Si dicho coste fuera 0, la
búsqueda sería aleatoria
Al ser h una estimación del verdadero coste h∗, cuanto más se
aproxime h a h∗ mayor será la tendencia a explorar en profundidad. Si
h = h∗ entonces A∗ converge directamente hacia el objetivo

Se puede demostrar que si h(n) es un minorante del coste real h∗(n), es
decir si ∀n h(n) ≤ h∗(n) A∗ encontrará (de haberlo) un camino óptimo.

c b e a (LSI-FIB-UPC)

Inteligencia Artificial

Curso 2011/2012

10 / 30

El algoritmo A∗

Búsqueda Heurística

Búsqueda A∗

Algoritmo: A*
Est_abiertos.insertar(Estado inicial)
Actual ← Est_abiertos.primero()
mientras no es_final?(Actual) y no Est_abiertos.vacía?() 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

La estructura de abiertos es una cola con prioridad
La prioridad la marca la función de estimación (f (n) = g(n) + h(n))
En cada iteración se escoge el mejor camino (el primero de la cola)
¡Es el mismo algoritmo que el Best First!

c b e a (LSI-FIB-UPC)

Inteligencia Artificial

Curso 2011/2012

11 / 30

Búsqueda Heurística

Búsqueda A∗

Tratamiento de repetidos

Si es un repetido que está en la estructura de abiertos

Si su coste es menor substituimos el coste por el nuevo, esto podrá
variar su posición en la estructura de abiertos
Si su coste es igual o mayor nos olvidamos del nodo

Si es un repetido que esta en la estructura de cerrados

Si su coste es menor reabrimos el nodo insertándolo en la estructura de
abiertos con el nuevo coste ¡Atención! No hacemos nada con sus
sucesores, ya se reabrirán si hace falta
Si su coste es mayor o igual nos olvidamos del nodo

c b e a (LSI-FIB-UPC)

Inteligencia Artificial

Curso 2011/2012

12 / 30

A∗ Ejemplo

Búsqueda Heurística

Búsqueda A∗

Abiertos

Cerrados

0+2

0+2

1+1

2+1

3+1

1+1

2+1

3+1

4+1

4+1 → 3+1

5+0

4+0

1+3

2+2

3+2

4+1

5+0

c b e a (LSI-FIB-UPC)

Inteligencia Artificial

Curso 2011/2012

13 / 30

A∗ Ejemplo

Búsqueda Heurística

Búsqueda A∗

Abiertos

Cerrados

0+2

0+21+1
1+1
1+3

1

0+2

1+1

2+1

3+1

1+1

2+1

3+1

4+1

4+1 → 3+1

5+0

4+0

1+3

2+2

3+2

4+1

5+0

c b e a (LSI-FIB-UPC)

Inteligencia Artificial

Curso 2011/2012

13 / 30

A∗ Ejemplo

Búsqueda Heurística

Búsqueda A∗

Abiertos

Cerrados

0+21+1
1+1
1+1
2+1
1+3
1+3

0+20+2
1+1

1

0+2

1+1

2+1

3+1

2

1+1

2+1

3+1

4+1

4+1 → 3+1

5+0

4+0

1+3

2+2

3+2

4+1

5+0

c b e a (LSI-FIB-UPC)

Inteligencia Artificial

Curso 2011/2012

13 / 30

A∗ Ejemplo

Búsqueda Heurística

Búsqueda A∗

Abiertos

Cerrados

0+21+1
1+1
2+1
1+1
2+1
2+1
1+3
1+3
1+3

0+20+2
0+2
1+1
1+1
1+1

1

3

0+2

1+1

2+1

3+1

2

1+1

2+1

3+1

4+1

4+1 → 3+1

5+0

4+0

1+3

2+2

3+2

4+1

5+0

c b e a (LSI-FIB-UPC)

Inteligencia Artificial

Curso 2011/2012

13 / 30

A∗ Ejemplo

Búsqueda Heurística

Búsqueda A∗

Abiertos

Cerrados

0+21+1
1+1
2+1
2+1
1+1
2+1
2+1
3+1
1+3
1+3
1+3
1+3

0+20+2
0+2
0+2
1+1
1+1
1+1
1+1
1+1
2+1

1

3

0+2

1+1

2+1

3+1

2

4

1+1

2+1

3+1

4+1

4+1 → 3+1

5+0

4+0

1+3

2+2

3+2

4+1

5+0

c b e a (LSI-FIB-UPC)

Inteligencia Artificial

Curso 2011/2012

13 / 30

A∗ Ejemplo

Búsqueda Heurística

Búsqueda A∗

Abiertos

Cerrados

0+21+1
1+1
2+1
2+1
3+1
1+1
2+1
2+1
3+1
3+1
1+3
1+3
1+3
1+3
1+3

0+20+2
0+2
0+2
0+2
1+1
1+1
1+1
1+1
1+1
1+1
1+1
2+1
2+1
2+1

1

3

5

0+2

1+1

2+1

3+1

2

4

1+1

2+1

3+1

4+1

4+1 → 3+1

5+0

4+0

1+3

2+2

3+2

4+1

5+0

c b e a (LSI-FIB-UPC)

Inteligencia Artificial

Curso 2011/2012

13 / 30

A∗ Ejemplo

Búsqueda Heurística

Búsqueda A∗

Abiertos

Cerrados

0+21+1
1+1
2+1
2+1
3+1
3+1
1+1
2+1
2+1
3+1
3+1
1+3
1+3
1+3
1+3
1+3
1+3
4+1

0+20+2
0+2
0+2
0+2
0+2
1+1
1+1
1+1
1+1
1+1
1+1
1+1
1+1
1+1
2+1
2+1
2+1
2+1
2+1
3+1

1

3

5

0+2

1+1

2+1

3+1

2

4

6

1+1

2+1

3+1

4+1

4+1 → 3+1

5+0

4+0

1+3

2+2

3+2

4+1

5+0

c b e a (LSI-FIB-UPC)

Inteligencia Artificial

Curso 2011/2012

13 / 30

A∗ Ejemplo

Búsqueda Heurística

Búsqueda A∗

Abiertos

Cerrados

0+21+1
1+1
2+1
2+1
3+1
3+1
1+3
1+1
2+1
2+1
3+1
3+1
1+3
4+1
1+3
1+3
1+3
1+3
1+3
4+1
4+1

0+20+2
0+2
0+2
0+2
0+2
0+2
1+1
1+1
1+1
1+1
1+1
1+1
1+1
1+1
1+1
1+1
1+1
2+1
2+1
2+1
2+1
2+1
2+1
2+1
3+1
3+1
3+1

1

3

5

7

0+2

1+1

2+1

3+1

2

4

6

1+1

2+1

3+1

4+1

4+1 → 3+1

5+0

4+0

1+3

2+2

3+2

4+1

5+0

c b e a (LSI-FIB-UPC)

Inteligencia Artificial

Curso 2011/2012

13 / 30

A∗ Ejemplo

Búsqueda Heurística

Búsqueda A∗

1

3

5

7

0+2

1+1

2+1

3+1

2

4

6

1+1

2+1

3+1

4+1

4+1 → 3+1

5+0

4+0

8

1+3

2+2

3+2

4+1

5+0

Abiertos

Cerrados

0+21+1
1+1
2+1
2+1
3+1
3+1
1+3
2+2
1+1
2+1
2+1
3+1
3+1
1+3
4+1
4+1
1+3
1+3
1+3
1+3
1+3
4+1
4+1
4+1

0+20+2
0+2
0+2
0+2
0+2
0+2
0+2
1+1
1+1
1+1
1+1
1+1
1+1
1+1
1+1
1+1
1+1
1+1
1+1
1+1
2+1
2+1
2+1
2+1
2+1
2+1
2+1
2+1
2+1
3+1
3+1
3+1
3+1
3+1
1+3

c b e a (LSI-FIB-UPC)

Inteligencia Artificial

Curso 2011/2012

13 / 30

A∗ Ejemplo

Búsqueda Heurística

Búsqueda A∗

1

3

5

7

0+2

1+1

2+1

3+1

2

4

6

1+1