Czy minimalne drzewo opinające obawia się ujemnych wag?

To jest kontynuacja pytania od Why most graph algorithms do not adapt so easily to negative numbers?.Czy minimalne drzewo opinające obawia się ujemnych wag?

myślę Najkrótsza ścieżka (SP) ma problem z ujemnymi wagami, ponieważ dodaje wszystkie wagi ścieżkami i próbuje znaleźć minimalny jeden.

Ale nie sądzę, że minimalne drzewo opinające (MST) ma problemy z ujemnymi wagami, ponieważ ma tylko jeden minimalny spadek wagi bez dbałości o całkowitą wagę całkowitą.

Mam rację?

Źródło

2012-05-02 Jackson Tale

za [komputer naukowy @ stackexchange] (http://cs.stackexchange.com/)? – HongboZhu

@HongboZhu tak, może następnym razem –

BTW, gdy wszystkie krawędzie na wykresie są ujemne, znalezienie najkrótszej ścieżki jest tym samym problemem, co znalezienie najdłuższej ścieżki do wykresu z krawędziami oznaczonymi bezwzględną wartością ich pierwotnej długości. Najdłuższy problem ze ścieżką jest znany jako NP-trudny. – Palec

Tak, masz rację. Koncepcja MST dopuszcza wagi dowolnego znaku. Dwa najbardziej popularne algorytmy do wyszukiwania MST (Kruskala i Prima) działają dobrze z ujemnymi krawędziami.

Faktycznie, można po prostu dodać dużą dodatnią stałą dla wszystkich krawędzi wykresu, dzięki czemu wszystkie krawędzie pozytywne. MST (jako podzbiór krawędzi) pozostanie taki sam.

Źródło

2012-05-02 12:54:21 Skiminok

Fakt, że drzewo będące pod-grafem wykresu ma stałą liczbę krawędzi w zależności od liczby wierzchołków, więc dodanie liczby 'p' do każdego kosztu krawędzi zwiększa całkowity koszt mst' pE'. Nie jest to prawda w znalezieniu najkrótszej ścieżki, ponieważ najkrótsze ścieżki mogą składać się z różnej liczby krawędzi. – enedil

Dwa najbardziej popularne algorytmy do wyszukiwania MST (Kruskala i Prima) działają dobrze z ujemnymi krawędziami, ponieważ działają na niekierowanych wykresach – raghavsood33

Tak, masz rację, ponieważ jeśli zobaczysz algorytm dla najkrótszej ścieżki, jak dijkstera, sprawdzi on, czy obecna odległość wierzchołka v jest większa niż suma obecnej wartości + grubość krawędzi, to zmieni wartość odległości wierzchołka v od s przez wartość sumy i jeśli waga krawędziowa jest ujemna, spowoduje to pewne problemy.

Ale problem MST istnieją algorytmy jak Prims, Kruskala-, który trwa tylko minimalną przewagę masy, tak aby sprawić, że negatywne krawędź zakwalifikować do MST.

Źródło

2017-02-13 08:05:19

Czy minimalne drzewo opinające obawia się ujemnych wag?

Odpowiedz

Powiązane problemy