Minimale Kostenflüsse: Reduzierte Kantenkosten < 0?

Moderator: Effiziente Graphenalgorithmen

Benutzeravatar
Arki
Mausschubser
Mausschubser
Beiträge: 62
Registriert: 15. Sep 2004 00:47
Wohnort: Darmstadt
Kontaktdaten:

Minimale Kostenflüsse: Reduzierte Kantenkosten < 0?

Beitrag von Arki »

In Übung 8 hatten wir uns in der 1. Aufgabe mit optimalen Knotenpotenzialen \(\pi(v)\) beschäftigt und den Graphen so transfomiert, dass der Fluss mit einem Maxflow-Algorithmus gefunden werden kann.

Wenn ich mich recht erinnere, dann gingen wir dabei so vor: Wir berechnen die reduzierten Kantenkosten \(c^{\pi}_{vw}\) in Bezug auf \(\pi\). In der Besprechung der Übung wurden die nachfolgenden Fälle durchgesprochen:
1. Fall: \(c^{\pi}_{vw} = 0\): Diese Kanten liegen im Fluss, die Frage ist, wieviel Fluss sie letzen Endes tragen werden.
2. Fall: \(c^{\pi}_{vw} > 0\): Diese Kanten liegen definitiv nicht im Fluss, also werden sie aus dem Graphen entfernt.
3. Fall: \(c^{\pi}_{vw} < 0\): Diese Kanten können direkt saturiert werden.

Meine Frage ist: Wie kann sich Fall 3 überhaupt ergeben? Ich habe mir dazu das Skript angeschaut und dort wird \(c^{\pi}_{vw} \ge 0\) festgehalten. Von negativen reduzierten Kantenkosten ist dort nicht die Rede. Wie kommt man also auf die Lösung?

Grüße,
Markus
Der Biber machts richtig: Nagt alles kaputt!

Benutzeravatar
Stille
Moderator
Moderator
Beiträge: 195
Registriert: 3. Jul 2008 10:11

Re: Minimale Kostenflüsse: Reduzierte Kantenkosten < 0?

Beitrag von Stille »

Arki hat geschrieben: Meine Frage ist: Wie kann sich Fall 3 überhaupt ergeben? Ich habe mir dazu das Skript angeschaut und dort wird \(c^{\pi}_{vw} \ge 0\) festgehalten. Von negativen reduzierten Kantenkosten ist dort nicht die Rede. Wie kommt man also auf die Lösung?
Niemand sonst?

Sie meinen sicherlich Theorem 91. \(c^{\pi}_{vw} \ge 0\) ist ein Optimalitätskriterium, keine allgemeine Aussage.

Reduzierte Kosten können durchaus negativ sein (vgl. Folie 218). Daher können die entsprechenden Kanten in Aufgabe 8.1 auch direkt saturiert werden.
Wolfgang Stille
UKP Lab - FB Informatik
http://www.ukp.informatik.tu-darmstadt.de

Benutzeravatar
Stille
Moderator
Moderator
Beiträge: 195
Registriert: 3. Jul 2008 10:11

Re: Minimale Kostenflüsse: Reduzierte Kantenkosten < 0?

Beitrag von Stille »

Nachtrag: Letztlich entsprechen die oben von Ihnen genannten drei Fälle dem Optimalitätskriterium \(c^{\pi}_{vw} \ge 0\), denn
nehmen wir an, es gäbe Kanten mit der folgenden Eigenschaft:

1. Fall: \(c^{\pi}_{vw} = 0\): Diese Kanten sind kostenneutral und daher beliebig benutzbar, ohne die Gesamtkosten zu ändern.
2. Fall: \(c^{\pi}_{vw} > 0\): Diese Kanten würden bei Benutzung die Kosten erhöhen. Sie sind daher ungeeignet.
3. Fall: \(c^{\pi}_{vw} < 0\): Diese Kanten senken die Kosten. Sie werden folglich saturiert. Die entsprechenden Rückwärtskanten im Residualgraphen sind Typ-2-Kanten, da \(c^{\pi}_{vw} = -c^{\pi}_{wv}\).

