Jakie jest znaczenie ujemnych krawędzi masy na wykresie?

Robiłem ćwiczenia programowania dynamicznego i znalazłem algorytm Floyda-Warshalla. Najwyraźniej znajduje wszystkie pary najkrótszych ścieżek dla wykresu, który może mieć ujemne krawędzie wagi, ale nie ma ujemnych cykli.

Zastanawiam się więc, jakie jest rzeczywiste znaczenie ujemnych krawędzi wagi? Przydałoby się proste angielskie wyjaśnienie.

Saeed Amiri podał już doskonały przykład w komentarzu: waga na krawędziach może reprezentować wszystko w prawdziwym świecie, na przykład ilość pieniędzy, które należy przenieść z jednego konta na drugie. Kwoty mogą być dodatnie lub ujemne. Na przykład, jeśli chcesz przejść od do na wykresie, tracąc przy tym jak najmniej pieniędzy (najkrótsza ścieżka), możesz rozważyć ujemne wagi. Więcej informacji można znaleźć w tym rozdziale książki .$a$$b$

Oprócz tego istnieje wiele innych aplikacji. Ujemne wagi zależą od tego, jak to modelujesz. Weźmy na przykład ten wykres

• Chemia: Odważniki można wykorzystać do przedstawienia ciepła wytwarzanego podczas reakcji chemicznej. (Tryby: związki, krawędź : jeśli związek można uzyskać („chemicznie zredukowany”) od . Na tym wykresie: wytwarzasz kJ do konwersji i kJ do konwersji do . Potrzebujesz kJ odzyskać od . v u 4 s - a 2 a t 5 s $e_{uv}$$v$$u$$4$$s-a$$2$$a$$t$$5$$s$$t$

• Prawdziwe Życie: Pomyśl o kierowcy, który zarabia na dysk swojego pracodawcę z do ale on płaci pomiędzy i (powiedzmy podróżowanie pomiędzy jego domu i jego pracy).t a $s$$t$$a$$b$

• Gry: Załóżmy, że grasz w papier z kamienia jak kamień. Węzły: kamień, papier, nożyczki. Krawędzie: dowolna relacja (klika). Masy: zakład. Na tym wykresie: (zapomnij o ) tutaj bije , bije i bije i wygrywa odpowiednio 4,2, -5.s a a t t $b$$s$$a$$a$$t$$t$$s$

Nie jestem chemikiem, ale nadal uważam, że ten przykład będzie wart, aby pomóc ci myśleć o procesorze, teorii sieci i pokrewnych sprawach ..

Rozważ wykres symulujący zachowanie cząsteczki w reakcji chemicznej, tj. Jakie ścieżki może ona przebiegać podczas reakcji, a ciężary reprezentują energię pochłoniętą lub uwolnioną podczas przejścia, więc jeśli chcemy energii z reakcji, reprezentujemy energię uwolnioną z dodatnimi ciężarami i pochłoniętymi energia z -ve.

Negatywna krawędź jest po prostu krawędzią o ujemnej wadze. Może być w dowolnym kontekście odnoszącym się do wykresu i do jakich jego krawędzi się odnoszą. Na przykład krawędź CD na powyższym wykresie jest krawędzią ujemną. Floyd-Warshall działa, minimalizując wagę między każdą parą wykresu, jeśli to możliwe. Tak więc dla masy ujemnej można po prostu wykonać obliczenia, jak w przypadku krawędzi dodatniej masy.

Problem powstaje, gdy występuje cykl ujemny. Spójrz na powyższy wykres. I zadaj sobie pytanie - jaka jest najkrótsza droga między A i E? Na początku możesz poczuć, że jego ABCE kosztuje 6 (2 + 1 + 3). Ale w rzeczywistości, patrząc głębiej, można zaobserwować cykl ujemny, którym jest BCD. Waga BCD wynosi 1 + (- 4) +2 = (-1). Podczas przechodzenia z punktu A do punktu E mógłbym ciągle jeździć wewnątrz BCD, aby za każdym razem obniżyć mój koszt o 1. Podobnie ścieżka BCE BCE kosztuje 5 (2 + (- 1) + 1 + 3). Teraz powtarzanie cyklu w nieskończoność razy zmniejszałoby koszt za każdym razem o 1. Mógłbym osiągnąć ujemną, nieskończoną najkrótszą drogę między A i E.

Problem jest widoczny dla każdego ujemnego cyklu na wykresie. Dlatego za każdym razem, gdy występuje cykl ujemny, minimalna waga nie jest zdefiniowana lub jest ujemną nieskończonością, dlatego Floyd-Warshall nie może w takim przypadku działać.

Dodatkowo warto przyjrzeć się algorytmowi Bellmana-Forda, który wykrywa, czy wykres ma cykl ujemny, czy nie, i w przeciwnym razie zwraca najkrótszą ścieżkę między dwoma węzłami.

Na przykład wyobraź sobie sieć logistyczną, w której ciężar w (i, j) krawędzi ij jest kosztem przejścia od wierzchołka i do wierzchołka j. Jeśli zawarłeś umowę biznesową z innymi firmami na transport ich produktów, w (i, j) byłby zyskiem zamiast kosztem, więc możesz interpretować tę wagę jako koszt ujemny.

Korki na mapie:

Innym przykładem powiązania ciężarów z krawędzią w świecie rzeczywistym może być to, że ciężary przedstawiają warunki ruchu na mapie (bardziej negatywne, bardziej niekorzystne) - możemy wtedy użyć tej reprezentacji do obliczenia optymalnych odległości.

Możemy naprawdę użyć metafory „wagi” do przedstawienia wszystkiego o wartości dodatniej / ujemnej między dowolnymi dwoma punktami na wykresie