Welche Bedeutung haben negative Gewichtungskanten in einem Diagramm?

15

Ich machte dynamische Programmierübungen und fand den Floyd-Warshall-Algorithmus. Anscheinend findet es die kürzesten Wege aller Paare für einen Graphen, der negative Gewichtungskanten, aber keine negativen Zyklen haben kann.

Ich frage mich also, was die reale Bedeutung negativer Gewichtsränder ist. Eine einfache englische Erklärung wäre hilfreich.

c2h5oh
quelle
3
Das Kantengewicht kann alles in der realen Welt darstellen, z. B. kann der Geldbetrag, der von einem Konto auf ein anderes Konto überwiesen werden soll, positiv oder negativ sein. Wenn Sie also etwas tun möchten, müssen Sie in Ihrem Diagramm von a-> b mit gehen so gering wie möglich Geld zu verlieren (kürzeste Strecke), dann können Sie eine negative Gewichte betrachten .... zB dieses Buch Kapitel sehen , die einige Beispiele enthält: informit.com/articles/article.aspx?p=169575&seqNum=8
Also, wenn a ---- (2) ----> b ---- (- 2) ----> c und a ----- (1) ----> c und gehen von a bis c, sollte ich den Pfad abc wählen, da die Gesamtkosten 0 sind? weil es der kürzeste Weg ist. korrigiere mich wenn ich falsch liege!
c2h5oh
zB nehme an, wenn Sie Job von Staat zu gehen ein zu b kostet 2 $ (zB Job kauft Buch kostet 2 $ ) nach, dass Sie einige Projekt tun können (Sie erhalten 2 $ , mittels Kostenfunktion - 2), dann hast du deinen Zweck erreicht (beruflich oder c), dann sind die Gesamtkosten 0 und du bist in deinem Zustand. a - (+ 2) -> b - (- 2) -> c: +2 - 2 = 0 (Gesamtkosten von a: Neuling bis c: Profi). e(ab)ab2$$$
Meine Vermutung ist also richtig, auch wenn wir eine Kante mehr zurücklegen müssen, wählen wir abc anstelle von ac.am, oder?
c2h5oh
Ja genau, Ihre Annahme ist richtig. Beachten Sie, dass Sie mehr lesen können (wie den Link, den ich für Sie bereitgestellt habe) oder durch unsere Diskussion Ihre eigene Frage beantworten und als akzeptierte Antwort markieren können.

Antworten:

16

Saeed Amiri hat bereits in einem Kommentar ein hervorragendes Beispiel gegeben: Das Gewicht der Kanten kann alles in der realen Welt darstellen, zum Beispiel den Geldbetrag, der von einem Konto auf ein anderes Konto überwiesen werden soll. Die Beträge können positiv oder negativ sein. Zum Beispiel, wenn Sie von nach b gehen möchtenab in Ihrem Diagramm wechseln und dabei so wenig Geld wie möglich verlieren (kürzester Weg), können Sie negative Gewichte in Betracht ziehen. Weitere Informationen finden Sie in diesem Buchkapitel .

Abgesehen davon gibt es viele weitere Anwendungen. Die negativen Gewichte hängen davon ab, wie Sie es modellieren. Betrachten Sie beispielsweise dieses Diagramm