Gäbe es folglich Typ-3-Kanten in einer Lösung, so wäre diese nicht optimal. Daher die Bedingung \(c^{\pi}_{vw} \ge 0\).
Wolfgang Stille
UKP Lab - FB Informatik
http://www.ukp.informatik.tu-darmstadt.de

Benutzeravatar
Arki
Mausschubser
Mausschubser
Beiträge: 62
Registriert: 15. Sep 2004 00:47
Wohnort: Darmstadt
Kontaktdaten:

Re: Minimale Kostenflüsse: Reduzierte Kantenkosten < 0?

Beitrag von Arki »

Danke für die Hilfestellung! Mir ist inzwischen klar geworden, wo bei der Sache mein Denkfehler gelegen hat ;).
Der Biber machts richtig: Nagt alles kaputt!

Siggi
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 101
Registriert: 15. Okt 2006 12:46

Re: Minimale Kostenflüsse: Reduzierte Kantenkosten < 0?

Beitrag von Siggi »

[edit] hat sich erledigt[/edit]

marluwie
Mausschubser
Mausschubser
Beiträge: 99
Registriert: 18. Okt 2005 22:33

Re: Minimale Kostenflüsse: Reduzierte Kantenkosten < 0?

Beitrag von marluwie »

Hallo!

Ich habe noch eine Frage zur dritten Möglichkeit die Kantenkosten positiv zu kriegen (Folie 217). Wenn es disjunkte Mengen S und V \ S gibt, die entweder von s oder \(\bar{s}\) erreichbar sind. Wie kann es dann Kanten (u, v) und (v, u) geben. Denn schließlich gibt es Gewichte für diese Kanten. Angenommen es sei ausreichend, dass S und V \ S von s oder \(\bar{s}\) erreichbar sind. Es kann also Knoten geben, die von beiden Startknoten erreichbar sind. Wie ist dann \(\pi(u)\) definiert, wenn u von s und \(\bar{s}\) erreichbar ist? Immer von \(\bar{s}\) aus ("\(\pi(u)\) have been set by shortest path distances from \(\bar{s}\)")? Durch die Addition von \(\bar{c}\) verfälschen wir doch das Ergebnis. Kommt das nicht einfach dem Ansatz gleich, dass ich auf alle Kantengewichte eine große Zahl addiere, so dass sie positiv werden? Ginge das dann nicht so einfacher :) ? (Die Antwort ist hoffentlich nein. Sonst kann das nämlich mit den negativen Zyklen auch gemacht werden)
"You can't change anything by fighting or resisting it. You change something by making it obsolete through superior methods." (Buckminster Fuller)

Benutzeravatar
Stille
Moderator
Moderator
Beiträge: 195
Registriert: 3. Jul 2008 10:11

Re: Minimale Kostenflüsse: Reduzierte Kantenkosten < 0?

Beitrag von Stille »

Ja, die Antwort lautet "Nein", Gegenbeispiel wurde bei Johnson's Algorithmus gemacht: einfach zwei disjunkte s,t-Pfade, einer bestehend aus 2 Kanten, einer aus 3 Kanten, Kantengewichte jeweils -1. Kürzester Weg geht über den 3-Kanten-Pfad, nach der Addition der Kantengewichte mit großer Zahl jedoch nicht mehr.

Hier geht es ja darum, optimale Knotenpotentiale zu erhalten. Man betrachtet zuerst die Menge der von s aus erreichbaren Knoten, im zweiten Schritt dann die bisher noch nicht erreichten, usw.
Wolfgang Stille
UKP Lab - FB Informatik
http://www.ukp.informatik.tu-darmstadt.de

Antworten

Zurück zu „Effiziente Graphenalgorithmen“