Métodos de búsqueda respaldados con información. La búsqueda de caminos es un problema que...
-
Upload
trini-cerna -
Category
Documents
-
view
5 -
download
0
Transcript of Métodos de búsqueda respaldados con información. La búsqueda de caminos es un problema que...
![Page 1: Métodos de búsqueda respaldados con información. La búsqueda de caminos es un problema que usualmente se resuelve por medio de algoritmos de búsqueda.](https://reader033.fdocumento.com/reader033/viewer/2022052618/54c3dc5c4979595c308b5d1c/html5/thumbnails/1.jpg)
![Page 2: Métodos de búsqueda respaldados con información. La búsqueda de caminos es un problema que usualmente se resuelve por medio de algoritmos de búsqueda.](https://reader033.fdocumento.com/reader033/viewer/2022052618/54c3dc5c4979595c308b5d1c/html5/thumbnails/2.jpg)
Métodos de búsqueda respaldados con información.
La búsqueda de caminos es un problema que usualmente se resuelve por medio de algoritmos de búsqueda en grafos.
![Page 3: Métodos de búsqueda respaldados con información. La búsqueda de caminos es un problema que usualmente se resuelve por medio de algoritmos de búsqueda.](https://reader033.fdocumento.com/reader033/viewer/2022052618/54c3dc5c4979595c308b5d1c/html5/thumbnails/3.jpg)
En este tipo de problemas conocemos:
El estado inicial
El estado final
Un conjunto de reglas.
![Page 4: Métodos de búsqueda respaldados con información. La búsqueda de caminos es un problema que usualmente se resuelve por medio de algoritmos de búsqueda.](https://reader033.fdocumento.com/reader033/viewer/2022052618/54c3dc5c4979595c308b5d1c/html5/thumbnails/4.jpg)
• Es un algoritmo de búsqueda preferente por lo mejor (best-first) en el que se utiliza f como función heurística y una función h aceptable.
• Es un algoritmo genérico de búsqueda.
• Basa su comportamiento en una función función de evaluaciónde evaluación.
![Page 5: Métodos de búsqueda respaldados con información. La búsqueda de caminos es un problema que usualmente se resuelve por medio de algoritmos de búsqueda.](https://reader033.fdocumento.com/reader033/viewer/2022052618/54c3dc5c4979595c308b5d1c/html5/thumbnails/5.jpg)
Esta función se encuentra compuesta por la siguiente combinación:
La búsqueda por costo uniforme, reduce al mínimo el costo de la ruta, g(n).
La búsqueda avara permite reducir al mínimo el costo de la meta, h(n).
f (n) = g (n) + h (n)
![Page 6: Métodos de búsqueda respaldados con información. La búsqueda de caminos es un problema que usualmente se resuelve por medio de algoritmos de búsqueda.](https://reader033.fdocumento.com/reader033/viewer/2022052618/54c3dc5c4979595c308b5d1c/html5/thumbnails/6.jpg)
inicio
fin
f(n) = costo estimado de la solución mas barata, pasando por n.
![Page 7: Métodos de búsqueda respaldados con información. La búsqueda de caminos es un problema que usualmente se resuelve por medio de algoritmos de búsqueda.](https://reader033.fdocumento.com/reader033/viewer/2022052618/54c3dc5c4979595c308b5d1c/html5/thumbnails/7.jpg)
Esta funcion viene de dos principios:
• Lo mas corto es lo mas rapido (g).
• Para asegurarnos que es la mejor opcion hay que agregar subestimaciones (h).
![Page 8: Métodos de búsqueda respaldados con información. La búsqueda de caminos es un problema que usualmente se resuelve por medio de algoritmos de búsqueda.](https://reader033.fdocumento.com/reader033/viewer/2022052618/54c3dc5c4979595c308b5d1c/html5/thumbnails/8.jpg)
Características de A*
• Siempre termina en grafos finitos.
• Si h(n) es un estimador optimista de h*(n), A* regresa la solución óptima.
• A* es admisible .
Se dice que este tipo de búsqueda es óptima y Se dice que este tipo de búsqueda es óptima y completa.completa.
![Page 9: Métodos de búsqueda respaldados con información. La búsqueda de caminos es un problema que usualmente se resuelve por medio de algoritmos de búsqueda.](https://reader033.fdocumento.com/reader033/viewer/2022052618/54c3dc5c4979595c308b5d1c/html5/thumbnails/9.jpg)
=
![Page 10: Métodos de búsqueda respaldados con información. La búsqueda de caminos es un problema que usualmente se resuelve por medio de algoritmos de búsqueda.](https://reader033.fdocumento.com/reader033/viewer/2022052618/54c3dc5c4979595c308b5d1c/html5/thumbnails/10.jpg)
Incorpora la longitud del camino desde la raíz hasta el estado actual en la función de evaluación h.
Considera si el estado es bueno
Toma en cuenta cómo es el camino usado para alcanzarlo
![Page 11: Métodos de búsqueda respaldados con información. La búsqueda de caminos es un problema que usualmente se resuelve por medio de algoritmos de búsqueda.](https://reader033.fdocumento.com/reader033/viewer/2022052618/54c3dc5c4979595c308b5d1c/html5/thumbnails/11.jpg)
Lista abierta:Lista abierta: contiene los nodos que podrían
formar parte del camino.
Lista cerrada:Lista cerrada: contiene los nodos que ya han
sido examinados y que no hace falta volver a
examinar.
![Page 12: Métodos de búsqueda respaldados con información. La búsqueda de caminos es un problema que usualmente se resuelve por medio de algoritmos de búsqueda.](https://reader033.fdocumento.com/reader033/viewer/2022052618/54c3dc5c4979595c308b5d1c/html5/thumbnails/12.jpg)
Monoticidad
Ruta máxima
Contornos
Optimamente eficiente
![Page 13: Métodos de búsqueda respaldados con información. La búsqueda de caminos es un problema que usualmente se resuelve por medio de algoritmos de búsqueda.](https://reader033.fdocumento.com/reader033/viewer/2022052618/54c3dc5c4979595c308b5d1c/html5/thumbnails/13.jpg)
La cantidad de nodos que están dentro del espacio de búsqueda en el contorno de la meta sigue siendo exponencial a lo largo de toda la solución.
![Page 14: Métodos de búsqueda respaldados con información. La búsqueda de caminos es un problema que usualmente se resuelve por medio de algoritmos de búsqueda.](https://reader033.fdocumento.com/reader033/viewer/2022052618/54c3dc5c4979595c308b5d1c/html5/thumbnails/14.jpg)
Elige el nodo de menor costo
El tiempo de cómputo
![Page 15: Métodos de búsqueda respaldados con información. La búsqueda de caminos es un problema que usualmente se resuelve por medio de algoritmos de búsqueda.](https://reader033.fdocumento.com/reader033/viewer/2022052618/54c3dc5c4979595c308b5d1c/html5/thumbnails/15.jpg)
![Page 16: Métodos de búsqueda respaldados con información. La búsqueda de caminos es un problema que usualmente se resuelve por medio de algoritmos de búsqueda.](https://reader033.fdocumento.com/reader033/viewer/2022052618/54c3dc5c4979595c308b5d1c/html5/thumbnails/16.jpg)
Distancia en línea recta a Bucharest
AradArad 366366 BucharestBucharest 00 CraiovaCraiova 160160 FagarasFagaras 178178 OradeaOradea 380380 PitestiPitesti 9898 Rimnicu VilceaRimnicu Vilcea 193193 SibiuSibiu 253253 TimisoaraTimisoara 329329 ZerindZerind 374374
![Page 17: Métodos de búsqueda respaldados con información. La búsqueda de caminos es un problema que usualmente se resuelve por medio de algoritmos de búsqueda.](https://reader033.fdocumento.com/reader033/viewer/2022052618/54c3dc5c4979595c308b5d1c/html5/thumbnails/17.jpg)
Arad
f(n)=0+366
= 366
Timisoara ZerindSibiu
f(n)=118+329
= 447
f(n)=75+374
= 449
f(n)=140+253
= 393
![Page 18: Métodos de búsqueda respaldados con información. La búsqueda de caminos es un problema que usualmente se resuelve por medio de algoritmos de búsqueda.](https://reader033.fdocumento.com/reader033/viewer/2022052618/54c3dc5c4979595c308b5d1c/html5/thumbnails/18.jpg)
Arad
f(n)=0+366
= 366
Sibiuf(n)=140+253
= 393
Arad FagarasRimnicu VilceaOradea
f(n)=280+366
= 646
f(n)=146+380
= 526
f(n)=239+178
= 417
f(n)=220+193
= 413
![Page 19: Métodos de búsqueda respaldados con información. La búsqueda de caminos es un problema que usualmente se resuelve por medio de algoritmos de búsqueda.](https://reader033.fdocumento.com/reader033/viewer/2022052618/54c3dc5c4979595c308b5d1c/html5/thumbnails/19.jpg)
Arad
f(n)=0+366
= 366
Sibiuf(n)=140+253
= 393
Rimmicu Vilcea
f(n)=220+193
= 413
Pitestif(n)=317+98
= 415
Craiova
f(n)=366+160
= 526
Sibiu
f(n)=300+253
= 553
![Page 20: Métodos de búsqueda respaldados con información. La búsqueda de caminos es un problema que usualmente se resuelve por medio de algoritmos de búsqueda.](https://reader033.fdocumento.com/reader033/viewer/2022052618/54c3dc5c4979595c308b5d1c/html5/thumbnails/20.jpg)
Aradf(n)=0+366
= 366
Sibiu
f(n)=140+253
= 393Rimmicu Vilcea
f(n)=220+193
= 413
Pitesti
f(n)=317+98
= 415
Bucharest
f(n)=418+0
= 418
![Page 21: Métodos de búsqueda respaldados con información. La búsqueda de caminos es un problema que usualmente se resuelve por medio de algoritmos de búsqueda.](https://reader033.fdocumento.com/reader033/viewer/2022052618/54c3dc5c4979595c308b5d1c/html5/thumbnails/21.jpg)
Arad
Arad
Timisoara
FagarasRimnicu VilceaOradea
Zerind
Sibiu PitestiCraiova
Sibiu
Bucharest
f(n) = g(n) + h(n)
f(n)=118+329
= 447
f(n)=280+366
= 646
f(n)=291+380
= 671
f(n)=418+0
= 418
f(n)=239+178
= 417
f(n)=317+98
= 415
f(n)=220+193
= 413
f(n)=366+160
= 526
f(n)=300+253
= 553
f(n)=75+374
= 449
f(n)=140+253
= 393
f(n)=0+366
= 366
![Page 22: Métodos de búsqueda respaldados con información. La búsqueda de caminos es un problema que usualmente se resuelve por medio de algoritmos de búsqueda.](https://reader033.fdocumento.com/reader033/viewer/2022052618/54c3dc5c4979595c308b5d1c/html5/thumbnails/22.jpg)
Búsqueda limitada Búsqueda limitada por la capacidad de por la capacidad de
la memoriala memoria
![Page 23: Métodos de búsqueda respaldados con información. La búsqueda de caminos es un problema que usualmente se resuelve por medio de algoritmos de búsqueda.](https://reader033.fdocumento.com/reader033/viewer/2022052618/54c3dc5c4979595c308b5d1c/html5/thumbnails/23.jpg)
En esta sección se exploraran dos algoritmos diseñados para conservar
la memoria:
BUSQUEDA A* por PROFUNDIZACION
ITERATIVA (A*PI)
BUSQUEDA A* ACOTA por MEMORIA
SIMPLIFICADA
![Page 24: Métodos de búsqueda respaldados con información. La búsqueda de caminos es un problema que usualmente se resuelve por medio de algoritmos de búsqueda.](https://reader033.fdocumento.com/reader033/viewer/2022052618/54c3dc5c4979595c308b5d1c/html5/thumbnails/24.jpg)
Búsqueda A*PI
Búsqueda A* por profundización iterativa (A*PI): en este caso la búsqueda preferente por profundidad se modifica para utilizar un límite del costo de ƒ en lugar de un límite de profundidad. De esta forma, en cada iteración se expanden todos los nodos que están dentro del contorno del costo ƒ actual, y se echa un vistazo al contorno para determinar en donde se encuentra el siguiente contorno. Una vez concluida la búsqueda dentro de un contorno, se procede a efectuar una nueva iteración utilizando un nuevo costo ƒ
![Page 25: Métodos de búsqueda respaldados con información. La búsqueda de caminos es un problema que usualmente se resuelve por medio de algoritmos de búsqueda.](https://reader033.fdocumento.com/reader033/viewer/2022052618/54c3dc5c4979595c308b5d1c/html5/thumbnails/25.jpg)
FunctionFunction IDA* (problem) IDA* (problem) returnsreturns a solution sequence a solution sequence FunciónFunción A*PI(problem) A*PI(problem) responderesponde concon una secuencia de solución una secuencia de solución EntradasEntradas: problema, un problema: problema, un problema EstáticoEstático: limite-f, el limite actual de COSTO-F: limite-f, el limite actual de COSTO-F Raíz, un nodoRaíz, un nodo Raíz HACER-NODO (ESTADO-INICIAL [problema])Raíz HACER-NODO (ESTADO-INICIAL [problema]) Límite-f COSTO-raíz)Límite-f COSTO-raíz) BucleBucle hacerhacer Solucion, limite-f DFS-CONTORNO (raíz, limite-f)Solucion, limite-f DFS-CONTORNO (raíz, limite-f) si solución no es nula si solución no es nula entonces respondeentonces responde con solución con solución si limite-f=∞, si limite-f=∞, entonces responde conentonces responde con falla; falla; finfin
FunctionFunction DFS-CONTOUR (node, f-limit) DFS-CONTOUR (node, f-limit) returnsreturns a solution sequence and a new f-COST a solution sequence and a new f-COST limitlimit
FunciónFunción CONTORNO-DFS (nodo, limite-f) CONTORNO-DFS (nodo, limite-f) responderesponde concon una secuencia de solución y una secuencia de solución y un nuevo limite de COSTO-fun nuevo limite de COSTO-f
EntradasEntradas: nodo, un nodo: nodo, un nodo Límite-f, el límite actual de COSTO-fLímite-f, el límite actual de COSTO-f EstáticoEstático: siguiente-f, el límite de COSTO-f correspondiente al siguiente contorno, : siguiente-f, el límite de COSTO-f correspondiente al siguiente contorno,
inicialmente ∞inicialmente ∞ sisi COSTO-f nodo] limite-f, COSTO-f nodo] limite-f, entonces responde conentonces responde con nulo, COSTO-f[nodo nulo, COSTO-f[nodo sisi PRUEBA-META[problema](ESTADO[NODO]) PRUEBA-META[problema](ESTADO[NODO]) entonces responde conentonces responde con nodo, limite-f nodo, limite-f por cadapor cada nodo s nodo s enen SUCESORES(nodo) SUCESORES(nodo) hacerhacer solución, nueva-f CONTORNO –DFS(s, limite-f)solución, nueva-f CONTORNO –DFS(s, limite-f) sisi solución no es nula, solución no es nula, entonces responde conentonces responde con solución, limite-f solución, limite-f siguiente-f MIN(siguiente-f, nueva-f); siguiente-f MIN(siguiente-f, nueva-f); finfin responde conresponde con nulo, siguiente-f nulo, siguiente-f
![Page 26: Métodos de búsqueda respaldados con información. La búsqueda de caminos es un problema que usualmente se resuelve por medio de algoritmos de búsqueda.](https://reader033.fdocumento.com/reader033/viewer/2022052618/54c3dc5c4979595c308b5d1c/html5/thumbnails/26.jpg)
• IDA* es un método de búsqueda completo y óptimo.
• Tiene las mismas ventajas y desventajas que A*, excepto en lo referente al coste espacial.
• En el mejor caso el coste temporal de IDA* puede ser muy similar al de A*, e incluso menor.
![Page 27: Métodos de búsqueda respaldados con información. La búsqueda de caminos es un problema que usualmente se resuelve por medio de algoritmos de búsqueda.](https://reader033.fdocumento.com/reader033/viewer/2022052618/54c3dc5c4979595c308b5d1c/html5/thumbnails/27.jpg)
EJEMPLO:
Se emplea la búsqueda con límite de profundidad, pero los límites van aumentando hasta encontrar una meta. Es completa y óptima
![Page 28: Métodos de búsqueda respaldados con información. La búsqueda de caminos es un problema que usualmente se resuelve por medio de algoritmos de búsqueda.](https://reader033.fdocumento.com/reader033/viewer/2022052618/54c3dc5c4979595c308b5d1c/html5/thumbnails/28.jpg)
Búsqueda A*SRM
Emplea toda la capacidad de memoria disponible para efectuar una búsqueda.
El empleo de mas memoria permite mejorar la eficiencia en la búsqueda
![Page 29: Métodos de búsqueda respaldados con información. La búsqueda de caminos es un problema que usualmente se resuelve por medio de algoritmos de búsqueda.](https://reader033.fdocumento.com/reader033/viewer/2022052618/54c3dc5c4979595c308b5d1c/html5/thumbnails/29.jpg)
A*SRM se Caracteriza por: Hará uso de toda la memoria que pueda disponer
En la medida que se lo facilite la memoria, evitara los estados repetidos
Es completo si la memoria disponible tienen capacidad suficiente para guardar la ruta solución mas cercana
![Page 30: Métodos de búsqueda respaldados con información. La búsqueda de caminos es un problema que usualmente se resuelve por medio de algoritmos de búsqueda.](https://reader033.fdocumento.com/reader033/viewer/2022052618/54c3dc5c4979595c308b5d1c/html5/thumbnails/30.jpg)
Es optima si dispone de suficiente
memoria para guardar la ruta de
solución optima mas cercana.
De lo contrario, produce la mejor
solución que sea posible obtener con la
memoria disponible
Si se dispone de suficiente memoria para
todo el árbol de búsqueda, ésta resultara
óptimamente eficiente
![Page 31: Métodos de búsqueda respaldados con información. La búsqueda de caminos es un problema que usualmente se resuelve por medio de algoritmos de búsqueda.](https://reader033.fdocumento.com/reader033/viewer/2022052618/54c3dc5c4979595c308b5d1c/html5/thumbnails/31.jpg)
functionfunction SMA*(problem) SMA*(problem) returnsreturns a solution sequence a solution sequence funciónfunción A*SRM (problema) A*SRM (problema) responderesponde concon una secuencia de solución. una secuencia de solución. EntradasEntradas: problema, un problema: problema, un problema EstáticoEstático: Lista de espera, una lista de nodos organizada según costo-f: Lista de espera, una lista de nodos organizada según costo-f Lista de espera HACER-LISTA DE ESPERA({HACER NODO ( ESTADO- InicialLista de espera HACER-LISTA DE ESPERA({HACER NODO ( ESTADO- Inicial [ problema]})[ problema]}) bucle hacer bucle hacer sisi Lista de espera esta vacía, Lista de espera esta vacía, entonces responde conentonces responde con falla falla n nodo mas profundo con f de mínimo costo en lista de esperan nodo mas profundo con f de mínimo costo en lista de espera sisi PRUEBA-META (n) PRUEBA-META (n) entonces responde conentonces responde con éxito éxito s s SIGUIENTE-SUCESOR (n) SIGUIENTE-SUCESOR (n) sisi s no es una meta y esta en la profundidad máxima, s no es una meta y esta en la profundidad máxima, entoncesentonces f(s) ∞ f(s) ∞o o bienbien f(s) MAX (f(n), g(s)+ h(s))f(s) MAX (f(n), g(s)+ h(s)) sisi ya se genero a todos los n sucesores ya se genero a todos los n sucesores entoncesentonces actualice los n costos-fy, de ser actualice los n costos-fy, de ser
necesario, los de los ancestros necesario, los de los ancestrossisi los SUCESORES(n) están todos en la memoria, los SUCESORES(n) están todos en la memoria, entoncesentonces quite n de Lista de quite n de Lista de
esperaesperasisi la memoria esta llena, la memoria esta llena, entoncesentonces borre en Lista de espera el nodo-de costo-f-mas-elevado que este mas borre en Lista de espera el nodo-de costo-f-mas-elevado que este mas
próximo, próximo, quítelo de la lista de sucesores de su padrequítelo de la lista de sucesores de su padre inserte su padre en Lista de espera, en caso de ser necesarioinserte su padre en Lista de espera, en caso de ser necesario inserte s en Lista de esperainserte s en Lista de espera finfin
![Page 32: Métodos de búsqueda respaldados con información. La búsqueda de caminos es un problema que usualmente se resuelve por medio de algoritmos de búsqueda.](https://reader033.fdocumento.com/reader033/viewer/2022052618/54c3dc5c4979595c308b5d1c/html5/thumbnails/32.jpg)
Ejemplo de A*SRM
A
BG
IH
J K
C D
E F
0+12=12
8+5=1310+5=15
20+0=2020+5=25
30+5=35 30+0=30
24+0=24 24+5=29
24+0=24
16+2=18
108
10 10
168
88
1010
Valor para c/nodo G+H=F
Nodos meta
![Page 33: Métodos de búsqueda respaldados con información. La búsqueda de caminos es un problema que usualmente se resuelve por medio de algoritmos de búsqueda.](https://reader033.fdocumento.com/reader033/viewer/2022052618/54c3dc5c4979595c308b5d1c/html5/thumbnails/33.jpg)
A
12
1
A
B
2
12
15
3 4
8
24
B
A
C
13
15 13
A
H
G13
13(15)
5
13(15)A
G
I
24(∞)
20(24)
6
A15
B G15 24
A
B
C
15(24)
7
15
25(∞)
A
B
D
24(∞)
20
![Page 34: Métodos de búsqueda respaldados con información. La búsqueda de caminos es un problema que usualmente se resuelve por medio de algoritmos de búsqueda.](https://reader033.fdocumento.com/reader033/viewer/2022052618/54c3dc5c4979595c308b5d1c/html5/thumbnails/34.jpg)
![Page 35: Métodos de búsqueda respaldados con información. La búsqueda de caminos es un problema que usualmente se resuelve por medio de algoritmos de búsqueda.](https://reader033.fdocumento.com/reader033/viewer/2022052618/54c3dc5c4979595c308b5d1c/html5/thumbnails/35.jpg)
Arad
Arad
Timisoara
FagarasRimnicu VilceaOradea
Zerind
Sibiu PitestiCraiova
Sibiu
Bucharest
f(n) = g(n) + h(n)
f(n)=118+329
= 447
f(n)=280+366
= 646
f(n)=291+380
= 671
f(n)=418+0
= 418
f(n)=239+178
= 417
f(n)=317+98
= 415
f(n)=220+193
= 413
f(n)=366+160
= 526
f(n)=300+253
= 553
f(n)=75+374
= 449
f(n)=140+253
= 393
f(n)=0+366
= 366
118 140 75
140 151 80 99
80 146 97
101
![Page 36: Métodos de búsqueda respaldados con información. La búsqueda de caminos es un problema que usualmente se resuelve por medio de algoritmos de búsqueda.](https://reader033.fdocumento.com/reader033/viewer/2022052618/54c3dc5c4979595c308b5d1c/html5/thumbnails/36.jpg)
Mapas
Juegos
Robótica
C++
![Page 37: Métodos de búsqueda respaldados con información. La búsqueda de caminos es un problema que usualmente se resuelve por medio de algoritmos de búsqueda.](https://reader033.fdocumento.com/reader033/viewer/2022052618/54c3dc5c4979595c308b5d1c/html5/thumbnails/37.jpg)
![Page 38: Métodos de búsqueda respaldados con información. La búsqueda de caminos es un problema que usualmente se resuelve por medio de algoritmos de búsqueda.](https://reader033.fdocumento.com/reader033/viewer/2022052618/54c3dc5c4979595c308b5d1c/html5/thumbnails/38.jpg)
8-Puzzle
![Page 39: Métodos de búsqueda respaldados con información. La búsqueda de caminos es un problema que usualmente se resuelve por medio de algoritmos de búsqueda.](https://reader033.fdocumento.com/reader033/viewer/2022052618/54c3dc5c4979595c308b5d1c/html5/thumbnails/39.jpg)
Cubo de
Rubik
![Page 40: Métodos de búsqueda respaldados con información. La búsqueda de caminos es un problema que usualmente se resuelve por medio de algoritmos de búsqueda.](https://reader033.fdocumento.com/reader033/viewer/2022052618/54c3dc5c4979595c308b5d1c/html5/thumbnails/40.jpg)
Posición inicial
Posición deseada
![Page 41: Métodos de búsqueda respaldados con información. La búsqueda de caminos es un problema que usualmente se resuelve por medio de algoritmos de búsqueda.](https://reader033.fdocumento.com/reader033/viewer/2022052618/54c3dc5c4979595c308b5d1c/html5/thumbnails/41.jpg)
Posición inicial
Posición
deseada
![Page 42: Métodos de búsqueda respaldados con información. La búsqueda de caminos es un problema que usualmente se resuelve por medio de algoritmos de búsqueda.](https://reader033.fdocumento.com/reader033/viewer/2022052618/54c3dc5c4979595c308b5d1c/html5/thumbnails/42.jpg)
A*
Lista
Mapa
![Page 43: Métodos de búsqueda respaldados con información. La búsqueda de caminos es un problema que usualmente se resuelve por medio de algoritmos de búsqueda.](https://reader033.fdocumento.com/reader033/viewer/2022052618/54c3dc5c4979595c308b5d1c/html5/thumbnails/43.jpg)
![Page 44: Métodos de búsqueda respaldados con información. La búsqueda de caminos es un problema que usualmente se resuelve por medio de algoritmos de búsqueda.](https://reader033.fdocumento.com/reader033/viewer/2022052618/54c3dc5c4979595c308b5d1c/html5/thumbnails/44.jpg)