![Page 1: Búsquedas basadas en Heurísticasiolmos/ia/Sesion5_Busquedas2.pdf · Búsquedas basadas en Heurísticas Heurística Técnica que mejora la eficiencia de un proceso de búsqueda posiblementeproceso](https://reader036.vdocumento.com/reader036/viewer/2022062403/5fd38104497c3f52a404501c/html5/thumbnails/1.jpg)
21/10/2009
1
Búsquedas basadas en qHeurísticas
Heurística
Técnica que mejora la eficiencia de un proceso de búsqueda posiblementeproceso de búsqueda, posiblemente sacrificando completez, pero ahorrando tiempo de búsqueda.Ej. Guía de turistas.
![Page 2: Búsquedas basadas en Heurísticasiolmos/ia/Sesion5_Busquedas2.pdf · Búsquedas basadas en Heurísticas Heurística Técnica que mejora la eficiencia de un proceso de búsqueda posiblementeproceso](https://reader036.vdocumento.com/reader036/viewer/2022062403/5fd38104497c3f52a404501c/html5/thumbnails/2.jpg)
21/10/2009
2
Heurística
Ayuda a evitar una explosión combinatoriaAyuda a evitar una explosión combinatoria.Rara vez se necesita obtener la solución óptima (lugar de estacionamiento).Aunque las aproximaciones obtenidas por una heurística pueden no ser buenas en el peor caso, éste rara vez se presenta en el mundo real.Comprender por qué funciona una heurística o porComprender por qué funciona una heurística, o por qué no, ayuda a comprender el problema.
Búsquedas heurísticas
Se utilizan básicamente en dos situaciones:Un problema no tiene soluciones conocidasUn problema no tiene soluciones conocidas.Un problema tiene una solución precisa pero tiene un costo computacional prohibitivo.
![Page 3: Búsquedas basadas en Heurísticasiolmos/ia/Sesion5_Busquedas2.pdf · Búsquedas basadas en Heurísticas Heurística Técnica que mejora la eficiencia de un proceso de búsqueda posiblementeproceso](https://reader036.vdocumento.com/reader036/viewer/2022062403/5fd38104497c3f52a404501c/html5/thumbnails/3.jpg)
21/10/2009
3
Búsquedas heurísticas
• NO es infalible.C i t d t• Consisten en dos partes:– La medida heurística.– Un algoritmo que usa la medida para buscar en el espacio de
estados. Heurística f(n) = g(n), costo uniforme
f(n) = h(n), búsqueda heurística puraf(n) = g(n) + h(n), algoritmo A*
¿qué camino seguir?
Opciones ordenadas conformef(n)
Técnicas heurísticas
Best-first search.A*Hill climbing.Recocido simulado.ACO
![Page 4: Búsquedas basadas en Heurísticasiolmos/ia/Sesion5_Busquedas2.pdf · Búsquedas basadas en Heurísticas Heurística Técnica que mejora la eficiencia de un proceso de búsqueda posiblementeproceso](https://reader036.vdocumento.com/reader036/viewer/2022062403/5fd38104497c3f52a404501c/html5/thumbnails/4.jpg)
21/10/2009
4
Búsqueda Mejor el Primeroq j
Best First Search
Búsqueda el primero mejor / “BúsquedaBúsqueda el primero mejor / Búsqueda Preferentemente por lo mejor”Estrategia de Control Sistemática.Combina ventajas de:
Depht First Search.Breadht First Search
![Page 5: Búsquedas basadas en Heurísticasiolmos/ia/Sesion5_Busquedas2.pdf · Búsquedas basadas en Heurísticas Heurística Técnica que mejora la eficiencia de un proceso de búsqueda posiblementeproceso](https://reader036.vdocumento.com/reader036/viewer/2022062403/5fd38104497c3f52a404501c/html5/thumbnails/5.jpg)
21/10/2009
5
Best First Search
DESCRIPCIÓNSelecciona siempre el nodo más “prometedor”Posición en el árbol: No es tomada en cuenta.Uso de información -> Funciones deUso de información Funciones de Evaluación
Best First Search
VENTAJA
Llega a la solución sin expandirse completamente.
DESVENTAJA
El camino no es necesariamente el más óptimo
![Page 6: Búsquedas basadas en Heurísticasiolmos/ia/Sesion5_Busquedas2.pdf · Búsquedas basadas en Heurísticas Heurística Técnica que mejora la eficiencia de un proceso de búsqueda posiblementeproceso](https://reader036.vdocumento.com/reader036/viewer/2022062403/5fd38104497c3f52a404501c/html5/thumbnails/6.jpg)
21/10/2009
6
Best First Search
ÁRBOL A EXPLORAR
H
A C
20
1614
D E G J
B
9
3 6
5 812
3
K L
F 0
![Page 7: Búsquedas basadas en Heurísticasiolmos/ia/Sesion5_Busquedas2.pdf · Búsquedas basadas en Heurísticas Heurística Técnica que mejora la eficiencia de un proceso de búsqueda posiblementeproceso](https://reader036.vdocumento.com/reader036/viewer/2022062403/5fd38104497c3f52a404501c/html5/thumbnails/7.jpg)
21/10/2009
7
ÁRBOL A EXPLORAR
H20
Open: H (20)
ÁRBOL A EXPLORAR
H20
A C
1614
Open: A (14) C (16)
![Page 8: Búsquedas basadas en Heurísticasiolmos/ia/Sesion5_Busquedas2.pdf · Búsquedas basadas en Heurísticas Heurística Técnica que mejora la eficiencia de un proceso de búsqueda posiblementeproceso](https://reader036.vdocumento.com/reader036/viewer/2022062403/5fd38104497c3f52a404501c/html5/thumbnails/8.jpg)
21/10/2009
8
ÁRBOL A EXPLORAR
H20
A C
1614
D E
9 5
Open: D (9) E(5) C(16)
ÁRBOL A EXPLORAR
H20
A C
1614
D E
9 5
Open: D(9) C(16)
![Page 9: Búsquedas basadas en Heurísticasiolmos/ia/Sesion5_Busquedas2.pdf · Búsquedas basadas en Heurísticas Heurística Técnica que mejora la eficiencia de un proceso de búsqueda posiblementeproceso](https://reader036.vdocumento.com/reader036/viewer/2022062403/5fd38104497c3f52a404501c/html5/thumbnails/9.jpg)
21/10/2009
9
ÁRBOL A EXPLORAR
H20
A C
1614
D E
9 5
3 6
Open: K(3) L(6)
K L
C(16)
ÁRBOL A EXPLORAR
H20
A C
1614
D E
9 5
3 6
Open: L(6) C(16)
K L
![Page 10: Búsquedas basadas en Heurísticasiolmos/ia/Sesion5_Busquedas2.pdf · Búsquedas basadas en Heurísticas Heurística Técnica que mejora la eficiencia de un proceso de búsqueda posiblementeproceso](https://reader036.vdocumento.com/reader036/viewer/2022062403/5fd38104497c3f52a404501c/html5/thumbnails/10.jpg)
21/10/2009
10
ÁRBOL A EXPLORAR
H20
A C
1614
D E
9 5
3 6
Open: F(0) C(16)
K L
F 0
Best First Search: Algoritmo
1. Open Estado Inicial2. Si Open es vacio, retornar fracazo. En caso
contrario1. X extraer nodo mínimo de Open usando “f”
3. Si X es solución, retornar el camino desde la raíz hasta X. En caso contrario
1. Open Open ∪ {sucesores de X no expandidos}
4. Ir a paso 2
![Page 11: Búsquedas basadas en Heurísticasiolmos/ia/Sesion5_Busquedas2.pdf · Búsquedas basadas en Heurísticas Heurística Técnica que mejora la eficiencia de un proceso de búsqueda posiblementeproceso](https://reader036.vdocumento.com/reader036/viewer/2022062403/5fd38104497c3f52a404501c/html5/thumbnails/11.jpg)
21/10/2009
11
Función de Evaluación: BFS
BFS puede utilizar de forma básica dos funciones de evaluaciónfunciones de evaluación
f(n) = g(n): suma de los costos desde la raíz hasta nf(n) = h(n): estimación de costo mínimo desde n h t l ióhasta una solución
BFS: Análisis
f(n) = g(n)S d d id d l dSe expande un nodo considerando un valor de costo ya conocido (no es una aproximación)El algoritmo es completo y óptimo, ya que encontrará la mejor solución en grafos finitos
f(n) = h(n)N ti t l j l ióNo garantiza que se encuentre la mejor soluciónSe comporta como un algoritmo no completo en grafos infinitos
![Page 12: Búsquedas basadas en Heurísticasiolmos/ia/Sesion5_Busquedas2.pdf · Búsquedas basadas en Heurísticas Heurística Técnica que mejora la eficiencia de un proceso de búsqueda posiblementeproceso](https://reader036.vdocumento.com/reader036/viewer/2022062403/5fd38104497c3f52a404501c/html5/thumbnails/12.jpg)
21/10/2009
12
A*
Algoritmo basado en BFSFunción de evaluación
f(n) = g(n) + h(n)
Resolver el problema del 8-puzzle mediante un algoritmo BFS genérico teniendo en cuenta los siguientes puntos
A* – Ejemplo #2
g p
Estado Final1 2 38 4
Estado inicial2 8 3
1 4 8 - 47 6 5
- 1 47 6 5
![Page 13: Búsquedas basadas en Heurísticasiolmos/ia/Sesion5_Busquedas2.pdf · Búsquedas basadas en Heurísticas Heurística Técnica que mejora la eficiencia de un proceso de búsqueda posiblementeproceso](https://reader036.vdocumento.com/reader036/viewer/2022062403/5fd38104497c3f52a404501c/html5/thumbnails/13.jpg)
21/10/2009
13
A* – Ejemplo 2
Reglas:
2 8 3- 1 4
Reglas:•g(n) = 1 por arco recorrido •h(n) = hsimple(n), es decir, el número de celdas que se encuentran mal colocadas incluyendo la posición vacía. •Orden de aplicación de
g(n) =
7 6 5Orden de aplicación de
operadores: Arriba, Abajo, Izquierda, Derecha •En caso de empate, seleccionar el nodo más antiguo.
h(n) = 4 fichas
A* – Ejemplo 2
2 8 31 ‐ 4
2 8 3- 1 47 6 5
7 6 5
- 8 32 1 47 6 5 h(n) = 4 fichas
h(n) = 4 fichas
h(n) = 5 fichas
7 6 57 6 5
2 8 37 1 4- 6 5
![Page 14: Búsquedas basadas en Heurísticasiolmos/ia/Sesion5_Busquedas2.pdf · Búsquedas basadas en Heurísticas Heurística Técnica que mejora la eficiencia de un proceso de búsqueda posiblementeproceso](https://reader036.vdocumento.com/reader036/viewer/2022062403/5fd38104497c3f52a404501c/html5/thumbnails/14.jpg)
21/10/2009
14
A* – Ejemplo 2
2 8 3 2 8 31 6 4
1 ‐ 47 6 5
1 6 47 - 5
2 ‐ 31 8 47 6 5 h(n) = 4 fichas
h(n) = 5 fichas
- 8 3
2 8 3- 1 47 6 5
h(n) = 5 fichas
7 6 5
2 8 31 4 ‐
7 6 5
2 1 47 6 5
2 8 37 1 4- 6 5
A* – Ejemplo#2
2 8 31 ‐ 47 6 5
2 8 3
1 6 4
7 - 5
2 ‐ 3
1 8 4
7 6 5
2 8 3
h(n) = 4 fichas
- 8 32 1 47 6 5
2 8 3- 1 47 6 5
1 4 ‐
7 6 5
8 ‐ 3
2 1 4
7 6 57 6 52 8 37 1 4- 6 5
![Page 15: Búsquedas basadas en Heurísticasiolmos/ia/Sesion5_Busquedas2.pdf · Búsquedas basadas en Heurísticas Heurística Técnica que mejora la eficiencia de un proceso de búsqueda posiblementeproceso](https://reader036.vdocumento.com/reader036/viewer/2022062403/5fd38104497c3f52a404501c/html5/thumbnails/15.jpg)
21/10/2009
15
A* – Ejemplo#2
2 8 31 ‐ 47 6 5
2 8 3
1 6 4
7 - 5
2 ‐ 3
1 8 4
7 6 5
2 8 3
2 8 31 4
7 6 5
1 4 ‐
7 6 5
- 8 32 1 47 6 5
2 8 3
8 ‐ 3
2 1 4
7 6 5
h(n) = 6 fichas
2 8 37 1 4- 6 5
2 8 3
7 1 4
6 - 5
A* – Ejemplo#2
2 8 31 4
2 8 3
1 6 4
7 - 5
2 ‐ 3
2 3 -
1 8 4
7 6 51 ‐ 47 6 5
2 8 31 4
7 6 52 8 3
1 4 ‐
7 6 5
2 31 8 47 6 5
- 2 3
1 8 4
7 6 5
- 8 32 1 47 6 5
2 8 3
7 1 4
- 6 5
8 ‐ 3
2 1 4
7 6 5
2 8 3
7 1 4
6 - 5
![Page 16: Búsquedas basadas en Heurísticasiolmos/ia/Sesion5_Busquedas2.pdf · Búsquedas basadas en Heurísticas Heurística Técnica que mejora la eficiencia de un proceso de búsqueda posiblementeproceso](https://reader036.vdocumento.com/reader036/viewer/2022062403/5fd38104497c3f52a404501c/html5/thumbnails/16.jpg)
21/10/2009
16
A* – Ejemplo#2
2 8 31 4
2 8 3
1 6 4
7 - 5
2 ‐ 3
2 3 -
1 8 4
7 6 5
1 ‐ 47 6 5
2 8 31 4
7 6 5
2 8 3
1 4 ‐
7 6 5
- 8 3
1 8 4
7 6 5- 2 3
1 8 4
7 6 5
8 ‐ 3
8 3 -
2 1 4
7 6 5- 8 32 1 47 6 5
2 8 3
7 1 4
- 6 5
2 8 3
7 1 4
6 - 5
8 3
2 1 4
7 6 5
7 6 5
8 1 3
2 - 4
7 6 5
A* – Ejemplo#2
2 8 31 4
2 8 3
1 6 4
7 - 5
2 ‐ 3
2 3 -
1 8 4
7 6 5
- 2 3 1 2 31 ‐ 47 6 5
2 8 31 4
7 6 5
2 8 3
1 4 ‐
7 6 5
- 8 3
1 8 4
7 6 5 1 8 4
7 6 5
8 3 -
2 1 4
- 8 4
7 6 5
8 ‐ 3- 8 32 1 47 6 5
2 8 3
7 1 4
- 6 5
2 8 3
7 1 4
6 - 5
7 6 5
8 1 3
2 - 4
7 6 5
8 3
2 1 4
7 6 5
![Page 17: Búsquedas basadas en Heurísticasiolmos/ia/Sesion5_Busquedas2.pdf · Búsquedas basadas en Heurísticas Heurística Técnica que mejora la eficiencia de un proceso de búsqueda posiblementeproceso](https://reader036.vdocumento.com/reader036/viewer/2022062403/5fd38104497c3f52a404501c/html5/thumbnails/17.jpg)
21/10/2009
17
A* – Ejemplo#2
2 8 31 4
2 8 3
1 6 4
7 - 5
2 ‐ 3
2 3 -
1 8 4
7 6 5
1 2 3
- 8 4
7 6 5- 2 3
1 ‐ 47 6 5
2 8 31 4
7 6 5
2 8 3
1 4 ‐
7 6 5
- 8 32 1 4
1 8 4
7 6 51 8 4
7 6 5
8 3 -
2 1 4
7 6 5
8 1 38 ‐ 3
2 1 4
8 1 3
2 4 -
8 1 3
- 2 4
7 6 5
2 1 47 6 5
2 8 3
7 1 4
- 6 5
2 8 3
7 1 4
6 - 5
8 1 3
2 - 4
7 6 5
2 1 4
7 6 5
8 1 3
2 6 4
7 - 5
7 6 5
A* – Ejemplo#22 3 -
1 8 4
7 6 5
- 2 32 8 31 4
2 8 3
1 6 4
7 - 5
2 ‐ 3
2 3 -
1 8 4
7 6 5
- 2 3 1 2 31 2 31 8 4
7 6 5
8 3 -
2 1 4
8 1 3
- 2 4
7 6 5
1 ‐ 47 6 5
2 8 31 4
7 6 5
2 8 3
1 4 ‐
7 6 5
- 8 32 1 4
1 8 4
7 6 51 8 4
7 6 5
8 ‐ 3
2 1 4
1 2 3
8 - 4
7 6 5
1 2 3
- 8 4
7 6 5
7 6 5
8 1 3
2 6 4
7 - 5
8 1 3
2 4 -
7 6 5
8 1 3
2 - 4
7 6 5
2 1 47 6 5
2 8 3
7 1 4
- 6 5
2 8 3
7 1 4
6 - 5
2 1 4
7 6 5
![Page 18: Búsquedas basadas en Heurísticasiolmos/ia/Sesion5_Busquedas2.pdf · Búsquedas basadas en Heurísticas Heurística Técnica que mejora la eficiencia de un proceso de búsqueda posiblementeproceso](https://reader036.vdocumento.com/reader036/viewer/2022062403/5fd38104497c3f52a404501c/html5/thumbnails/18.jpg)
21/10/2009
18
A* – Ejemplo#2
- 2 32 8 31 4
2 ‐ 3 - 2 3 1 2 31 2 31 8 4
7 6 5
1 ‐ 47 6 5
2 8 31 4
7 6 5
1 8 4
7 6 51 8 4
7 6 5
1 2 3
8 - 4
7 6 5
1 2 3
- 8 4
7 6 5