Algorytm znajdujący liczbę prostych ścieżek od do w


34

Ktoś może zaproponować mi liniowy algorytmu czasu, który wprowadzany jest skierowany acykliczny wykres a dwa wierzchołki i i powraca liczbę prostych odcinków z na w . Mam algorytm, w którym uruchomię DFS (Głębokie pierwsze wyszukiwanie), ale jeśli DFS znajdzie to nie zmieni koloru (z białego na szary) żadnego z węzłów, które znajdują się na ścieżce tak że jeśli jest to podścieżka jakiejkolwiek innej ścieżki, to również DFS ponownie przechodzi przez tę podścieżkę. Na przykład rozważ listę przyległości, w której musimy znaleźć liczbę ścieżek od do vs t s t G t s t p vG=(V,E)ststG
tstpv .

poszorsvsrryyvvwzwz
Tutaj DFS rozpocznie się od p a następnie powiedzmy, że idzie do pz ponieważ nie napotyka v DFS będzie działał normalnie. Teraz drugi ścieżka jest psryv ponieważ napotyka v , nie zmieniamy koloru wierzchołków s,r,y,v na szary. Następnie ścieżka pov ponieważ kolor v jest nadal biały. Następnie ścieżka posryv,posryv ponieważ kolor s jest biały i podobnie ścieżkaporyv.Utrzymywany jest również licznik, który zwiększa się, gdy napotka v .

Czy mój algorytm jest poprawny? jeśli nie, jakie modyfikacje są potrzebne, aby było poprawne, lub wszelkie inne podejścia będą bardzo mile widziane.

Uwaga : Rozważyłem tutaj algorytm DFS podany w książce „Wprowadzenie do algorytmów przez Cormena”, w którym koloruje on węzły zgodnie z jego statusem, więc jeśli węzeł nie jest odwiedzany, niezbadany i badany, wówczas kolor będzie biały, odpowiednio szary i czarny. Wszystkie pozostałe elementy są standardowe.



4
Zauważ, że wszystkie ścieżki na ukierunkowanym wykresie acyklicznym są z konieczności proste (z racji acykliczności).
Noldorin

Odpowiedzi:


37

Twoja obecna implementacja obliczy prawidłową liczbę ścieżek w DAG. Jednak nie oznaczanie ścieżek zajmie wykładniczy czas. Na przykład na poniższej ilustracji każdy etap DAG zwiększa całkowitą liczbę ścieżek o wielokrotność 3. Ten wykładniczy wzrost można rozwiązać za pomocą programowania dynamicznego.

dag

Obliczenie liczby ścieżek - w DAG jest określone przez powtarzalność, st

Ścieżki(u)={1Jeśli u=t(u,przeciwko)miŚcieżki(przeciwko)Inaczej.

Prosta modyfikacja DFS obliczy to jako

def dfs(u, t):
    if u == t:
        return 1
    else:
        if not u.npaths:
            # assume sum returns 0 if u has no children
            u.npaths = sum(dfs(c, t) for c in u.children)
        return u.npaths

Nietrudno zauważyć, że każda krawędź jest oglądana tylko raz, stąd środowisko uruchomieniowe .O(V.+mi)


Zrozumiałem twój algorytm i można go uczynić nieco bardziej wydajnym za pomocą programowania dynamicznego, ponieważ te same rekurencyjne połączenia są wywoływane wiele razy, więc lepiej jest zapisać.
Saurabh

1
@SaurabhHota, używa programowania dynamicznego. Po raz pierwszy wierzchołek napotkano, to oblicza się liczbę ścieżek to musi t . Jest to przechowywane w ścieżkach użytkownika. Każde kolejne wywołanie u nie spowoduje ponownego obliczenia liczby ścieżek, ale po prostu zwróci ścieżki u. utu
Nicholas Mancuso,

1
Dla takich wykresów nie jest odpowiedzią tylko m ^ n, gdzie m jest liczbą węzłów w kolumnie (tutaj 3), a n jest liczbą kolumn z wyłączeniem s, t (tutaj 4). wyjście to 3 ^ 4 = 81 dla przykładowego wykresu.
saadtaame

@saadtaame, jasne; moim zamiarem było jednak jedynie przedstawienie wykładniczego wzrostu wraz ze wzrostem „długości” wykresu. Oczywiście dla tego wysoce ustrukturyzowanego wykresu można liczyć w formie zamkniętej, podczas gdy wymieniony algorytm działa dla wszystkich wykresów.
Nicholas Mancuso,

3
Czas działania zakłada, że ​​można wykonać niezbędne dodania w stałym czasie, ale dodawane liczby mogą mieć w najgorszym przypadku Θ ( V ) bitów. Jeśli potrzebujesz dokładnej liczby ścieżek, czas działania (liczenie operacji bitowych) to w rzeczywistości O ( V E ) . O(V+E)Θ(V)O(VE)
JeffE

15

Trzeba tylko zauważyć, że liczba ścieżek od jednego węzła do węzła docelowego jest sumą liczby ścieżek od jego potomków do celu. Wiesz, że ten algorytm zawsze się zatrzyma, ponieważ twój wykres nie ma żadnych cykli.

Teraz, jeśli zapiszesz liczbę ścieżek z jednego węzła do celu podczas odwiedzania węzłów, złożoność czasu stanie się liniowa w liczbie wierzchołków, a pamięć liniowa w liczbie węzłów.


0

Liczbę ścieżek między dowolnymi dwoma wierzchołkami w DAG można znaleźć za pomocą reprezentacji macierzy przyległości.

Załóżmy, że A jest macierzą przylegania G. Biorąc moc Kth z A po dodaniu do niej macierzy tożsamości, daje liczbę ścieżek o długości <= K.

Ponieważ maksymalna długość dowolnej prostej ścieżki w DAG wynosi | V | -1, obliczenie | V | -1 potęgi dałoby liczbę ścieżek między wszystkimi parami wierzchołków.

Obliczenia | V | -1 mocy można dokonać wykonując logarytmiczne (| V | -1) wielokrotności każdego z TC: | V | ^ 2.


Pytanie dotyczy liniowego algorytmu czasu. Twój algorytm jest wolniejszy.
DW

@Vivek, czy możesz w swojej odpowiedzi wymienić odniesienie do twierdzeń?
Hamideh
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.