Dlaczego większość algorytmów graficznych nie przystosowuje się tak łatwo do liczb ujemnych?

Question

Algorithm Design Manual mówi:

Większość algorytmów wykres nie tak łatwo dostosować do liczb ujemnych. W rzeczywistości najkrótsze algorytmy ścieżki mają problem z liczbami ujemnymi iz pewnością nie generują najdłuższej możliwej ścieżki za pomocą tej techniki.

Ale dlaczego? Kiedy dodajemy ujemną wartość - przed oryginalną wagą, myślę, że większość problemów związanych z wykresem, które dotyczą wagi, może być rozpatrywana równo, prawda?

Answer 1

Ponieważ podczas rozważania minimalnego lub maksymalnego kosztu ścieżki zawsze kończy się biorąc pod uwagę sumę wszystkich pojedynczych kroków.

A ponieważ wiele z tych algorytmów działa lokalnie, wybierając najlepsze podejście krok po kroku (oczywiście z krokiem o różnej wielkości), posiadanie ujemnych wag generowałoby tylko cykle lub fałszywe alarmy.

Posiadanie ujemnej wagi oznacza, że ​​koszt ścieżki może się zmniejszyć w przyszłości, dlatego stwarza problemy: nie można wykluczyć ścieżek z listy potencjalnych dobrych ścieżek nawet po osiągnięciu punktu, w którym ścieżka do teraz jest droższy od drugiego, ponieważ można znaleźć krawędzie o ujemnej wadze, które zmieniają sytuację.

Tylko jako przykład: jeśli masz dwa węzły połączone wzajemnie przez dwie krawędzie masy 1 i -2 można stworzyć cykl między nimi, aby określić ścieżkę z dowolnego niskim kosztem (nawet -∞).

Answer 2

Rzeczywiście, najkrótsze ścieżki algorytmy mają kłopoty z liczb ujemnych,

Dotyczy to Dijkstra's Algorithm, ale nie dla najkrótszych ścieżek algorytmów w ogóle. Model Bellman-Ford Algorithm może obsługiwać ujemne grubości krawędzi, pod warunkiem, że wykres nie zawiera ujemnych cykli. Jednakże:

Bellman-Ford może wykryć cykli ujemnych i zgłosić swoje istnienie, ale nie może wyprodukować poprawną odpowiedź, jeśli negatywny cykl nie jest osiągalny ze źródła.

Answer 3

Dodam odpowiedź na pytanie dotyczące najkrótszej ścieżki. Ogólny problem z ujemnymi krawędziami jest dobrze opisany w Jack’s answer.

Rozważ wykres G = (V, E) o krawędziach o długości l(e) ≤ 0 dla każdej krawędzi e ∈ E. Najkrótsza ścieżka w G jest taka sama jak najdłuższa ścieżka w G' z l'(e) = - l(e) ≥ 0 ∀e ∈ E. Longest path problem jest znany jako NP-trudny w ogólnych wykresach. Chociaż można go rozwiązać w czasie liniowym w DAG i innych klasach wykresów.

Jako cls answered problem dotyczy tylko cykli ujemnych i Bellman-Ford algorithm radzi sobie z niektórymi krawędziami będącymi ujemnymi. Ale najdłuższy algorytm ścieżki musi radzić sobie z cyklami na wykresie, a Bellman-Ford nie może dać prawidłowej odpowiedzi na wykresach z ujemnymi cyklami. Dlatego algorytm Bellmana-Forda może być użyty do obliczenia najdłuższej ścieżki tylko na wykresach bez dodatnich cykli. Wymienianie, ponieważ ten pomysł to obviously not uncommon.