Algoritmiek 2012/12
College 12
Twaalfde college complexiteit 11 mei 2012 Overzicht, MST 1
Algoritmiek 2012/12
Agenda voor vandaag
Minimum Opspannende Boom (minimum spanning tree) als voorbeeld van greedy algoritmen Overzicht: wat voor technieken hebben we behandeld, wat zijn de voor en nadelen van de verschillende technieken, wat pas je wanneer toe? Vraag en antwoord - wat voor stof willen jullie nog herhaald zien
2
Algoritmiek 2012/12
Een kabelprobleem
Stel, een kabelmaatschappij (zoals Ziggo) wil in een nieuwbouwwijk kabels aanleggen om de woningen met elkaar te verbinden. Vanwege allerlei beperkingen (riolering, gasleidingen e.d.) kunnen niet tussen alle woningen kabels getrokken worden. Waar dit wel kan, zijn de kosten verschillend: bijvoorbeeld door de afstand, type ondergrond en dergelijke). Bepaal voor de kabelmaatschappij een zo voordelig mogelijke oplossing die alle woningen verbindt, en die minimale kosten heeft.
3
Algoritmiek 2012/12
Minimum Opspannende Boom
Dit probleem kun je vertalen naar het vinden van een minimum opspannende boom oftewel minimum spanning tree in een gewogen ongerichte graaf. Een opspannende boom is een subset van de edges in de graaf, die onderling een boom vormt (dus: alles is met elkaar verbonden en er zijn geen cycles) en die alle knopen onderling verbindt. In een gewogen graaf is de minimaal opspannende boom degene met het laagste gewicht. 4
Algoritmiek 2012/12
Eigenschappen MOB
• Een opspannende boom over n knopen heeft precies n − 1 kanten (want?) • Er kunnen meerdere opspannende bomen zijn met hetzelfde gewicht. In het bijzonder, als alle gewichten identiek zijn is iedere opspannende boom een minimum opspannende boom • Aan de andere kant: een graaf met unieke gewichten heeft precies ´ e´ en MOB (gaan we bewijzen) • Als een graaf een cycle heeft, zit de edge met het hoogste gewicht nooit in de MOB (gaan we bewijzen). 5
Algoritmiek 2012/12 Unieke gewichten = unieke MOB -1-
Stelling: een graaf met alle gewichten verschillend heeft precies ´ e´ en minimum opspannende boom Bewijs: dit bewijzen we met een bewijs uit het ongerijmde: we nemen aan dat er twee MOB’s zijn in dit geval, en leiden daar een logische inconsistentie uit af. De aanname (er zijn twee MOB’s) kan daarom niet juist zijn, ergo, er is maar ´ e´ en MOB Laat A en B de twee verschillende MOBs zijn van een graaf G
6
Algoritmiek 2012/12 Unieke gewichten = unieke MOB -2-
A en B zijn verschillend, dus niet alle kanten die in A zitten, zitten ook in B. Neem e1 als een kant die wel in A zit, maar niet in B. B is een MOB, en e1 zit niet in B. Het toevoegen van e1 aan B introduceert een cycle C Op deze cycle C ligt minimaal ´ e´ en edge e2 die niet in A ligt anders was B geen opspannende boom!
7
Algoritmiek 2012/12 Unieke gewichten = unieke MOB -3e1 en e2 hebben niet hetzelfde gewicht - alle gewichten waren immers verschillend in G Neem aan dat het gewicht van e1 lager is dan dat van e2. Dan leidt het vervangen van e2 door e1 in B tot de opspannende boom B ∪ {e1} − {e2} met een lager gewicht als B → B was dus geen MOB! Neem aan dat het gewicht van e1 hoger is dan dat van e2. Dan leidt het vervangen van e1 door e2 in A tot de opspannende boom A ∪ {e2} − {e1} met een lager gewicht als A → A was dus geen MOB! Conclusie: er kunnen geen twee MOB’s bestaan! 8
Algoritmiek 2012/12
Zwaarste/lichtste edge op cycle
Als een graaf G een cycle C heeft, kan de edge met het hoogste gewicht nooit in een MOB zitten. Immers, in een cycle met m kanten behoren maximaal m − 1 kanten tot de MOB (anders introduceren we een cycle in de MOB). Stel dat e1 de edge met het hoogste gewicht op C is, en behoort tot een opspannende boom. Dan kunnen we e1 vervangen door een andere edge op C met lager gewicht en dus een lager totaalgewicht voor de MOB krijgen. In de graaf hiernaast is (B, C) weliswaar de edge met het laagste gewicht op de cycle A, B, C, maar deze zal niet in de MOB terecht komen: het is immers ook de edge met het hoogste gewicht op de cycle B, C, D.
A
5
5
4
C
3
B 3 D 9
Algoritmiek 2012/12
Algoritmen
Hoe vinden we nu een MOB in een gegeven gewogen ongerichte graaf? Hiervoor zijn twee bekende algoritmen: het algoritme van Kruskal (Joseph Kruskal, 1956) en het algoritme van Prim (Robert Prim, 1957, maar al eerder (in 1930) onafhankelijk door de Tsjech Vojtˇ ech Jarn´ık). Beide algoritmen zijn greedy. De looptijd is vergelijkbaar (met optimale datastructuren), namelijk O(E lg V ). Deze looptijden gaan we overigens niet bewijzen. Intuitief: Kruskal groeit meerdere sub-boompjes tegelijkertijd, Prim groeit ´ e´ en subboom. Prim is iets simpeler. 10
Algoritmiek 2012/12
Algoritme van Prim
Initieel beginnen we met een lege tree, d.w.z. een lege set met knopen V en lege set met edges E. We kiezen een random startknoop X, zodat V = {X}. Bij iedere stap in het algoritme, kiezen we een edge (u, v) met u in V die minimum gewicht heeft. We voegen v toe aan V en (u, v) aan E. Het algoritme eindigt wanneer alle knopen in V zitten. Voorbeeld: op het bord.
11
Algoritmiek 2012/12
Eindresultaat
12
Algoritmiek 2012/12
Algoritme van Kruskal
We beginnen met een set F van ‘sub-bomen’, waarbij iedere knoop in de graaf een losse boom vormt, en een set S van alle edges in de graaf. Bij iedere stap in het algoritme halen we de edge (u, v) met de laagste waarde uit S, en als (u, v) twee verschillende sub-bomen in F verbindt, voegen we deze sub-bomen samen tot ´ e´ en sub-boom. Anders gooien we de edge gewoon weg. Het algoritme stopt als F precies ´ e´ en sub-boom bevat. Voorbeeld: op het bord.
13
Algoritmiek 2012/12
Eindresultaat
14
Algoritmiek 2012/12
Greedy
Beide methoden zijn greedy: kies de snelst te bereiken knoop, kies de kortste edge. Beide geven een opspannende boom terug. Het bewijs dat deze minimaal is, is wat bewerkelijk (omdat er meerdere MOB’s kunnen zijn) maar wat eenvoudiger als we aannemen dat alle waarden uniek zijn en er dus maar ´ e´ en MOB is. Stel: A is een MOB. Het toevoegen van een willekeurige edge e1 = (u, v) introduceert ergens een cycle C. Omdat A een MOB is, is e1 op C de edge met de hoogste waarde. Prim zal e1 nooit kiezen, omdat v (of u) vanuit een ander punt op de cycle (via e2 = (w, v)) sneller te bereiken is. Kruskal zal e1 nooit kiezen, omdat er een andere edge op C is die een lagere waarde heeft en dus eerder gekozen wordt. 15
Algoritmiek 2012/12
Overzicht methoden
• Brute Force, Exhaustive Search
• Backtracking, Branch-and-Bound
• Divide and Conquer
• Greedy
• Dynamisch Programmeren 16
Algoritmiek 2012/12
Brute Force
Te gebruiken bij: problemen waarbij deeloplossingen niet bestaan of je geen inzicht geven in een volledige oplossing. Voordeel: Werkt altijd: is altijd toepasbaar, vindt altijd een oplossing als deze bestaat. Implementatie vaak triviaal: volgt de definitie van het probleem. Nadeel: Bijna per definitie exponentieel zonder veel mogelijkheden om de looptijd te bekorten (maar: let op definitie van het zoekprobleem, b.v. 8-queens puzzel: ´ e´ en Q per rij en kolom).
17
Algoritmiek 2012/12
Backtracking
Te gebruiken bij: problemen waarbij je bij deeloplossingen vaak al kunt zien of een pad in de zoekboom naar een niet-toegestane oplossing leidt, zodat je soms snel kunt stoppen. Voordeel: Soms grote winst als er flinke stukken van de zoekboom gesnoeid kunnen worden. Als je een optimale oplossing zoekt (in plaats van ‘een’ oplossing) kun je soms ook snoeien als de maximaal te bereiken score lager is dan wat je al had. Nadeel: Hangt af van mate waarin deeloplossingen inzicht geven in de eindoplossing.
18
Algoritmiek 2012/12
Branch-and-Bound
Te gebruiken bij: Optimalisatieproblemen, waarbij je deeloplossingen kunt genereren en waarbij je snel een heuristiek voor een onder/bovengrens kunt berekenen. Voordeel: Als de onder/bovengrens dicht bij het te bereiken optimum zit, is zeer grote snelheidswinst bereikbaar. De ondergrens kan ook gebruikt worden om slim de eerstvolgende tak in de zoekboom te selecteren. Nadeel: Alleen voor optimalisatieproblemen. Met slechte ondergrens weinig winst te boeken. Kost extra tijd/geheugen om alle nog te onderzoeken deeloplossingen te berekenen en in het geheugen te houden. 19
Algoritmiek 2012/12
Divide-and-Conquer
Te gebruiken bij: Problemen die een hoge mate van parallellisatie mogelijk maken, zoals sorteren van een array, en waarbij oplossingen voor een deelprobleem eenvoudig gecombineerd kunnen worden tot een oplossing voor een groter probleem. Voordeel: Vaak sneller dan iteratieve methoden. Nadeel: Het probleem moet zich er toe lenen. Soms veel overhead in het verdelen en mergen, wat de snelheidswinst in de praktijk teniet doet.
20
Algoritmiek 2012/12
Dynamisch Programmeren
Te gebruiken bij: Problemen waarbij deeloplossingen overlappen, en een zuiver recursief algoritme (zoals bij divide-and-conquer) veel werk dubbel doet. Voordeel: Minder werk doordat je deeloplossingen maar ´ e´ en keer uitrekent. Nadeel: Geheugengebruik: de te vullen tabel, zeker als er meer dan twee dimensies zijn, kan erg groot worden. Hangt af van geschikte combinatie van deeloplossing naar eindoplossing.
21
Algoritmiek 2012/12
Greedy algoritmen
Te gebruiken bij: Problemen waarbij lokale keuzes voldoen om een globaal beste oplossing te vinden (lange halen, snel thuis). Voordeel: Snelle en eenvoudige algoritmen. Nadeel: De techniek werkt lang niet altijd om een optimale oplossing te vinden. Bij sommige problemen vind je dan een suboptimale, of zelfs geen oplossing. Je zult moeten bewijzen dat de aanname (lokale beste keuze zorgt voor globale beste oplossing) correct is.
22
Algoritmiek 2012/12
Nog vragen op dit moment?
Als er nog tijd beschikbaar is, is dit een mooi moment om onduidelijkheden uit de weg te ruimen...
23
Algoritmiek 2012/12
Werkcollege
Volgende week is er geen hoor- of werkcollege in verband met Hemelvaart. De week erna is het laatste werkcollege op donderdag 24 mei (over branch-and-bound en heapsort) Op vrijdag 25 mei bespreken we het oefententamen van augustus 2011. Probeer het eerst zelf te maken! Deadline laatste practicumopgave is 18 mei (online). Je mag de papieren versie t/m maandag 21 mei inleveren. 24
