2WO12: Optimalisering in Netwerken Leo van Iersel Technische Universiteit Eindhoven (TU/E) en Centrum Wiskunde & Informatica (CWI) 24 februari 2014 http://homepages.cwi.nl/~iersel/2WO12/ [email protected] Leo van Iersel (TUE/CWI) 2WO12: Optimalisering in Netwerken 24 februari 2014 1 / 40 Overzicht Tot nog toe: grafen, kleuren en routeren graafrepresentaties en complexiteit Vandaag acyclische gerichte grafen kortste pad algoritmes Leo van Iersel (TUE/CWI) 2WO12: Optimalisering in Netwerken 24 februari 2014 2 / 40 Definitie Een acyclische gerichte graaf is een gerichte graaf die geen gerichte circuits bevat. Lemma Elke acyclische gerichte graaf bevat een punt met ingraad nul en een punt met uitgraad nul. c a b a d f e g Acyclische gerichte graaf Leo van Iersel (TUE/CWI) c b e d f g Cyclische gerichte graaf 2WO12: Optimalisering in Netwerken 24 februari 2014 3 / 40 Toepassing: fylogenetische netwerken Leo van Iersel (TUE/CWI) 2WO12: Optimalisering in Netwerken 24 februari 2014 4 / 40 Definitie Een topologische ordening van een gerichte graaf is een nummering van de punten met volgnummers 1, . . . , n zodanig dat: (i, j) ∈ A =⇒ i <j 1 3 2 4 8 5 6 7 9 Stelling Een gerichte graaf heeft een topologische ordening dan en slechts dan als de graaf acyclisch is. Leo van Iersel (TUE/CWI) 2WO12: Optimalisering in Netwerken 24 februari 2014 5 / 40 Probleem TOPORD Gegeven: gerichte graaf D Gevraagd: is D acyclisch? Zo ja, geef een topologische ordening; zo nee, geef een gericht circuit. Stelling Er bestaat een lineair algoritme voor TOPORD. Leo van Iersel (TUE/CWI) 2WO12: Optimalisering in Netwerken 24 februari 2014 6 / 40 Algoritme (TOPORD) 1 i := 1 2 Als er geen punt met ingraad nul is, dan is er een gericht circuit. Geef zo’n gericht circuit als uitvoer en stop. Als er wel een punt v met ingraad 0 is, doe dan het volgende: 3 I I I 4 Geef punt v nummer i Verwijder v (en alle pijlen die uit v vertrekken) uit de graaf i := i + 1 Herhaal stappen 2 en 3 totdat alle punten uit de graaf verwijderd zijn Leo van Iersel (TUE/CWI) 2WO12: Optimalisering in Netwerken 24 februari 2014 7 / 40 Toepassing: voorkeurslijstjes Stel er zijn n kandidaten en m beoordelers die elk een voorkeurslijst hebben ingediend. Gevraagd wordt om een volgorde van de kandidaten te vinden die met alle voorkeurslijsten overeenstemt. Voorbeeld Kandidaten: A,B,C,D,E Beoordeler 1: B,A,E Beoordeler 2: D,C,E Beoordeler 3: D,E Beoordeler 4: D,C,A Leo van Iersel (TUE/CWI) 2WO12: Optimalisering in Netwerken 24 februari 2014 8 / 40 Probleem Kortste Pad Gegeven: D = (V , A), lengtefunctie ` : A → R en punt s ∈ V Bepaal: voor alle t ∈ V een s − t pad P in D van minimale lengte X `(a) a∈A(P) A(P) is de verzameling pijlen van pad P d(u, v ) is de lengte van een kortste pad van u naar v Leo van Iersel (TUE/CWI) 2WO12: Optimalisering in Netwerken 24 februari 2014 9 / 40 Algoritme voor Kortste Pad in een acyclische gerichte graaf: Algoritme Zet de punten in topologische volgorde 1, 2, . . . , n. Neem aan dat s = 1. d(1) := 0, A0 := ∅ Voor i = 2, . . . , n I d(i) := min d(k) + `(k, i) k<i|(k,i)∈A I Voeg een pijl (k, i) waarvoor dit minimum wordt aangenomen toe aan verzameling A0 d(i) is de afstand van s tot i over een kortste pad De pijlen van A0 vormen een kortste-pad-boom. D.w.z. elk pad dat alleen pijlen van A0 gebruikt is een kortste pad. Leo van Iersel (TUE/CWI) 2WO12: Optimalisering in Netwerken 24 februari 2014 10 / 40 Voorbeeld Vind de lengte van een kortste pad vanuit s naar elk ander punt. s 3 3 5 1 2 3 1 Leo van Iersel (TUE/CWI) 3 2 7 3 3 2 2WO12: Optimalisering in Netwerken 24 februari 2014 11 / 40 Voorbeeld Een topologische ordening van de punten is: (s, a, b, c, d, e, f , g , h). s 3 3 a 5 1 Leo van Iersel (TUE/CWI) 3 2 c 2 d 1 f b 3 e g 7 3 3 2 h 2WO12: Optimalisering in Netwerken 24 februari 2014 12 / 40 Toepassing: projectplanning Voorbeeld Gegeven zijn een aantal taken die uitgevoerd moeten worden en zogenaamde precedentie-eisen, bovendien heeft elke taak een zekere tijdsduur. Plan de taken zo in dat aan alle precedentieeisen voldaan wordt en de laatste taak zo vroeg mogelijk is afgerond. Modelleer als kortste pad probleem in gerichte acyclische graaf: punten zijn taken pijlen zijn precedentie-eisen lengte van pijl (u, v ) is tijdsduur van taak v de korst mogelijke tijdsduur van het totale project is nu: min duur(s) + max d(s, t) s∈V Leo van Iersel (TUE/CWI) t∈V \{s} 2WO12: Optimalisering in Netwerken 24 februari 2014 13 / 40 Algoritme voor kortste pad in een ongewogen (gerichte) graaf: Algoritme V0 := {s} V1 , . . . , Vn , A0 := ∅ Voor i = 1, . . . , |V | I I voor elke v ∈ V \ (V0 ∪ V1 ∪ . . . ∪ Vi ), als er een u ∈ Vi is waarvoor (u, v ) ∈ A, dan F F stop v in Vi+1 stop (u, v ) in A0 (voor ´e´en zo’n u) Vi bevat de punten met afstand i van s (via een kortste pad) V 0 := V0 ∪ V1 ∪ . . . ∪ Vn bevat all punten bereikbaar vanuit s (V 0 , A0 ) is een kortste-pad-boom vanuit s, d.w.z. elk s-v pad in (V 0 , A0 ) is een kortste pad in D Leo van Iersel (TUE/CWI) 2WO12: Optimalisering in Netwerken 24 februari 2014 14 / 40 Voorbeeld Vind een kortste-pad-boom vanuit s. s b a c g d f Leo van Iersel (TUE/CWI) e h 2WO12: Optimalisering in Netwerken 24 februari 2014 15 / 40 Stelling Het algoritme voor het vinden van een kortste pad in een ongewogen graaf heeft looptijd O(|A|). Definitie Een s − t snede (cut) is een verzameling δ + (U) voor U ⊂ V met s ∈ U en t ∈ V \ U. Stelling De lengte van een kortste s − t pad is gelijk aan het maximale aantal disjuncte s − t snedes. Leo van Iersel (TUE/CWI) 2WO12: Optimalisering in Netwerken 24 februari 2014 16 / 40 Algoritme van Dijkstra voor het vinden van kortste paden in een graaf met niet-negatieve lengtefunctie ` : A → Q+ Algoritme U := V f (s) := 0 f (v ) := ∞ voor alle v 6= s Herhaal tot U leeg is: 1 Vind u ∈ U met minimale f (u) 2 Voor elke a = (u, v ) ∈ A met f (v ) > f (u) + `(a) I I f (v ) := f (u) + `(a) verwijder u uit U Na afloop is f (t) de afstand van s tot t, voor alle t ∈ V Een kortste-pad-boom wordt gegeven door de verzameling pijlen A0 met voor elke v ∈ V een pijl a = (u, v ) ∈ A met f (v ) = f (u) + `(a) Leo van Iersel (TUE/CWI) 2WO12: Optimalisering in Netwerken 24 februari 2014 17 / 40 Voorbeeld Vind de afstand over een kortste pad van s naar elk ander punt. s 4 3 a 5 c 2 d 1 f Leo van Iersel (TUE/CWI) b 2 3 1 2 4 e g 4 2 1 h 2WO12: Optimalisering in Netwerken 24 februari 2014 18 / 40 Stelling Voor een gerichte graaf D = (V , A) met niet-negatieve lengtefunctie ` en s, t ∈ V is de waarde f (t) gevonden door het algoritme van Dijkstra de lengte van een kortste s-t pad in D. Stelling Dijkstra’s algoritme heeft een looptijd van O(|V |2 ). Leo van Iersel (TUE/CWI) 2WO12: Optimalisering in Netwerken 24 februari 2014 19 / 40 Definitie Een binaire heap voor een functie f : V → R is een binaire boom T = (V , A) waarvoor geldt: als (u, v ) ∈ A dan f (u) ≤ f (v ) alle lagen m.u.v. de laatste laag zijn volledig gevuld s(0) a(5) c(5) f(7) b(4) g(7) d(7) e(1) h(1) Lemma Gegeven een binaire heap voor f : V → R, kunnen we in constante tijd een element v ∈ V vinden waarvoor f (v ) minimaal is. Leo van Iersel (TUE/CWI) 2WO12: Optimalisering in Netwerken 24 februari 2014 20 / 40 Lemma Na het verwijderen van het element v ∈ V waarvoor f (v ) minimaal is kunnen we de binaire heap “repareren” in tijd O(log(|V |)). s(0) a(5) c(5) f(7) b(4) g(7) d(7) e(1) h(1) Leo van Iersel (TUE/CWI) 2WO12: Optimalisering in Netwerken 24 februari 2014 21 / 40 Lemma Na het verwijderen van het element v ∈ V waarvoor f (v ) minimaal is kunnen we de binaire heap “repareren” in tijd O(log(|V |)). h(1) a(5) c(5) b(4) g(7) d(7) e(1) f(7) Leo van Iersel (TUE/CWI) 2WO12: Optimalisering in Netwerken 24 februari 2014 22 / 40 Lemma Na het verwijderen van het element v ∈ V waarvoor f (v ) minimaal is kunnen we de binaire heap “repareren” in tijd O(log(|V |)). b(4) a(5) c(5) h(1) g(7) d(7) e(1) f(7) Leo van Iersel (TUE/CWI) 2WO12: Optimalisering in Netwerken 24 februari 2014 23 / 40 Lemma Na het verwijderen van het element v ∈ V waarvoor f (v ) minimaal is kunnen we de binaire heap “repareren” in tijd O(log(|V |)). b(4) d(7) a(5) c(5) g(7) h(1) e(1) f(7) Leo van Iersel (TUE/CWI) 2WO12: Optimalisering in Netwerken 24 februari 2014 24 / 40 Lemma Na het verlagen van f (v ) voor een v ∈ V kunnen we de binaire heap “repareren” in tijd O(log(|V |)). b(4) d(7) a(5) c(5) g(2) h(1) e(1) f(7) Leo van Iersel (TUE/CWI) 2WO12: Optimalisering in Netwerken 24 februari 2014 25 / 40 Lemma Na het verlagen van f (v ) voor een v ∈ V kunnen we de binaire heap “repareren” in tijd O(log(|V |)). b(4) g(2) c(5) d(7) a(5) h(1) e(1) f(7) Leo van Iersel (TUE/CWI) 2WO12: Optimalisering in Netwerken 24 februari 2014 26 / 40 Lemma Na het verlagen van f (v ) voor een v ∈ V kunnen we de binaire heap “repareren” in tijd O(log(|V |)). g(2) b(4) c(5) d(7) a(5) h(1) e(1) f(7) Leo van Iersel (TUE/CWI) 2WO12: Optimalisering in Netwerken 24 februari 2014 27 / 40 Stelling Een implementatie van Dijkstra’s algoritme met een binaire heap heeft een looptijd van O(|A| log(|V |)). Stelling Een implementatie van Dijkstra’s algoritme met een “Fibonacci heap” heeft een looptijd van O(|A| + |V | log(|V |)). Leo van Iersel (TUE/CWI) 2WO12: Optimalisering in Netwerken 24 februari 2014 28 / 40 Kortste paden in gewogen grafen met willekeurige lengtefunctie ` : A → Q, dus negatieve lengtes zijn toegestaan! Een “path” in the CO dictaat noemen wij een “wandeling” Een “simple path” in het CO dictaat noemen wij een “pad” Als negatieve lengtes zijn toegestaan, dan hoeft een kortste s − t wandeling niet te bestaan Voorbeeld In de onderstaande graaf bestaat er geen kortste s-t wandeling door een gericht circuit (a, b, c, d, e) met negatieve lengte 3 − 1 − 3 + 2 − 2 = −1. a 3 s 3 -2 b Leo van Iersel (TUE/CWI) -2 -1 c e -1 2 -3 t d 2WO12: Optimalisering in Netwerken 2 24 februari 2014 29 / 40 Stelling Gegeven D = (V , A) en ` : A → R met `(C ) ≥ 0 voor elk gericht circuit C . Als er dan een s − t pad bestaat, dan bestaat er ook een kortste s-t wandeling, en er bestaat een kortste s-t wandeling die een s − t pad is. Leo van Iersel (TUE/CWI) 2WO12: Optimalisering in Netwerken 24 februari 2014 30 / 40 Probleem Gegeven: gewogen graaf D = (V , A) met lengtefunctie ` : A → Q zonder gerichte circuits met negatieve lengte en s ∈ V . Vind: een kortste s − t pad voor alle t ∈ V . Algoritme van Bellman en Ford. Algoritme f0 (s) := 0 f0 (v ) := ∞ voor alle v 6= s Voor k = 0, 1, . . . , n − 1 Voor alle v ∈ V fk+1 (v ) := min{fk (v ), min (fk (u) + `(u, v ))} (u,v )∈A Na afloop is fn−1 (t) de afstand van s tot t (via een kortste pad), voor alle t ∈ V (met n = |V |) Leo van Iersel (TUE/CWI) 2WO12: Optimalisering in Netwerken 24 februari 2014 31 / 40 Voorbeeld Voer het Bellman-Ford algoritme uit op de onderstaande graaf. a 2 1 c s -4 2 d 2 f 1 -1 e Leo van Iersel (TUE/CWI) b -3 -2 h -1 1 -3 2WO12: Optimalisering in Netwerken g 3 24 februari 2014 32 / 40 a 2 1 c s 2 e s 0 0 0 0 0 0 0 0 Leo van Iersel (TUE/CWI) a ∞ 2 2 2 2 2 2 2 -4 -2 d 2 f 1 -1 f0 f1 f2 f3 f4 f5 f6 f7 b -3 b ∞ ∞ −1 −1 −1 −1 −1 −1 c ∞ ∞ 0 0 0 0 0 −4 d ∞ ∞ ∞ −5 −5 −5 −5 −5 1 g -3 e ∞ −1 −1 −1 −1 −1 −5 −5 h -1 f ∞ ∞ ∞ ∞ −3 −3 −3 −3 2WO12: Optimalisering in Netwerken 3 g ∞ ∞ ∞ ∞ ∞ −2 −2 −2 h ∞ ∞ ∞ −3 −3 −4 −4 −4 24 februari 2014 33 / 40 Voorbeeld Voor elk punt v is fn−1 (v ) de afstand van s tot v (via een kortste pad). a 2 0 s 2 -1 -3 1 -1 -4 -5 1 e -5 Leo van Iersel (TUE/CWI) -4 2 c b -3 -2 d 2 -3 -1 f 1 3 g -2 2WO12: Optimalisering in Netwerken -4 h 24 februari 2014 34 / 40 Voorbeeld De dikke lijnen vormen een kortste-pad-boom. a 2 0 s 2 -1 -3 1 -1 -4 -5 1 e -5 Leo van Iersel (TUE/CWI) -4 2 c b -3 -2 d 2 -3 -1 f 1 3 g -2 2WO12: Optimalisering in Netwerken -4 h 24 februari 2014 35 / 40 Lemma Voor alle k = 0, . . . , n − 1 en alle v ∈ V : fk (v ) = min{`(P) | P is een s − v wandeling over hoogstens k pijlen} Stelling Gegeven een gerichte graaf D = (V , A), s, t ∈ V en een lengtefunctie ` : A → Q zodanig dat D geen gericht circuit met negatieve lengte heeft, kan men een kortste s − t pad vinden in tijd O(|V ||A|). Leo van Iersel (TUE/CWI) 2WO12: Optimalisering in Netwerken 24 februari 2014 36 / 40 Stelling (1.5) Laat D = (V , A) een gerichte graaf zijn, s, t ∈ V en ` : A → Z+ een lengtefunctie. De minimale lenge van een s − t pad is gelijk aan het maximale aantal s − t snedes C1 , . . . , Ck (herhaling toegestaan) waarvoor geldt dat elke a ∈ A in hooguit `(a) van deze snedes voorkomt. Leo van Iersel (TUE/CWI) 2WO12: Optimalisering in Netwerken 24 februari 2014 37 / 40 Toepassing: sociale netwerken Kortste paden tussen Facebook gebruikers Leo van Iersel (TUE/CWI) 2WO12: Optimalisering in Netwerken 24 februari 2014 38 / 40 Toepassing: sociale netwerken Samenhangende componenten van de Facebook graaf Leo van Iersel (TUE/CWI) 2WO12: Optimalisering in Netwerken 24 februari 2014 39 / 40 Kortste pad d.m.v. slijmzwam http://www.youtube.com/watch?v=czk4xgdhdY4 Leo van Iersel (TUE/CWI) 2WO12: Optimalisering in Netwerken 24 februari 2014 40 / 40
© Copyright 2024 ExpyDoc
