Camino más corto

[jearaneda]

Estoy tratando de obtener el camino más corto entre dos nodos de un grafo, pues se pide en varias actividades anteriores. Investigué un poco y me aparecen algunos algoritmos: el de dijkstra y 2-opt principalmente. Sin embargo, ambos piden que la modelación tenga weights y no hallo forma de hacerlo funcionar con la modelación que estoy usando, a continuación:

    def entregar_ruta(self, origen, destino):
        if origen == destino:
            return True
        origen = self.get_terreno(origen)
        destino = self.get_terreno(destino)
        if origen is None or destino is None:
            return None
        cola = [[origen]]
        visited = list()
        while len(cola):
            current_path = cola.pop(0)
            current = current_path[-1]
            if current not in visited:
                lista_vecinos=[self.get_terreno(x) for x in current.conexiones]
                for vecino in lista_vecinos:
                    cola.append(list(current_path) + [vecino])
                    if vecino == destino:
                        for t in range(len(cola[-1])):
                            if cola[-1][t-1] == cola[-1][t]:
                                cola[-1].remove(cola[-1][t]) 
                        return cola[-1]
                visited.append(current)
        return None  

¿Qué otra manera puede haber de encontrar todos los caminos para luego retornar el más corto?

[Hernan4444]

¡Hola @jearaneda!

Para aclarar primero un punto, si bien los algoritmos dijkstra y 2-opt piden que las aristas tengan un peso (weights), uno igual lo puede hacer con un grafo sin pesos, pero es necesario hacer un paso previo el cual es setear un peso a cada arista con el mismo valor, por defecto es 1. Luego ya se pueden aplicar los algoritmos que encontraste c:

Ahora,

¿Qué otra manera puede haber de encontrar todos los caminos para luego retornar el más corto?

Te voy a dar la intuición de 2 formas posibles de encontrar el camino más corto usando los contenidos que ya sabemos 😄.

BFS

Sabemos que este algoritmo parte de un nodo, recorre todos los vecinos de ese nodo y luego recorre todos los vecinos de los nodos agregados. Si lo vemos desde otra perspectiva:

• (1) El algoritmo parte de un nodo (origen) y visita todos los nodos con distancia 1 del origen y agrega los vecinos de aquellos nodos, es decir, agrega nodos con distancia 2.
• (2) Luego de ver todos esos nodos de distancia 1, parte viendo todos los nodos con distancia 2 y agrega los vecinos de aquellos nodos, es decir, agrega nodos con distancia 3.
• (3) Y así sucesivamente, por lo tanto, cuando te encuentres con tu nodo destino, lo habrás encontrado con la mínima distancia posible.

Ahora, tenemos 2 dificultades. La primera es como determinar la distancia (cuando pasamos de distancia 1 a distancia 2 por ejemplo) y luego determinar el camino encontrado. Para el primero te mostraré una forma (hay más) de como editar el BFS para almacenar esa información

from collections import deque

def bfs(grafo, inicio):
    # Vamos a mantener un set con los nodos visitados.
    visitados = set()
    # La cola de siempre, comienza desde el nodo inicio.
    queue = deque([inicio, 0]) # Distancia inicial del origen al inicio es 0

    while len(queue) > 0:
        vertice, distancia = queue.popleft() # Notar que en la primera iteración, distancia será 0

        # Detalle clave: si ya visitamos el nodo, no hacemos nada!
        if vertice not in visitados:
            # Lo visitamos
            visitados.add(vertice)
            # Agregamos los vecinos a la cola si es que no han sido visitados.
            for vecino in grafo[vertice]:
                if vecino not in visitados:
                    queue.append([vecino, distancia + 1])
                    # Aquí es donde se hace la magia, tu asocias cada nodo con una distancia, origen == 0
                    # y luego, cada vez que el nodo visitado agregue vecinos, los asocia a distancia + 1
                    # Por lo tanto los vecinos del origen tendrán distancia 1 y cuando ellos agreguen
                    # vecinos, será con distancia 2 y así sucesivamente

    return visitados

