Oto akcyza:
Niech G będzie ważonym grafem skierowanym za pomocą nwierzchołki i krawędzie m, gdzie wszystkie krawędzie mają dodatnią masę. Cykl kierowany to ukierunkowana ścieżka, która zaczyna się i kończy przy tym samym wierzchołku i zawiera co najmniej jedną krawędź. Daj algorytm O (n ^ 3), aby znaleźć ukierunkowany cykl w G o minimalnej masie całkowitej. Częściowy kredyt zostanie przyznany za algorytm O ((n ^ 2) * m).
Oto mój algorytm.
Robię DFS. Za każdym razem, gdy znajdę back edge, Wiem, że mam skierowany cykl.
Potem tymczasowo cofnę się wzdłuż parent array (dopóki nie przejdę przez wszystkie wierzchołki w cyklu) i nie obliczę total weights.
Następnie porównuję total weight tego cyklu z min. min zawsze pobiera minimalną całkowitą wagę. Po zakończeniu DFS znajduje się także nasz minimalny cykl kierowany.
Ok, to o złożoności czasu.
Szczerze mówiąc, nie znam złożoności czasowej mojego algorytmu.
W przypadku DFS przejście wykonuje O (m + n) (jeśli m jest równeliczba krawędzi, a n to liczba wierzchołków). Dla każdego wierzchołka może wskazywać na jednego z jego przodków, tworząc w ten sposób cykl. Gdy cykl zostanie znaleziony, O (n) zajmuje podsumowanie całkowitej masy.
Myślę więc, że całkowity czas to O (m + n * n). Ale oczywiście jest źle, jak stwierdzono w akcyzie, optymalnym czasem jest O (n ^ 3), a normalnym czasem jest O (m * n ^ 2).
Czy ktoś może mi pomóc:
- Czy mój algorytm jest poprawny?
- Jaka jest złożoność czasu, jeśli mój algorytm jest poprawny?
- Czy jest jakiś lepszy algorytm dla tego problemu?
Odpowiedzi:
19 dla odpowiedzi nr 1Możesz użyć Floyd-Warshall algorytm tutaj.
Algorytm Floyd-Warshall znajduje najkrótszą drogę między wszystkie pary wierzchołków.
Algorytm jest wtedy bardzo prosty, przejdź przez wszystkie pary (u,v), i znajdź parę, która zminimalizowała dist(u,v)+dist(v,u), ponieważ ta para wskazuje w cyklu od u do u z wagą dist(u,v)+dist(v,u). Jeśli wykres pozwala również na pętle własne (krawędź (u,u)), musisz także sprawdzić je samodzielnie, ponieważ te cykle (i tylko je) nie zostały sprawdzone przez algorytm.
pseudo kod:
run Floyd Warshall on the graph
min <- infinity
vertex <- None
for each pair of vertices u,v
if (dist(u,v) + dist(v,u) < min):
min <- dist(u,v) + dist(v,u)
pair <- (u,v)
return path(u,v) + path(v,u)
path(u,v) + path(v,u) w rzeczywistości jest to ścieżka znaleziona od u do v, a następnie od v do u, która jest cyklem.
Czas działania algorytmu wynosi O(n^3), ponieważ floyd-warshall jest szyjką butelki, ponieważ pętla trwa O(n^2) czas.
Myślę, że poprawność tutaj jest banalna, ale daj mi znać, jeśli nie zgadzasz się ze mną i postaram się to lepiej wyjaśnić.
2 dla odpowiedzi nr 2
„Dla każdego wierzchołka może wskazywać na jednego z jego przodków, tworząc w ten sposób cykl”
Myślę, że może to wskazywać na któregokolwiek z jego przodków, co oznacza N
Ponadto, jak zamierzasz oznaczać wierzchołki, gdy wychodziłeś z jego dfs, możesz tam wrócić z innego wierzchołka i będzie to kolejny cykl. Więc to już nie jest (n + m) dfs.
- Więc, algo jest niekompletne
- to samo tutaj
3. Podczas jednego dfs myślę, że wierzchołek powinien być albo niewidoczny, albo sprawdź, a dla sprawdzonego u może zapisać minimalną wagę ścieżki do wierzchołka początkowego. Więc jeśli na jakimś innym etapie znajdziesz krawędź tego wierzchołka, nie musisz już szukać tej ścieżki. To dfs znajdzie minimalny ukierunkowany cykl zawierający pierwszy wierzchołek. i to „s O (n ^ 2) (O (n + m), jeśli zapisujesz wykres jako listę)
Jeśli więc zrobimy to z innego wierzchołka, będzie to O (n ^ 3) (O (n * (n + m))
Przepraszam za mój angielski i nie jestem dobry w terminologii
2 dla odpowiedzi nr 3
Czy mój algorytm jest poprawny?
Nie. Podam przykład przeciwny. Wyobraź sobie, że uruchamiasz DFS z u, są dwie ścieżki p1 i p2 od u do v i 1 ścieżka p3 od v wrócić do u, p1 jest krótszy niż p2.
Załóżmy, że zaczynasz od p2 ścieżka do vi wróć do u drogą p3. Znaleziono jeden cykl, ale najwyraźniej nie jest on minimalny. Potem kontynuujesz badanie u biorąc p1 ścieżka, ale od tego czasu v jest w pełni zbadany, DFS kończy się bez znalezienia minimalnego cyklu.