¿Cómo encontrar la ruta más larga en un gráfico cíclico entre dos nodos?

Question

Ya he resuelto la mayoría de las preguntas publicadas here, todas excepto la más larga. He leído el artículo de Wikipedia sobre las rutas más largas y parece que cualquier problema fácil si la gráfica era acíclica, y la mía no.

¿Cómo resuelvo el problema, entonces? Fuerza bruta, al verificar todos los caminos posibles? ¿Cómo empiezo a hacer eso?

Sé que va a tomar MUCHO en un gráfico con ~ 18000. Pero solo quiero desarrollarlo de todos modos, porque es necesario para el proyecto y lo probaré y se lo mostraré al instructor en un gráfico de menor escala donde el tiempo de ejecución es de uno o dos segundos.

Al menos hice todas las tareas requeridas y tengo una prueba de concepto en ejecución que funciona, pero no hay mejor manera en los gráficos cíclicos. Pero no tengo ni idea de por dónde empezar a verificar todas estas rutas ...

Answer 1

La solución es forzarla brutalmente. Puede hacer algunas optimizaciones para acelerarlo, algunas son triviales, otras son muy complicadas. Dudo que pueda hacer que funcione lo suficientemente rápido para 18 000 nodos en una computadora de escritorio, e incluso si puede, no tengo ni idea de cómo. Así es como funciona la fuerza bruta.

Nota: Dijkstra y cualquiera de los otros algoritmos de ruta más cortos NO funcionarán para este problema si está interesado en una respuesta exacta.

Start at a root node *root* 
Let D[i] = longest path from node *root* to node i. D[*root*] = 0, and the others are also 0. 

void getLongestPath(node, currSum) 
{ 
    if node is visited 
     return; 
    mark node as visited; 

    if D[node] < currSum 
     D[node] = currSum; 

    for each child i of node do 
     getLongestPath(i, currSum + EdgeWeight(i, node)); 

    mark node as not visited; 
} 

Vamos a ejecutarlo con la mano en este gráfico: 1 - 2 (4), 1 - 3 (100), 2 - 3 (5), 3 - 5 (200), 3 - 4 (7), 4 - 5 (1000)

Let the root be 1. We call getLongestPath(1, 0); 
2 is marked as visited and getLongestPath(2, 4); is called 
D[2] = 0 < currSum = 4 so D[2] = 4. 
3 is marked as visited and getLongestPath(3, 4 + 5); is called 
D[3] = 0 < currSum = 9 so D[3] = 9. 
4 is marked as visited and getLongestPath(4, 9 + 7); is called 
D[4] = 0 < currSum = 16 so D[4] = 16. 
5 is marked as visited and getLongestPath(5, 16 + 1000); is called 
D[5] = 0 < currSum = 1016 so D[5] = 1016. 
getLongestPath(3, 1016 + 200); is called, but node 3 is marked as visited, so nothing happens. 
Node 5 has no more child nodes, so the function marks 5 as not visited and backtracks to 4. The backtracking will happen until node 1 is hit, which will end up setting D[3] = 100 and updating more nodes. 

es como se vería de forma iterativa Aquí (no probado, sólo una idea básica):

Let st be a stack, the rest remains unchanged; 
void getLongestPath(root) 
{ 
    st.push(pair(root, 0)); 

    while st is not empty 
    { 
     topStack = st.top(); 
     if topStack.node is visited 
      goto end; 
     mark topStack.node as visited; 

     if D[topStack.node] < topStack.sum 
      D[topStack.node = topStack.sum; 

     if topStack.node has a remaining child (*) 
      st.push(pair(nextchild of topStack.node, topStack.sum + edge cost of topStack.node - nextchild)) 

     end: 
     mark topStack.node as not visited 
     st.pop(); 
    } 
} 

(*) - esto es un problema - tienes que mantener un puntero al próximo hijo para cada nodo, ya que puede cambiar entre diferentes iteraciones del ciclo while e incluso reiniciarse (el puntero se reinicia cuando e topStack.node nodo fuera de la pila, así que asegúrese de restablecerlo). Esto es más fácil de implementar en las listas enlazadas, sin embargo, debe usar las listas int[] o vector<int>, para poder almacenar los punteros y tener acceso aleatorio, porque lo necesitará. Puede mantener, por ejemplo, next[i] = next child of node i in its adjacency list y actualizarlo en consecuencia. Es posible que tenga algunos casos límite y podría necesitar diferentes situaciones end:: una normal y otra que ocurre cuando visita un nodo ya visitado, en cuyo caso los punteros no necesitan reiniciarse. Tal vez mueva la condición visitada antes de decidir empujar algo en la pila para evitar esto.

¿Ves por qué dije que no deberías molestarte? :)