Wydajny algorytm odzyskiwania przejściowego zamknięcia ukierunkowanego wykresu acyklicznego

14

Próbuję rozwiązać problem z grafem (nie jest to praca domowa, tylko po to, aby ćwiczyć swoje umiejętności). Podaje się DAG , gdzie jest zbiorem wierzchołków, a krawędziami. Wykres jest reprezentowany jako lista przylegania, więc jest zbiorem zawierającym wszystkie połączenia . Moim zadaniem jest znalezienie których wierzchołki są osiągalne z każdego wierzchołka . Rozwiązanie, którego używam, ma złożoność , z przejściowym zamknięciem, ale czytam, że na blogu może być szybsze, chociaż nie ujawniało, jak to zrobić. Czy ktoś mógłby mi powiedzieć inny sposób (z większą złożonością), aby rozwiązać problem przejścia przechodniego w DAG?V E A v v v V O ( V 3 )sol(V.,mi)V.miZAvvvV.O(V.3))

Rontogiannis Aristofanis
źródło
Jednak proponuję zachować . ale po prostu spróbuj zmniejszyć liczbę porównań średnio. To znaczy zgaduj i dodaj proste reguły do ​​swojego algorytmu. Możesz użyć mnożenia macierzy - ale jeśli używasz go do małych wykresów - to jest po prostu bałagan i w rzeczywistości Twoja metoda jest lepsza. O(|V|3)
AJed,
@AJed W tym konkretnym problemie przekroczy limit czasu. O(V3)
Rontogiannis Aristofanis,
2
@RondogiannisAristophanes Kiedy mówisz o limicie czasu, czy masz na myśli, że jest to problem w niektórych wyzwaniach związanych z programowaniem / algorytmem, takich jak topcoder itp.? Jeśli tak, i jeśli masz pewność, że poprawnie wdrożyłeś rozwiązanie , możesz ponownie przyjrzeć się problemowi. Mogą istnieć inne ukryte właściwości, które mogą uprościć sprawy, lub może istnieć lepszy sposób na wyrażenie problemu, tak aby przechodnie zamknięcie nie było potrzebne. Ponieważ przechodnie przechodzenie jest tak trudne jak mnożenie macierzy. Przeczytaj student.cs.uwaterloo.ca/~cs466/Old_courses/F08/…O(V3)
Paresh,

Odpowiedzi:

8

Fakt, że nasz wykres jest acykliczny, znacznie upraszcza ten problem.

Sortowanie topologiczne może dać nam uporządkowanie wierzchołków tak, że jeśli i < j , to nie ma krawędzi od v j z powrotem do v i . Wymieniliśmy wierzchołki tak, aby wszystkie krawędzie były „do przodu” na naszej liście.v1,v2,,vni<jvjvi

(edytowane w celu naprawy analizy i nieco szybszego algorytmu)

Teraz przechodzimy do tyłu przez tę listę, zaczynając od ostatniego wierzchołka . Zamknięcie przechodnie v n jest po prostu samo w sobie. Dodaj także v n do przejściowego zamknięcia każdego wierzchołka z krawędzią do v n .vnvnvnvn

Dla każdego innego wierzchołka , idąc od końca do tyłu, najpierw dodaj v i do własnej przechodniego zamknięcia, a następnie dodać wszystko w przechodniego zamknięcia v í do przechodniego zamknięciu wszystkie wierzchołki z krawędzią do V í .vivivivi

Czas pracy wynosi w najgorszym przypadku, przy n liczbie wierzchołków i m O ( n 2 ) liczbie krawędzi. Sortowanie topologiczne zajmuje czas O ( n + m ) . Następnie wykonujemy kolejną pracę O ( m n ) w przejściu wstecznym: Gdy przeglądamy listę do tyłu, dla każdej krawędzi musimy dodać do nO(n+m+nm)=O(n3)nmO(n2)O(n+m)O(mn)n wierzchołki do kogoś przechodnie przechodnie.

Zauważ, że możesz uzyskać ładne przyspieszenie o stałym współczynniku, reprezentując przechodnie przechodzenie wszystkich przez tablice bitów. Powiedzmy, że miałeś tylko ; wtedy użyłbyś pojedynczego 64-bitowego int, gdzie bit i ma wartość 1, jeśli i jest w moim przejściowym zamknięciu, a 0 w przeciwnym razie. Następnie część, gdzie możemy dodać wszystko í „s przechodniego zamknięciem j ” s jest bardzo szybki: Po prostu wziąć c j | = c i . (Operacja binarna LUB.)n=64iiijcjci

Dla musielibyście trzymać je w tablicach i wykonywać arytmetykę, ale byłoby to znacznie szybsze niż zestaw obiektów.n>64

Wiem też, że duże- w najgorszym przypadku to wciąż O ( n 3 ) , ale aby pokonać to w praktyce, musiałbyś mieć coś znacznie bardziej złożonego. Algorytm ten działa również bardzo dobrze na rzadkich grafach.OO(n3)

usul
źródło
1
Prawdopodobnie możesz użyć połączonej reprezentacji listy dla zestawów, które w końcu będą miały wspólne ogony.
Kyle Butt,