Jak znaleźć najdłuższą ścieżkę w cyklicznym wykresie między dwoma węzłami?

Question

Już rozwiązałem większość pytań opublikowanych here, wszystkie oprócz najdłuższej ścieżki. Czytałem artykuł z Wikipedii o najdłuższych ścieżkach i wydaje mi się, że jest to łatwy problem, jeśli wykres jest acykliczny, a mój nie.

Jak zatem rozwiązać problem? Brute force, sprawdzając wszystkie możliwe ścieżki? Jak mogę nawet zacząć to robić?

Wiem, że to zajmie DUŻO na wykresie z ~ 18000. Ale po prostu chcę go rozwinąć, ponieważ jest to wymagane do projektu, a ja po prostu przetestuję go i pokażę instruktorowi na wykresie w mniejszej skali, gdzie czas wykonania wynosi zaledwie sekundę lub dwie.

Przynajmniej wykonałem wszystkie wymagane zadania i mam działający proof of concept, który działa, ale nie ma lepszego sposobu na cyklicznych wykresach. Ale nie mam pojęcia, gdzie zacząć sprawdzać wszystkie te ścieżki ...

Answer 1

Rozwiązaniem jest brutalne wymuszanie tego. Możesz zrobić kilka optymalizacji, aby przyspieszyć, niektóre są trywialne, inne są bardzo skomplikowane. Wątpię, czy uda ci się sprawić, by działała wystarczająco szybko, by uzyskać 18 000 węzłów na komputerze stacjonarnym, a nawet jeśli nie mogę mieć pojęcia, jak to zrobić. Oto jak działa bruteforce.

Uwaga: Dijkstra i każdy inny algorytm najkrótszej ścieżki NIE zadziała w tym przypadku, jeśli interesuje Cię dokładna odpowiedź.

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; 
} 

Niech go uruchomić ręcznie na tym wykresie: 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. 

Oto jak to będzie wyglądać iteracyjnie (nie testowane, tylko podstawowa idea):

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(); 
    } 
} 

(*) - to jest mały problem - musisz mieć wskaźnik do następnego potomka dla każdego węzła, ponieważ może on zmieniać pomiędzy różnymi iteracjami pętli while, a nawet resetować się (wskaźnik resetuje się, gdy wyskakujesz e topStack.node Węzeł ze stosu, więc pamiętaj o zresetowaniu go). Jest to najłatwiejsze do wdrożenia na połączonych listach, jednak powinieneś używać list int[] lub vector<int>, aby móc przechowywać wskaźniki i mieć swobodny dostęp, ponieważ będziesz go potrzebować. Możesz zachować na przykład next[i] = next child of node i in its adjacency list i odpowiednio je zaktualizować. Możliwe są sytuacje skrajne i mogą wystąpić różne sytuacje: end:: normalne i występujące podczas odwiedzania już odwiedzonego węzła, w którym to przypadku wskaźniki nie muszą być resetowane. Może przesuwać odwiedzone warunki, zanim zdecydujesz się nacisnąć coś na stosie, aby tego uniknąć.

Zobacz, dlaczego powiedziałem, że nie powinieneś się przejmować? :)