Para la segunda parte, ¿como determinar el camino? Lo dejaré como ejercicio propuesto, porque existen muchas formas y alguna puede adaptarse más a tu modelación (por ejemplo, la que tu estabas haciendo es una de ellas), además que sirve como estudio el editar BFS para que logre lo esperado, pero te dejaré la idea de como yo lo enfrentaría:

(1) Cada vez que un nodo agregue un vecino, que este vecino registre quien fue el "padre" que lo agregó a la queue. (2) Luego, cuando encuentres el nodo destino, preguntare cual fue su padre y lo guardas en una lista, luego al padre le vuelves a preguntar cual fue su padre y la respuesta la guardas en la lista. (3) Si sigues preguntando sucesivamente, en algún momento te toparás con el origen, ahí terminas de preguntar, guardas el origen en la lista y terminaste, tendrás el camino para llegar de destino a origen, aplicamos reverse y tienes el camino de origen a destino. Nota: Debido a la característica de BFS, este también es el camino más corto.

Backtracking

Si bien no está en el material, este algoritmo fue enseñado (hasta el semestre pasado :cry:) en Introducción a la programación y por ello también podemos utilizarlo en grafos. La idea sería crear una función que genere todos los caminos posibles de un nodo a otro y luego tener otra que busque cual es el camino que tiene menos nodos. La idea del algoritmo en palabras sería:

• (1) Crear una función que reciba una lista de nodos (será el camino) y el nodo destino.
• (1.A) La función revisa la lista de nodo y si el último es igual a destino, guarda esa lista en otra llamada "soluciones" y termina, no hace nada más.
• (1.B) Si el último nodo no es el destino, hace N copias de la lista y a cada una le agrega un vecino distinto del último nodo (asumo que el último nodo tiene N vecinos).
• (2) Llamar nuevamente a la función pero con las nuevas N listas

Esto de forma recursiva irá probando con todos los caminos de largo 2, largo 3, largo 4, etc. Importante: lo descrito anteriormente solo funciona con grafos que no tienen ciclo (un grafo con las siguientes conexiones A --> B, B--> C y C--> A si tiene ciclo). En caso de tener, este backtracking no termina nunca 😭. Dejo como propuesto (y motivación de estudio) como modificar los pasos para poder soportar grafos con ciclos, hint: de forma óptima es 1 línea más que agregar 🙈.

Saludos y éxito en la actividad del jueves ✌️

[jearaneda]

EDIT: en el código que adjunto usé print(newpath) y descubrí que el programa, en el caso HARD, encuentra MUCHISIMOS caminos. Llevo 10 minutos corriendo el programa y sigue encontrando caminos, por eso se demora.

Gracias!! Estoy pensando lo del método BFS y logré hacer algo con el método de Dijkstra. Sin embargo, hay algo extraño que no he podido entender:

Por poner un ejemplo, en el ejercicio 1-2018 nos dan un árbol en varios txt (easy, medium, hard) y se piden rutas cortas en todos los path. Se da el output esperado, así que sé que el algoritmo está "funcionando". Lo estoy haciendo así:

def ruta_corta(graph, start, end, path =[]): 
        path = path + [start] 
        if start == end: 
            return path 
        shortest = None
        for node in graph.get_terreno(start).conexiones: 
            if node not in path: 
                newpath = ruta_corta(graph, node, end, path) 
                if newpath: 
                    if not shortest or len(newpath) < len(shortest): 
                        shortest = newpath 
        return shortest 

En easy y medium el programa logra encontrar las rutas más cortas en menos de un segundo -como es el caso de [A, B, D, E, C]-. El problema es que cuando entra a hard se queda ejecutando indefinidamente, sin terminar la recursión. Debería retornar [A, 0, 4, 5, L, Z], pero sigue volviendo al loop una y otra vez.

Lo mismo me pasa con otras actividades de semestres anteriores, en algunos casos funciona y en otros se queda pegado indefinidamente. Sé que no es un caso base -tiene solución-, y encontré a alguien con un problema similar en Stack Overflow cuando había mas de 19 nodos.

Por mientras seguiré intentando con el BFS, gracias!