wykres - Jak znaleźć minimalny cykl reżyserii (minimalna masa całkowita)?

Question

Oto akcyzy:

Niech G być ważone skierowane wykres z n a m wierzchołków krawędzi, gdzie wszystkie krawędzie mają pozytywny wagi. Kierowany cykl jest skierowaną ścieżką, która rozpoczyna się i kończy w tym samym wierzchołku i zawiera co najmniej jedną krawędź. Podaj algorytm O (n^3), aby znaleźć ukierunkowany cykl w G minimalnej masy całkowitej. Częściowy kredyt zostanie przyznany za algorytm O ((n^2) * m).

---

Oto mój algorytm.

Wykonuję . Za każdym razem, gdy znajduję back edge, wiem, że mam ukierunkowany cykl.

Następnie tymczasowo przejdę wstecz wzdłuż parent array (dopóki nie przejdę przez wszystkie wierzchołki w cyklu) i obliczyć wartość total weights.

Następnie porównuję total weight tego cyklu z min. min zawsze przyjmuje minimalne masy całkowite. Po zakończeniu DFS zostanie również znaleziony nasz minimalny ukierunkowany cykl.

---

Ok, a następnie o złożoności czasu.

Szczerze mówiąc, nie znam złożoności czasu mojego algorytmu.

Dla DFS przejście trwa O (m + n) (jeśli m jest liczbą krawędzi, a n jest liczbą wierzchołków). Dla każdego wierzchołka może wskazywać jednego z jego przodków, a zatem tworzy cykl. Gdy zostanie znaleziony cykl, potrzeba O (n) do podsumowania całkowitej masy.

Uważam, że całkowity czas to O (m + n * n). Ale oczywiście jest źle, jak stwierdzono w akcyzie, optymalny czas to O (n^3), a normalny czas to O (m * n^2).

---

Czy ktoś może mi pomóc z:

1. Czy mój algorytm jest prawidłowy?
2. Jaka jest złożoność czasu, jeśli mój algorytm jest poprawny?
3. Czy istnieje lepszy algorytm dla tego problemu?

Answer 1

można użyć Floyd-Warshall algorytmu tutaj.

algorytm Floyda-Warshalla znajdzie najkrótszą ścieżkę między wszystkich par wierzchołków:

Algorytm to to bardzo proste, przejrzyj wszystkie pary: (u,v) i , znajdź parę, która zminimalizowała dist(u,v)+dist(v,u), ponieważ ta para wskazuje na 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)), należy również sprawdzić je samodzielnie, ponieważ te cykle (i tylko one) nie zostały sprawdzone przez algorytm.

pseudokod:

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) jest rzeczywiście znaleziono ścieżki z U-V, a następnie z v u, który to cykl.

Czas pracy algorytmu to O(n^3), ponieważ floyd-warshall jest szyjką butelki, ponieważ pętla przyjmuje czas O(n^2).

Myślę, że poprawność tutaj jest banalna, ale daj mi znać, jeśli nie zgadzasz się ze mną, a ja postaram się wyjaśnić to lepiej.

Answer 2

„dla każdego wierzchołka może wskazywać z powrotem do jednego z jego przodków i tworzy w ten sposób cykl”

myślę może wskazywać z powrotem do jego przodkach co oznacza N

Również jak zamierzasz oznaczać vertexes, kiedy wyjdziesz z dfs, możesz przyjść tam ponownie z innego wierzchołka i będzie to kolejny cykl. Więc to już nie jest (n + m) dfs.

1. Więc ur algo jest niepełna
2. samo tutaj

3. Podczas jednego dfs, uważam, że wierzchołek powinien być albo niewidoczny, albo sprawdzić, a dla sprawdzenia u może przechowywać minimalną wagę dla ścieżki do początkowego wierzchołka. Więc jeśli na jakimś etapie odkryjesz krawędź tego wierzchołka, nie musisz już szukać tej ścieżki. Ten program dfs znajdzie minimalny ukierunkowany cykl zawierający pierwszy wierzchołek. i jest to O (n^2) (O (n + m) jeśli przechowujesz wykres jako listę)

Więc jeśli zrobić to z dowolnego innego wierzchołka będzie to O (n^3) (O (n * (n + m))

Niestety, za mój angielski, a ja nie jestem dobry w terminologii

Answer 3

Czy mój algorytm jest prawidłowy?

Nie. Pozwól mi podać przykład kontrłaty. Wyobraź sobie, że zaczynają DFS z u istnieją dwie ścieżki p1 i p2 z u do v i 1 ścieżkę p3 z v powrotem do u, p1 jest krótszy niż p2.

Załóżmy zacząć biorąc ścieżkę p2 do v, i iść z powrotem do u przez ścieżkę p3. Znaleziono jeden cykl, ale najwyraźniej nie jest to minimum. Następnie kontynuujesz eksplorację u, przechodząc ścieżkę p1, ale ponieważ v jest w pełni zbadane, DFS kończy się bez znalezienia minimalnego cyklu.