Algoritmos de búsqueda en grafos¶
Hemos definido el problema de búsqueda de caminos en un laberinto como encontrar un camino entre dos nodos cualesquiera del grafo, en caso de existir ese camino.
Este no es un problema nuevo para la computación, de hecho el algoritmo que le da solución y que lleva el nombre de su inventor, fue descubierto en 1956.
Dijkstra¶
El algoritmo de dijkstra es un algoritmo que determijna camino más corto, dado un vértice origen, hacia el resto de los vértices en un grafo con pesos.
La idea es partir del nodo de origen y explorar recusivamente los caminos mínimos al resto de nodos, guardando y actualizando la información de forma continua en memoria.
ALGORITMO Dijkstra(Grafo G, Nodo origen)
INICIALIZAR distancia[nodos de G] a infinito
INICIALIZAR visto[nodos de G] a falso
DISTANCIA[origen] = 0
MIENTRAS existan nodos no vistos HACER
nodo_actual = nodo no visto con menor valor en DISTANCIA
visto[nodo_actual] = verdadero
PARA CADA vecino DE nodo_actual HACER
SI visto[vecino] es falso ENTONCES
distancia_tentativa = DISTANCIA[nodo_actual] + peso(nodo_actual, vecino)
SI distancia_tentativa < DISTANCIA[vecino] ENTONCES
DISTANCIA[vecino] = distancia_tentativa
FIN SI
FIN SI
FIN PARA
FIN MIENTRAS
FIN ALGORITMO
In [1]:
from heapq import heappush, heappop # colas de prioridad
import networkx as nx
import numpy as np
In [2]:
from maze import Maze
m = Maze(10) ## RANDOM SEED NOT SET ON MAZE GENERATION ###
In [3]:
def dijkstra(grafo, start):
distancias = {}
caminos = {}
padres = {}
vistos = set()
queue = []
for n in grafo.nodes:
distancias[n] = float('inf')
padres[n] = None
caminos[n] = []
distancias[start] = 0
caminos[start] = [start]
heappush(queue, (distancias[start], start))
while queue:
dist_actual, nodo_actual = heappop(queue)
vistos.add(nodo_actual)
if dist_actual > distancias[nodo_actual]:
continue
for ady in list(grafo.neighbors(nodo_actual)):
if ady not in vistos:
nueva_dist = distancias[nodo_actual] + grafo[nodo_actual][ady].get('weight', 1)
if nueva_dist < distancias[ady]:
distancias[ady] = nueva_dist
padres[ady] = nodo_actual
caminos[ady] = caminos[nodo_actual] + [ady]
heappush(queue, (distancias[ady], ady))
return distancias, caminos
In [4]:
# DIJKSTRA
distancias, caminos = dijkstra(m.grid,m.start)
caminos[m.end]
Out[4]:
[(0, 0), (0, 1), (0, 2), (1, 2), (2, 2), (3, 2), (3, 3), (3, 4), (3, 5), (4, 5), (4, 6), (5, 6), (6, 6), (7, 6), (7, 7), (7, 8), (8, 8), (9, 8), (9, 9)]
Visualización de resultados - Animación con pyvis¶
In [5]:
from pyvis.network import Network
def dijkstra_animado_con_pyvis(G):
start, end = G.start, G.end
visitados = set()
distancias = {nodo: float('inf') for nodo in G.grid.nodes()}
distancias[start] = 0
cola = [(0, start)]
while cola:
_, nodo_actual = heappop(cola)
if nodo_actual in visitados:
continue
visitados.add(nodo_actual)
visualizar_grafo_con_pyvis(G.grid, visitados, start, end, f"resources/frames/dijkstra_{len(visitados)}.html")
if nodo_actual == end:
break
for vecino in G.grid.neighbors(nodo_actual):
nueva_dist = distancias[nodo_actual] + 1 # Asumiendo un peso de 1 para cada arista
if nueva_dist < distancias[vecino]:
distancias[vecino] = nueva_dist
heappush(cola, (nueva_dist, vecino))
def visualizar_grafo_con_pyvis(G, visitados, start, end, filename):
nt = Network(notebook=True, width="100%", height="700px",cdn_resources="local")
for node in G.nodes:
x, y = node
nt.add_node(str(node), title=str(node), x=x*100, y=-y*100, color="lightgray" if node not in visitados else "skyblue", fixed=True)
for edge in G.edges:
nt.add_edge(str(edge[0]), str(edge[1]))
nt.get_node(str(start))["color"] = "green"
nt.get_node(str(end))["color"] = "red"
nt.toggle_physics(False)
nt.show(filename)
In [6]:
# Ejecutar la animación de Dijkstra
m = Maze(10) ## RANDOM SEED NOT SET ON MAZE GENERATION ###
m.display()
dijkstra_animado_con_pyvis(m)
Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook. resources/frames/dijkstra_1.html Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook. resources/frames/dijkstra_2.html Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook. resources/frames/dijkstra_3.html Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook. resources/frames/dijkstra_4.html Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook. resources/frames/dijkstra_5.html Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook. resources/frames/dijkstra_6.html Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook. resources/frames/dijkstra_7.html Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook. resources/frames/dijkstra_8.html Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook. resources/frames/dijkstra_9.html Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook. resources/frames/dijkstra_10.html Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook. resources/frames/dijkstra_11.html Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook. resources/frames/dijkstra_12.html Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook. resources/frames/dijkstra_13.html Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook. resources/frames/dijkstra_14.html Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook. resources/frames/dijkstra_15.html Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook. resources/frames/dijkstra_16.html Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook. resources/frames/dijkstra_17.html Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook. resources/frames/dijkstra_18.html Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook. resources/frames/dijkstra_19.html Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook. resources/frames/dijkstra_20.html Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook. resources/frames/dijkstra_21.html Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook. resources/frames/dijkstra_22.html Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook. resources/frames/dijkstra_23.html Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook. resources/frames/dijkstra_24.html Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook. resources/frames/dijkstra_25.html Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook. resources/frames/dijkstra_26.html Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook. resources/frames/dijkstra_27.html Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook. resources/frames/dijkstra_28.html Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook. resources/frames/dijkstra_29.html Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook. resources/frames/dijkstra_30.html Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook. resources/frames/dijkstra_31.html Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook. resources/frames/dijkstra_32.html Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook. resources/frames/dijkstra_33.html Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook. resources/frames/dijkstra_34.html Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook. resources/frames/dijkstra_35.html Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook. resources/frames/dijkstra_36.html Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook. resources/frames/dijkstra_37.html Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook. resources/frames/dijkstra_38.html Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook. resources/frames/dijkstra_39.html Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook. resources/frames/dijkstra_40.html Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook. resources/frames/dijkstra_41.html Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook. resources/frames/dijkstra_42.html Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook. resources/frames/dijkstra_43.html Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook. resources/frames/dijkstra_44.html Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook. resources/frames/dijkstra_45.html Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook. resources/frames/dijkstra_46.html Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook. resources/frames/dijkstra_47.html Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook. resources/frames/dijkstra_48.html Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook. resources/frames/dijkstra_49.html Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook. resources/frames/dijkstra_50.html Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook. resources/frames/dijkstra_51.html Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook. resources/frames/dijkstra_52.html Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook. resources/frames/dijkstra_53.html Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook. resources/frames/dijkstra_54.html Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook. resources/frames/dijkstra_55.html Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook. resources/frames/dijkstra_56.html Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook. resources/frames/dijkstra_57.html Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook. resources/frames/dijkstra_58.html Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook. resources/frames/dijkstra_59.html Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook. resources/frames/dijkstra_60.html Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook. resources/frames/dijkstra_61.html Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook. resources/frames/dijkstra_62.html Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook. resources/frames/dijkstra_63.html Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook. resources/frames/dijkstra_64.html Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook. resources/frames/dijkstra_65.html Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook. resources/frames/dijkstra_66.html Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook. resources/frames/dijkstra_67.html Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook. resources/frames/dijkstra_68.html Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook. resources/frames/dijkstra_69.html Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook. resources/frames/dijkstra_70.html Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook. resources/frames/dijkstra_71.html Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook. resources/frames/dijkstra_72.html Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook. resources/frames/dijkstra_73.html Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook. resources/frames/dijkstra_74.html Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook. resources/frames/dijkstra_75.html Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook. resources/frames/dijkstra_76.html Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook. resources/frames/dijkstra_77.html Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook. resources/frames/dijkstra_78.html Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook. resources/frames/dijkstra_79.html Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook. resources/frames/dijkstra_80.html
¿Cómo visualizar la animación? Después de ejecutar el comando anterior, se habran creado archivos html dentro de frames. Ahora tenemos ejecutar html_to_images.js para renderizar el javascript, realizar una captura de pantalla de cada html, y convertirlo todo después a vídeo.
- Ir a la carpeta resources
cd resources/
- Convertir los html a imagenes
node html_to_images.js
- Convertir las imagenes a un vídeo secuencial, donde cada frame dura 1s
ffmpeg -framerate 1 -pattern_type glob -i 'temp_images/capture_dijkstra_*.png' -c:v libx264 -r 30 -pix_fmt yuv420p out.mp4
In [8]:
from IPython.display import Video
## RANDOM SEED NOT SET ON MAZE GENERATION ###
Video("resources/out.mp4")
Out[8]:
A*¶
In [ ]:
# Función heurística para el algoritmo A*
def manhattan(s,e):
dmin = min(abs(s[0]-e[0]), abs(s[1]-e[1]))
dmax = max(abs(s[0]-e[0]), abs(s[1]-e[1]))
return dmin + (dmax-dmin)