Grafos – Encontrando caminos óptimos

Cómo el uso de grafos puede ayudarnos en encontrar rutas óptimas para solucionar diversos problemas

Un ejemplo de cómo el uso de grafos puede ayudarnos a encontrar rutas óptimas para solucionar diversos problemas.

Un sistema de grafos puede utilizarse con múltiples finalidades, siendo en algunos casos muy útil para resolver problemas complejos. En esta ocasión vamos a ver cómo utilizar esta herramienta para encontrar caminos óptimos con grafos.

En primer lugar construiremos un grafo dirigido tipo grid de dos dimensiones de 6 x 6 sobre el que trabajar. Además nos quedaremos con el identificador del primer y último nodo para utilizarlos más adelante.

DG = nx.grid_2d_graph(6, 6, periodic=False).to_directed()
positions = nx.kamada_kawai_layout(DG,)
start_node = list(DG.nodes())[0]
end_node = list(DG.nodes())[-1]
Grafos dirigido tipo Grid de 6 x 6
Grafo dirigido tipo Grid de 6 x 6

Vamos a hacer un sistema que encuentre el camino óptimo desde el punto inicial (start_node) hasta el punto final (end_node). Pero pondremos un punto de complejidad para hacer el ejercicio más divertido.

Imaginemos que cada uno de los nodos son salas de un edificio en llamas, las cuales tienen distintas temperaturas. Nuestro objetivo es llegar desde el punto inicial hasta la salida pasando por las habitaciones menos calientes.

El siguiente paso entonces, es asignar de forma aleatoria nuestro grafo (salas del edificio), puntos calientes iniciales y puntos calientes colindantes.

hot_nodes = random.choices(list(DG.nodes()), k=5)
DG.add_nodes_from(hot_nodes, node_temp=0.9)
for hot_node in hot_nodes:
    this_neighbors = list(DG.neighbors(hot_node))
    DG.add_nodes_from(this_neighbors, node_temp=0.5)
Distintas temperaturas asignadas de forma aleatoria en los nodos del grafo
Distintas temperaturas asignadas de forma aleatoria en los nodos del grafo

Ahora vamos a tratar con las aristas (pasillos) que conectan entre ellos nuestros nodos (salas). Estos pasillos tendrán una temperatura media obtenida entre la temperatura de las salas que conecta.

De manera que, si recorremos cada arista del grafo podemos calcular la temperatura y asignarla de la siguiente forma:

for edge_ori, edge_dest in list(DG.edges()):
    DG.add_edges_from(
        [(edge_ori, edge_dest)], 
        edge_temp=np.mean(
            [DG.nodes[edge_ori]["node_temp"], 
             DG.nodes[edge_dest]["node_temp"]]
        )
    )
Aristas del grafo con las temperaturas asignadas según los nodos que conecta cada una

Por lo tanto, si lo que queremos es encontrar el camino óptimo desde el punto inicial (en este caso, nodo del extremo derecho) al punto final (nodo del extremo izquierdo), podemos utilizar uno de los algoritmos que resuelve este tipo de problemas siendo óptimos en cuanto a computación.

El algoritmo A*, que tiene un funcionamiento como el que se puede ver en la siguiente imagen.

De esta forma, si utilizamos este sistema sin tener en cuenta las temperaturas de los nodos, encontraríamos como respuesta uno (puede haber varios) de los caminos más cortos del punto inicial al punto final.

nx.astar_path(DG, start_node, end_node)
[(0, 0),
 (1, 0),
 (2, 0),
 (3, 0),
 (4, 0),
 (5, 0),
 (5, 1),
 (5, 2),
 (5, 3),
 (5, 4),
 (5, 5)]
Uno de los caminos más cortos desde el nodo inicial (0, 0) al nodo final (5, 5)

Aunque como hemos dicho, no es esto lo que buscamos, porque si pasásemos por todas las salas que nos indica el camino más corto, pasaríamos por salas y pasillos con unas temperaturas muy altas.

Por ello, repitamos el proceso, esta vez teniendo en cuenta las temperaturas para encontrar el camino más corto y frío posible.

nx.astar_path(DG, start_node, end_node, weight='edge_temp')
[(0, 0),
 (1, 0),
 (1, 1),
 (2, 1),
 (2, 2),
 (3, 2),
 (3, 3),
 (4, 3),
 (5, 3),
 (5, 4),
 (5, 5)]
Uno de los recorridos más cortos y fríos desde el nodo inicial (0, 0) al nodo final (5, 5)

Así tenemos ya un sistema que resuelve el problema que hemos presentado en cuestión de milisegundos.

Sin embargo ¿qué pasaría si además, eliminamos algunos nodos de nuestro grafo, simulando salas inaccesibles por el incendio?, por ejemplo:

to_remove = [
    (5, 1), (4, 2), (3, 3),
    (0, 2), (1, 1), (2, 1)
]
for node in to_remove:
    DG.remove_node(node)
Ejemplo de ruta óptima eliminando algunos de los nodos del grafo

La ruta se adapta al entorno y obtenemos de nuevo el camino más óptimo teniendo en cuenta la temperatura del trayecto.

De esta forma y con el algoritmo ya preparado, podemos generar un entorno mucho más grande y hacer que el algoritmo se enfrente a un número mayor de decisiones a tomar para encontrar la ruta óptima.

Por ejemplo, generando un nuevo grafo de 2500 nodos y 150 puntos de calor a tener en cuenta.

Grafo dirigido de 50 x 50 con puntos de calor aleatorios

Y con la misma facilidad de lo ya programado, obtenemos la ruta óptima a la salida.

Ruta óptima sobre el grafo teniendo en cuenta la temperatura del camino

Evidentemente esto es un ejemplo simple explicativo del uso de grafos para explicar cómo pueden utilizarse a la hora de resolver ciertos problemas. Estas mismas herramientas pueden ser útiles para resolver distintas problemáticas que podemos encontrarnos en las empresas en su día a día.

A continuación, algunos ejemplos de distintas complejidades sobre los que se puede trabajar con un sistema de grafos y elección de caminos óptimos:

  • Optimización de espacios de almacén
  • Distribución de mercancías
  • Ahorro de combustible en flotas de vehículos
  • Optimización de reglas de compra / venta de productos

El código del ejemplo expuesto está en https://github.com/ para que puedas descargarlo y utilizarlo tú mismo.

Si te ha parecido útil este post sobre grafos, compártelo con tus contactos para que ellos también puedan leerlo y opinar. ¡Nos vemos en redes!

Imagen por defecto
David Martín
Artículos: 2