¿Cómo encontrar el camino más largo en un gráfico cíclica entre dos nodos?

Question

Ya resolvió la mayoría de las preguntas enviadas aquí , todos menos el más largo de un camino. He leído el artículo de Wikipedia acerca de las rutas más largas y parece cualquier problema fácil si el grafo acíclico era, que la mía no es.

¿Cómo puedo solucionar el problema entonces? La fuerza bruta, mediante la comprobación de todos los caminos posibles? ¿Cómo puedo siquiera comenzar a hacer eso?

Yo sé que va a tomar mucho en un gráfico con ~ 18000. Pero sólo quiero desarrollar todos modos, porque es necesario para el proyecto y que voy a probarlo y demostrarlo con el instructor en un gráfico de menor escala, donde el tiempo de ejecución es sólo uno o dos segundos.

Por lo menos lo hice todas las tareas requeridas y tengo una prueba de funcionamiento del concepto que funciona, pero no hay mejor manera en los gráficos cíclicos. Pero no tengo idea de por dónde empezar a comprobar todos estos caminos ...

Answer 1

La solución es que la fuerza bruta. Usted puede hacer algunas optimizaciones para acelerarlo, algunos son triviales, algunos son muy complicados. Dudo que usted puede conseguir que funcione lo suficientemente rápido para 18 000 nodos en una computadora de escritorio, e incluso si lo puedo tener ni idea de cómo. Así es como funciona la fuerza bruta sin embargo.

Nota:. Dijkstra y cualquiera de los otros algoritmos del camino más corto no va a funcionar 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;
}

ejecutar Vamos a 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.

Así es como se vería de forma iterativa (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 poco de un problema - usted tiene que mantener un puntero al siguiente niño para cada nodo, ya que puede cambiar entre las diferentes iteraciones del bucle while e incluso restablecer en sí (el puntero a sí mismo cuando se reinicia usted hace estallar el nodo topStack.node de la pila, así que asegúrese de reiniciarlo). Esto es más fácil de implementar en las listas enlazadas, sin embargo usted debe utilizar cualquiera de las listas int[] o listas vector<int>, con el fin de ser capaz de almacenar los punteros y tienen acceso aleatorio, ya que lo necesita. Usted puede mantener, por ejemplo, next[i] = next child of node i in its adjacency list y actualización que en consecuencia. Es posible que tenga algunos casos extremos y puede ser que necesite diferentes situaciones end:: uno normal y uno que pasa cuando se visita un nodo ya visitado, en cuyo caso los punteros no tienen que ser reiniciado. Tal vez mover la condición visitado antes de decidirse a empujar algo en la pila para evitar esto.

Vea por qué dije que no debería molestarse? :)