Post on 19-Aug-2018
transcript
Anwendungen von Netzwerkfluss
Wojciech PolcwiartekInstitut für InformatikFU Berlin13. 01. 2009
Aktuelle Themen in der Algorithmik: Anwendungen von Netzwerkfluss
Gliederung
• Einführung• Netzwerk, Fluss und Schnitt• Max-Flow-Min-Cut Theorem
• Algorithmen zum Bestimmen vom maximalen Fluss• Ford – Fulkerson Algorithmus• Edmonds – Karp Algorithmus
• Anwendungen• Bipartites Matching• Zirkulation mit Anforderungen (mit unteren Schranken)• Umfrageentwurf• Bildsegmentierung• Projektauswahl
Aktuelle Themen in der Algorithmik: Anwendungen von Netzwerkfluss
Einführung: Netzwerk
• Ein Netzwerk N=(V, E, s, t, c) ist ... • ein gerichteter Graph
ohne Mehrfachkanten • mit zwei ausgezeichneten Knoten
• Quelle s aus V• Senke t aus V
• mit einer Kapazitätsfunktion c, die jeder Kante e aus E eine nicht-negative, reellwertige Kapazität c(e) zuweist
• Ein Restnetzwerk (Residualnetzwerk) vom N ist ein Netzwerk N'=(V, E, s, t, c'), in dem die Kapazitäten jeder Kante um den Fluss durch diese Kante vermindert wurden
s t
c=1
c=3
c=0
c=2
c=4
c=2
c=3
c=1
Aktuelle Themen in der Algorithmik: Anwendungen von Netzwerkfluss
Einführung: s-t-Fluss
• Ein s-t-Fluss ist eine Funktion f, die jeder Kante e im Netzwerk einen nicht-negativen, reellen Flusswert f(e) zuweist
• Bedingungen vom Fluss:• Kapazitätsbeschränkung
• Flusserhaltung
• Wert vom Fluss im Netzwerk
• Verbesserungspfad ist ein Pfad (v[1], ..., v[k]), wobei • v[1] = s, v[k]=t• c(v[i],v[i+1]) – f(v[i], v[i+1]) > 0
s t
c=1 f=0
c=3 f=1
c=1 f=1
c=2 f=0
c=4 f=1
c=2 f=1
c=3 f=2
c=1 f=0
∑einc v
f e−∑e ausv
f e=0
0 f ec e ,∀ e∈E
Aktuelle Themen in der Algorithmik: Anwendungen von Netzwerkfluss
Einführung: Schnitt
• Ein Schnitt ist eine Menge von Kanten eines Graphen G = (V,E), die zwischen zwei Knotenmengen S und T liegt, wobei••
• Kapazität c(S, T) vom Schnitt (S,T)
s t
c=1
c=3
c=0
c=2
c=4
c=2
c=3
c=1
S
T
S∪T=VS∩T=∅
Aktuelle Themen in der Algorithmik: Anwendungen von Netzwerkfluss
Einführung: Max-Flow-Min-Cut
• Der maximale Fluss im Netzwerk hat genau den Wert dessen minimalen Schnitts.
• Die folgenden Aussagen sind äquivalent:• f ist der maximale Fluss in G• das Restnetzwerk G' enthält keinen Verbesserungspfad• |f| = c(S,T) gilt für irgendeinen Schnitt (S,T)
Aktuelle Themen in der Algorithmik: Anwendungen von Netzwerkfluss
Gliederung
• Einführung• Netzwerk, Fluss und Schnitt• Max-Flow-Min-Cut Theorem
• Algorithmen zum Bestimmen vom maximalen Fluss• Ford – Fulkerson Algorithmus• Edmonds – Karp Algorithmus
• Anwendungen• Bipartites Matching• Zirkulation mit Anforderungen (mit unteren Schranken)• Umfrageentwurf• Bildsegmentierung• Projektauswahl
Aktuelle Themen in der Algorithmik: Anwendungen von Netzwerkfluss
Algorithmen: Ford-Fulkerson
• Erfinder • Lester Randolph Ford, Jr
• beteiligt auch an Bellman-Ford Algorithmus
• Delbert Ray Fulkerson
• Idee:Solange es im Netzwerk einen Verbesserungspfad gibt, richte den Fluss durch diesen Pfad
• Laufzeit: O( |E| * f' ) • f' ist der maximale Fluss im Graphen• Vorsicht: Algorithmus muss nicht terminieren
• Uri Zwick: „The smallest networks on which the Ford-Fulkerson maximum flow procedure may fail to terminate“
Aktuelle Themen in der Algorithmik: Anwendungen von Netzwerkfluss
Algorithmen: Ford-Fulkerson (1/9)
Aktuelle Themen in der Algorithmik: Anwendungen von Netzwerkfluss
Algorithmen: Ford-Fulkerson (2/9)
Aktuelle Themen in der Algorithmik: Anwendungen von Netzwerkfluss
Algorithmen: Ford-Fulkerson (3/9)
Aktuelle Themen in der Algorithmik: Anwendungen von Netzwerkfluss
Algorithmen: Ford-Fulkerson (4/9)
Aktuelle Themen in der Algorithmik: Anwendungen von Netzwerkfluss
Algorithmen: Ford-Fulkerson (5/9)
Aktuelle Themen in der Algorithmik: Anwendungen von Netzwerkfluss
Algorithmen: Ford-Fulkerson (6/9)
Aktuelle Themen in der Algorithmik: Anwendungen von Netzwerkfluss
Algorithmen: Ford-Fulkerson (7/9)
Aktuelle Themen in der Algorithmik: Anwendungen von Netzwerkfluss
Algorithmen: Ford-Fulkerson (8/9)
Aktuelle Themen in der Algorithmik: Anwendungen von Netzwerkfluss
Algorithmen: Ford-Fulkerson (9/9)
Aktuelle Themen in der Algorithmik: Anwendungen von Netzwerkfluss
Algorithmen: Edmonds-Karp
• Erfinder• Yefim Dinitz (1970) (University of the Negev)• Jack Edmonds und Richard Karp (1972) (Univ. of California)
• R. Karp bekannt auch wegen „Karp's 21 NP-C problems“
• IdeeFunktioniert ähnlich zum Ford-Fulkerson Algorithmus.Der Verbesserungspfad wird aber mit Hilfe von Breitensuche ausgewählt, so dass die Länge der Verbesserungspfade steigt.
• Laufzeit: O( |V| * |E|² ) • Beweis: siehe Cormen, Leierson, Rivest und Stein
• O( |E| ) - Verbesserungspfad finden• Jedes Mal wird mind. eine Kante gesättigt• Laenge vom Pfad ist max. |V|
Aktuelle Themen in der Algorithmik: Anwendungen von Netzwerkfluss
Gliederung
• Einführung• Netzwerk, Fluss und Schnitt• Max-Flow-Min-Cut Theorem
• Algorithmen zum Bestimmen vom maximalen Fluss• Ford – Fulkerson Algorithmus• Edmonds – Karp Algorithmus
• Anwendungen• Bipartites Matching• Zirkulation mit Anforderungen (mit unteren Schranken)• Umfrageentwurf• Bildsegmentierung• Projektauswahl
Aktuelle Themen in der Algorithmik: Anwendungen von Netzwerkfluss
Anwendungen: Bipartites Matching
• Reales Problem: Paarung der Menschen
• Bipartites Matching / Paarung /Unabhängige Kantenmenge• Eingabe: ungerichteter, bipatrtiter
Graph• ist ein Matching, wenn zwei
beliebige Kanten aus M mit verschiedenen Knoten inzident sind
• Ziel: finde Paarung mit der höchsten Kardinalität
G=L∪R , E M⊂E
Aktuelle Themen in der Algorithmik: Anwendungen von Netzwerkfluss
Anwendungen: Bipartites Matching
• Formulierung als Netzwerkflussproblem• Erstelle Graph
• Richte alle Kanten von L nach R und weise den unendliche Kapazität zu Füge Quelle s und Senke t hinzu
• Füge Kanten mit einer Kapazität von 1 von der Quelle zu jedem der Knoten aus L
• Füge Kanten mit einer Kapazität von 1 von jedem der Knoten aus R zu der Senke
• Rechne den maximalen Fluss in G' aus
G '=L∪R∪{s , t} ,E '
G G'
Aktuelle Themen in der Algorithmik: Anwendungen von Netzwerkfluss
Anwendungen: Bipartites Matching
Aktuelle Themen in der Algorithmik: Anwendungen von Netzwerkfluss
Anwendungen: Bipartites Matching
Aktuelle Themen in der Algorithmik: Anwendungen von Netzwerkfluss
Anwendungen: Zirkulation mit Anforderungen
• Reales Problem:Mehrere Datenquellen undDatensenken in einem Netzwerk
• Eingabe• Gerichteter Graph G=(V,E)• Kantenkapazität c(e), für alle e aus E• Angebot/Anforderung d(v), für alle v aus V
• Anforderung d(v) > 0 • Angebot d(v) < 0
• Gültige Zirkulation ist eine Funktion, die erfüllt auf solchen Graphen• Kapazitätbeschränkung • Flusserhaltung
0 f ec e ,∀ e∈E∑einc v
f e−∑e ausv
f e=d v
Aktuelle Themen in der Algorithmik: Anwendungen von Netzwerkfluss
Anwendungen: Zirkulation mit Anforderungen
• Nötige Bedingung für eine gültige Zirkulation•
• Formulierung als Netzwerkflussproblem• Erstelle Graph
• Füge eine Quelle s und Senke t hinzu• Verbinde die Quelle mit jedem Knoten mit Angebot mit Hilfe
von einer gerichteter Kante mit der Kapazität -d(v)• Verbinde jeden Knoten mit Anforderung mit der Senke mit Hilfe
von einer gerichteter Kante mit der Kapazität d(v)
∑v :d v0
d v =− ∑v: d v0
d v =D
G '=G∪{s , t }, E '
G G'
Aktuelle Themen in der Algorithmik: Anwendungen von Netzwerkfluss
Anwendungen: Zirkulation mit Anforderungen
• G hat eine gültige Zirkulation, wenn der maximale Fluss in G' den Wert D hat
Aktuelle Themen in der Algorithmik: Anwendungen von Netzwerkfluss
Anwendungen: Zirkulation mit Anforderungen und unteren Schranken
• Reales Problem:Netz der Abwasserkanäle• Minimaler Fluss nötig
• Eingabe• Gerichteter Graph G=(V,E)• Kantenkapazität c(e) und
untere Schranke l(e),für alle e aus E• Angebot/Anforderung d(v), für alle v aus V
• Anforderung d(v) > 0 • Angebot d(v) < 0
• Gültige Zirkulation ist eine Funktion, die erfüllt auf solchen Graphen• Kapazitätbeschränkung • Flusserhaltung
l e f ec e ,∀ e∈E∑einc v
f e−∑e ausv
f e=d v
Aktuelle Themen in der Algorithmik: Anwendungen von Netzwerkfluss
Anwendungen: Zirkulation mit Anforderungen und unteren Schranken
• Formulierung als Netzwerkflussproblem• Erstelle Graph wie in „Zirkulation mit Anforderungen“• Modelliere untere Schranke mit Anforderungen im G'
• Lasse l(e) Fluss durch die Kante durch• Aktualisiere Anforderungen an beiden Enden
• Weiter wie „Zirkulation mit Anforderungen“
G G'
Aktuelle Themen in der Algorithmik: Anwendungen von Netzwerkfluss
Anwendungen: Umfagenentwurf
• Reales ProblemMarktanalysen, Kundenumfragen
• Problem • Frage n Kunden nach m Produkten• Man darf den Kunden i nur dann
nach Produkt j fragen, wenn i j besitzt• Stelle dem Kunden i zwischen c(i) und c'(i) Fragen• Befrage zwischen p(j) und p'(j) Kunden nach Produkt j
• Ziel: Finde eine passende Umfrage, wenn möglich
Aktuelle Themen in der Algorithmik: Anwendungen von Netzwerkfluss
Anwendungen: Umfagenentwurf
• Formulierung als Netzwerkflussproblem• Modelliere Problem als Zirkulation mit unteren Schranken
• Kunden und Produkte als Knoten• Füge zwei Knoten s und t hinzu• Verbinde mit Kunden i und Produkt j, wenn i j besitzt;
Kantenschranken [0,1]• Verbinde s mit allen Kunden; Kantenschranken [c(i),c'(i)]• Verbinde alle Produkte mit t; Kantenschranken [p(j),p'(j)]• Verbinde t mit s; Kantenschranken [0, unendl.]
Aktuelle Themen in der Algorithmik: Anwendungen von Netzwerkfluss
Anwendungen: Umfagenentwurf
• Eine Umfrage existiert wenn es im aufgebauten Graphen eine gültige Zirkulation gibt
Aktuelle Themen in der Algorithmik: Anwendungen von Netzwerkfluss
Anwendungen: Bildsegmentierung
• Reales ProblemErkennung von Objektenauf einem Bild
• Problem • Jedes Pixel i hat ein Maß a(i)>=0,
das seine Ähnlichkeit mitdem Vordergrund A ausdrückt
• Jedes Pixel i hat ein Maß b(i)>=0, das seine Ähnlichkeit mit dem Hintergrund B ausdrückt
• Die Entfernungsstrafe p(i,j)>=0 zwischen zwei Pixeln i und j, von den ein zum Vorder- und ein zum Hintergrund gehört
• Ziel: finde eine Partition• Mit maximalem
oder• Mit minimalem
q A , B=∑i∈A
a i ∑j∈B
b j − ∑ i , j∈E;∣A∩{i , j }∣=1
p i , j
q ' A ,B =∑i∈A
b i ∑j∈B
a j ∑i , j ∈E ;∣A∩ {i , j }∣=1
p i , j
Aktuelle Themen in der Algorithmik: Anwendungen von Netzwerkfluss
Anwendungen: Bildsegmentierung
• Formulierung als Netzwerkflussproblem• Erstelle einen Graph G=(V,E)
• Pixel als Knoten • Füge zwei Knoten s und t hinzu• Verbinde s mit allen Pixeln i; Kantenkapazität a(i)• Verbinde alle Pixeln j mit t; Kantenkapazität b(j)• Verbinde Benachbarte Pixel i und j mit zwei gerichteten Kanten
(entgegen gesetzte Richtung) mit Kapazität p(i,j)
Aktuelle Themen in der Algorithmik: Anwendungen von Netzwerkfluss
Anwendungen: Bildsegmentierung
• Die gesuchte Partition q'(A,B) hat die Größe des Kapazität vom Schnitt c(A,B) c A , B=∑
i∈A
bi ∑j∈B
a j ∑ i , j∈E;∣A∩{i , j }∣=1
p i , j =q ' A ,B
Aktuelle Themen in der Algorithmik: Anwendungen von Netzwerkfluss
Anwendungen: Projektauswahl
• Reales ProblemProjektverwaltung,strategische Planung
• Problem • Es gibt eine Menge der potenziellen
Projekte• Mit Projekt v ist erwarteter Gewinn p(v) verbunden
• Gewinn kann auch negativ sein (Verlust)
• Manche Projekte hängen von anderen ab • Eine Menge der Projekte ist gültig, wenn alle voneinander
abhängige Projekte zu dieser Menge gehören
• Ziel: Finde eine gültige Menge der Projekte, so dass der erwartete Gewinn maximal ist• Eine Partition q(A,B), so dass maximal ist∑
i∈A
p i
Aktuelle Themen in der Algorithmik: Anwendungen von Netzwerkfluss
Anwendungen: Projektauswahl
• Formulierung als Netzwerkflussproblem• Erstelle einen Graph G=(V,E)
• Projekte als Knoten• Füge zwei Knoten s und t hinzu• Verbinde jedes Projekt mit allen seinen Vorbedingungen;
Kantenkapazität = unendl.• Verbinde s mit allen profitablen Projekten; Kantenkapazität p(i)• Verbinde alle verlustbehaftete Projekte mit t;
Kantenkapazität -p(i)
Aktuelle Themen in der Algorithmik: Anwendungen von Netzwerkfluss
Anwendungen: Projektauswahl
• Minimaler Schnitt ist die Partition q(A,B), für die maximal ist
• Die gesuchte Projektmenge ist die Untermenge A \ {s}
∑i∈A
p i
Aktuelle Themen in der Algorithmik: Anwendungen von Netzwerkfluss
Quellen
• Jon Kleinberg, Éva Tardos, „Algorithm Design“
• Folien von K. Wayne, www.cs.princeton.edu/~wayne
• www.wikipedia.org
Aktuelle Themen in der Algorithmik: Anwendungen von Netzwerkfluss
Vielen Dank!