Bildbeschreibung hier eingeben

  • Chemie: Die Gewichte können verwendet werden, um die Wärme darzustellen, die während einer chemischen Reaktion erzeugt wird. (Modi: Verbindungen, Kante : wenn Verbindungeuv von u erhalten werden kann ("chemisch reduziert"). In diesem Diagramm: Sie produzieren 4 kJ, um s - a und 2 kJ, um a in t umzuwandeln. Sie benötigen 5 kJ, um s von t zurückzubekommen .vu4sa2at5st

  • Real Life: Denken Sie an einen Fahrer, der dafür bezahlt wird, dass er seinen Arbeitgeber von nach t fährt , aber zwischen a und b bezahlt (sagen wir zwischen seinem Zuhause und seinem Arbeitsplatz).stab

  • Spiele: Angenommen, Sie spielen Stein-Papier-Schere für Geld. Knoten: Stein, Papier, Schere. Kanten: jede Beziehung (Clique). Gewichte: Wette. In diesem Diagramm: (vergessen ), hier s Beats ein , eine Beat t und t Beats s und gewinnt 4,2, -5 auf.bsaatts

Subhayan
quelle
Hallo, danke für die Antwort. Kann jemand das Stein-Papier-Scheren-Beispiel erklären? Wie sind Sie auf die Gewichte 4, 2, -5 gekommen?
Saurabh Goyal
3

Ich bin kein Chemiker, aber dennoch denke ich, dass dieses Beispiel es wert sein wird, Ihnen dabei zu helfen, über den Prozessor, die Netzwerktheorie und verwandte Dinge hinauszudenken.

Stellen Sie sich einen Graphen vor, der das Verhalten eines Moleküls in einer chemischen Reaktion simuliert, dh, welche Pfade es während der Reaktion nehmen kann, und Gewichte stellen die Energie dar, die beim Übergang absorbiert oder freigesetzt wird. Wenn wir also Energie aus der Reaktion heraus wollen, stellen wir die freigesetzte Energie mit fünf Gewichten und absorbiert dar Energie mit -ve.

pj
quelle
1

Bildbeschreibung hier eingeben

Eine negative Flanke ist einfach eine Flanke mit einem negativen Gewicht. Es kann sich in jedem Zusammenhang um den Graphen handeln und worauf beziehen sich seine Kanten? Beispielsweise ist die Kante CD in der obigen Grafik eine negative Flanke. Floyd-Warshall minimiert, wenn möglich, das Gewicht zwischen jedem Diagrammpaar. Für ein negatives Gewicht können Sie also einfach die Berechnung durchführen, wie Sie es für positive Gewichtsränder getan hätten.

Das Problem tritt auf, wenn ein negativer Zyklus vorliegt. Schauen Sie sich die obige Grafik an. Und stellen Sie sich die Frage: Was ist der kürzeste Weg zwischen A und E? Sie könnten sich zunächst so fühlen, als würde das ABCE 6 (2 + 1 + 3) kosten. Bei genauerer Betrachtung würde man jedoch einen negativen Zyklus beobachten, der BCD ist. Das Gewicht von BCD beträgt 1 + (- 4) + 2 = (-1). Beim Überqueren von A nach E konnte ich innerhalb von BCD weiterfahren, um meine Kosten jedes Mal um 1 zu senken. Ebenso kostet der Pfad A (BCD) BCE 5 (2 + (- 1) + 1 + 3). Wenn Sie nun den Zyklus unendlich oft wiederholen, werden die Kosten jedes Mal um 1 gesenkt. Ich könnte einen negativen unendlichen kürzesten Weg zwischen A und E erreichen.

Das Problem ist für jeden negativen Zyklus in einer Grafik offensichtlich. Wenn also ein negativer Zyklus vorliegt, ist das Mindestgewicht nicht definiert oder negativ unendlich, sodass Floyd-Warshall in einem solchen Fall nicht arbeiten kann.

Als Ergänzung möchten Sie vielleicht einen Blick auf den Bellman-Ford-Algorithmus werfen, der erkennt, ob ein Graph einen negativen Zyklus hat oder nicht, und auf andere Weise den kürzesten Weg zwischen zwei Knoten zurückgibt.

Divanshu
quelle
4
Ich glaube nicht, dass dies die Frage beantwortet. Die Frage ist nicht "warum ist ein negativer Zyklus ein Problem", sondern "warum sollte man im wirklichen Leben jemals Kanten mit negativen Gewichten haben".
Juho
0

Stellen Sie sich beispielsweise ein logistisches Netzwerk vor, in dem das Gewicht w (i, j) einer Kante ij die Kosten für den Übergang von Scheitelpunkt i zu Scheitelpunkt j sind. Wenn Sie eine Geschäftsvereinbarung mit anderen Unternehmen getroffen haben, um deren Produkte zu transportieren, ist w (i, j) ein Gewinn anstelle von Kosten, sodass Sie dieses Gewicht als negative Kosten interpretieren können.

Luis Pargas Carmona
quelle
-2

Verkehrsstau auf einer Karte:

Ein weiteres Beispiel für die Zuordnung von Gewichten zu einer Kante in der realen Welt könnten die Gewichte sein, die die Verkehrsbedingungen auf einer Karte darstellen (negativer, ungünstiger). Mit dieser Darstellung könnten wir dann die optimalen Entfernungen berechnen.

Wir können die "Gewichts" -Metapher wirklich verwenden, um irgendetwas von positivem / negativem Wert zwischen zwei beliebigen Punkten in einer Grafik darzustellen

Ranga
quelle
Willkommen auf der Seite! Ich denke nicht, dass dies ein sehr gutes Beispiel ist. Bei Verkehrsstaus scheint es natürlicher zu sein, Kanten auf der Karte zu gewichten, bis sie auf der Straße zurückgelegt sind, sodass hohe Verkehrsstaus zu einem hohen Gewicht führen würden. Schließlich geht es in der Regel darum, schnell ans Ziel zu gelangen, und man würde in der Regel lieber eine kurze, aber überlastete Straße als eine viel längere, nicht überlastete Straße nehmen. Außerdem möchten wir in der Regel die niedrigsten Kosten als Metrik verwenden: Das funktioniert gut mit der von mir vorgeschlagenen Gewichtung und sehr schlecht mit der von Ihnen vorgeschlagenen.
David Richerby