Algoritmo De Busqueda A Ciegas En Mapas De Juegos

Búsqueda Heurística

IIIA-CSIC

Algoritmos
• Algoritmo: procedimiento computacional que termina
• si en algún caso no termina, hay que especificarlo
• Características: algoritmo A(x) → y | fallo
• correcto: y es lo que A dice que es
• completo:
• satisfacción: y es solución
• optimización: y es la solución óptima

Búsqueda Heurística

2

Complejidad
A l g o r i t m o A ( x ), |x | = n
Coste en tiempo: pasos que da A en función de n, caso peor
• polinomio de n:
n2 + 2n + 3 → O(n2)
• exponencial:

3n + nlog(n)

→ O(3n)

Coste en espacio: memoria de A en función de n, caso peor
• polinomio de n:
2n 3 + 4n
→ O(n3)
• exponencial:

2n + nlog(n) → O(2n)

nos quedamos con
el término dominante
Búsqueda Heurística

3

Complejidad caso peor / caso medio
•Caso peor:

peor opción en tiempo / memoria

• Caso medio: coste medio en ejemplares reales
• Si caso peor no es frecuente:
• complejidad caso peor no es una estimación realista y...
... una complejidad alta no nos asusta

• Si el caso peor cercano al caso medio:
• la función de complejidad va a determinar la bondad del
a l g o r i tm o
Búsqueda Heurística

4

Búsqueda ciega
•Búsqueda ciega (fuerza bruta): sin función heurística
• Algoritmos:
• Busqueda en anchura (BFS)
• Búsqueda en profundidad (DFS)
• Profundización iterativa (ID)

• Evaluación:
• calidad solución: ¿óptimo?
• coste en tiempo: proporcional a los nodos generados
• coste en memoria: proporcional a los nodos almacenados
Búsqueda Heurística

5

Nodo: operaciones
• Generación: cuando se crea• Expansión: cuando se generan sus sucesores

nodo

¿es solución?

generación
de sucesores
expansión

no
generación

Búsqueda Heurística

6

Búsqueda en árbol
Árbol de búsqueda:
– finito: profundidad d
– factor de ramificación b (uniforme)
d
...

b

soluciones
Búsqueda Heurística

7

Esquema de búsqueda ciega
1. L ← lista de nodos iniciales del problema.
L contienela lista de nodos no visitados.
2. Si L vacía, fallo, stop.
Sino, n ← extrae un nodo de L (n se elimina de L)
3. Generar los sucesores de n. Si un sucesor es solución,
retornar el camino desde la raíz, stop.
4. Sino, añadir a L los sucesores de n,
etiquetando sus respectivos caminos desde la raíz. Ir a 2.
Opciones:
• extrae un nodo de L
• añadir a L
• sucesores de n

¿al principio? ¿alfinal ?
¿al principio? ¿al final ?
¿todos? ¿unos pocos?
Búsqueda Heurística

8

Búsqueda en anchura
Algoritmo BFS (breadth-first search)
1. Lista L ← nodo raíz
2. Si L vacía, fallo, stop.
Sino, n ← extrae-primero(L).
3. Generar los sucesores de n. Si alguno es solución,
retornar el camino desde la raíz, stop.
4. Sino, añadir al final de L todos los sucesores de n,
etiquetando cadasucesor con su camino desde la raíz.
Ir a 2.
Búsqueda Heurística

9

Búsqueda en anchura (II)
0
1

2

3

4

5

6

7

8

9

10

11

12

13

14

15 16

17 18

19 20

21 22

23 24

25 26

27 28

29 30

orden de generación
Búsqueda Heurística

10

Búsqueda en anchura (III)
• Calidad: se visita por niveles → encuentra la solución
más cercanaa la raíz
• Tiempo: proporcional a los nodos generados

nivel

nodos

0

1

1

b

2

b d+ 1 - 1

b d+ 1

b2

1 + b + b2 + ... + bd =

b-1

≈

b-1

Complejidad temporal: O(bd)

• Espacio: nodos memorizados bd
d

bd

Complejidad espacial: O(bd)
Búsqueda Heurística

11

Búsqueda en anchura IV
1
2

b d -1

d-1
d
caso mejor

caso peor

b d -1 + bbd
caso medio
1/2 b d
Búsqueda Heurística

12

Complejidad espacial exponencial

¡¡

!!

• Velocidad generación nodos: 107 por seg
• Memoria disponible:
2,5 x 108 nodos
• Si guardamos todos los nodos:

25 seg

• Si guardamos solo el último nivel:
• en cuanto bd > 2,5 108 → memory overflow
• en la práctica, cuestion de minutos
Búsqueda Heurística

13

Búsqueda en...