8. Complexiteit van algoritmen: _________________________________________
Voorbeeld: Een gevaarlijk spel ________________________________ 1 Spelboom voor het wespenspel ________________________________ 2
8.1 8.2 8.3 8.4
Complexiteit ______________________________________4 NP-problemen ____________________________________6 De oplossing _____________________________________7 Een vuistregel ____________________________________8
In dit hoofdstuk wordt het duidelijk dat er problemen zijn waarvoor er geen volledig correct antwoord te berekenen is. Met een voorbeeld wordt duidelijk gemaakt dat het verstandig is om eerst de orde van grootte van je probleem te analyseren en pas daarna het algoritme te bedenken. Je maakt kennis met NP-problemen en NP-volledige problemen en hun oplossingen. Voorbeeld: Een gevaarlijk spel In het volgende voorbeeld gaan we een spel spelen met twee sluipwespen. De sluipwespen worden om de beurt in een bakje met twee drosophila poppen gezet. Er wordt gewacht totdat de wesp in het bakje twee eitjes gelegd heeft. Wanneer de wesp haar 2 eitjes gelegd heeft, is de beurt aan de andere sluip-
wesp. Deze mag ook 2 eitjes leggen. Dit spel gaat door totdat in beide drosophila poppen 5 eitjes gelegd zijn.We nemen aan dat de wespen kunnen waarnemen hoeveel eitjes van haarzelf en hoeveel eitjes van een andere wesp in de pop aanwezig zijn. De wesp die het meeste eitjes in een pop heeft, heeft de grootste kans dat de uiteindelijke wesp die uit de pop ontstaat een kind van
Pagina 8 - 2 haar is en heeft een punt gewonnen. Bij 2 poppen kan een wesp dus met 2-0 winnen of 1-1 gelijk spelen. Stel dat de wespen de namen w1 en w2 krijgen en de drosophila poppen de namen pop1 en pop2. W1 mag met het spel beginnen. Er zou dan een volgend spelverloop kunnen zijn: pop1
pop2
w1
w2
w1
w2
w1 legt 2 eitjes in pop1
2
0
0
0
w2 legt 1 eitje in pop1 en 1 eitje in pop2
2
1
0
1
w1 legt 1 eitje in pop1 en 1 eitje in pop2
3
1
1
1
w2 legt 2 eitjes in pop2
3
1
1
3
w1 legt 1 eitje in pop1 en 1 eitje in pop2
4
1
2
3
Allebei de poppen zitten nu vol, w1 heeft pop1 gewonnen en w2 heeft pop2 gewonnen de eindstand is dus 1-1. De 5 rijen met cijfers geven de toestand aan waar het spel zich op dat moment in bevindt. Hier zijn slechts 5 toestanden te zien,in totaal zijn er echter veel meer. Om een overzicht te krijgen van het aantal toestanden, is het handig om een spelboom te maken. Hieronder zie je een voorbeeld van zo'n spelboom.
00 00 Wesp 1 20 00
10 10 Wesp 2
22 00
20 02
21 01
02 20
00 22
01 21
12 10
10 12
Wesp 1 22 20
32 10
Wesp 1
Wesp 2
32 30
23 21 22 22
32 32 Wesp 1 wint 23 41 Gelijkspel 32 32 Wesp 1 wint
Spelboom voor het wespenspel Door ruimte gebrek is deze spelboom niet helemaal afgemaakt. De toestanden zijn de knopen van de boom en de getallen die erbij staan (00 00, 20 00 enz.) zijn weergaven van de stand (net zoals in de tabel). Als je vanuit een knoop naar links gaat dan leg je in pop1 2 eitjes, als je vanuit een knoop de middelste tak neemt dan leg je in pop2 2 eitjes,als je de rechter tak neemt dan legt de wesp 1 eitje in pop1 en 1 eitje in pop2. Er zijn ook knopen die illegale toestanden afbeelden. Dit zijn toestanden die niet voor mogen komen. In zo’n geval zouden er meer dan 5 eitjes in een pop gelegd worden. (Zoek ze op en geef ze met een kruis aan).
Hoofdstuk 8
11 11
Pagina 8 - 3 Wanneer je nu wilt weten welke zet je bij een bepaalde toestand moet doen, kan je voor elke mogelijke zet door de spelboom naar beneden wandelen en kijken wat de kans op winst is bij die bepaalde zet.Welke zet zou jij b.v. doen wanneer je wesp1 was en de toestand is 22 00? Bij 2 poppen is deze boom nog redelijk te overzien. Het spel kan echter ook met 4 of 5 poppen gespeeld worden. De spelboom zal in die gevallen groter worden. De vraag is echter: Hoe groot worden die bomen? De diepte van de boom is gelijk aan het aantal eieren gedeeld door 2. Als er 2 poppen zijn dan moeten er 10 eieren gelegd worden. Omdat er per beurt 2 eieren gelegd worden, zijn er 10/2 = 5 beurten nodig voordat de poppen vol zijn. De diepte van de spelboom is dus 5. In het algemeen kan je zeggen dat voor n poppen de diepte 5n/2 = 2.5n zal zijn. Het aantal mogelijkheden waarop de wesp haar n eieren kan leggen neemt ook bij het toenemen van het aantal toe. Bij 1 pop kan het maar op 1 manier. Bij 2 poppen kan het op 1 + 2 = 3 manieren. Bij 3 poppen kan het op 1 + 2+ 3 = 6 manieren Bij n poppen kan het op 1 + 2 + 3......+ n manieren. Wanneer je alle punten (alle toestanden) wilt berekenen moet je voor elk niveau berekenen hoeveel toestanden er per niveau zijn. Bij n = 2 zijn er op het eerste niveau 3 toestanden, op het tweede niveau zijn er 9, op het derde niveau zijn er 27, op het vierde niveau zijn er 81 en op het vijfde niveau zijn er 243 toestanden; in totaal zijn er dus 363 toestanden (voor het gemak zijn de onmogelijke toestanden meegerekend, het gaat namelijk om de orde van grootte). In het algemeen geldt:
∑(1+2+…+n)n voor n=1 tot 2.5a Waarbij a het aantal poppen voorstelt. Voor a = 2 geldt dus:
∑(1+2)n voor n=1 tot 5 Dit is 3 + .... + 32 + 33 +34 + 35 = 363 toestanden Als we voor een aantal poppen het aantal toestanden berekenen dan komen we tot de volgende tabel: aantal poppen
aantal toestanden
tijdsduur
1
3
0.03 sec
2
363
3.63 sec
3
335922
56 minuten
4
1.11 x 10 10
3.5 jaar
5
2 x 1015
661215 jaar
Bij tijdsduur hebben we aangenomen dat de computer ongeveer 0.01 seconde nodig heeft om een toestand te berekenen.
Hoofdstuk 8
Pagina 8 - 4
8.1 Complexiteit Je ziet dat de tijd die nodig is schrikbarend toeneemt met het aantal poppen. Bij 5 poppen is de oplossing voor het probleem al onuitvoerbaar (ook al zou je een duizend keer zo snelle computer hebben). We spreken in zo’n geval van een onhandelbaar probleem. Voor dergelijke problemen is geen redelijk algoritme beschikbaar. Wat verstaan we dan onder een redelijk algoritme? Om te kunnen beoordelen of er voor een probleem een redelijk algoritme mogelijk is moeten we kijken naar de samenhang tussen de omvang van de invoer van een probleem en de hoeveelheid tijd en geheugenruimte die nodig is om een oplossing van het probleem te berekenen. Die twee factoren bepalen de complexiteit van een algoritme. Complexe algoritmen vragen veel van een computer in termen van beschikbaar geheugen en vereiste rekentijd door de centrale processor (CPU). Complexiteit kunnen we beschrijven door te kijken naar het aantal handelingen en/of vergelijkingen dat nodig is om van input naar gewenste output te komen. Daarbij gaat het niet om het precieze aantal handelingen maar om de orde van grootte van het aantal handelingen. Die orde van grootte geven we aan met de hoofdletter O. We spreken daaarom ook wel van de grote-O-notatie. Wanneer we van een probleem zeggen dat het in de klasse O(n) ligt dan betekent dat dat er een lineair verband is tussen de omvang van het probleem, i.e., het aantal te verrichten handelingen of vergelijkingen dat nodig is om de input om te zetten in een oplossing van het probleem, en de hoeveelheid tijd die daar voor nodig is. We onderscheiden verschillende klassen van problemen al naar gelang de relatie tussen omvang en tijd: O(log n)
: logaritmisch
O(n)
: lineair
O(n2)
: kwadratisch (i.h.a., polynomiaal)
O(2n )
: exponentieel
Problemen die tot de eerste drie klassen behoren noemen we handelbaar. Voor dergelijke problemen zijn redelijke algoritmen mogelijk. Zodra de relatie tussen omvang van het probleem en de benodigde rekentijd exponentieel van karakter wordt noemen we het probleem onhandelbaar, en is er geen redelijk algoritme mogelijk. In het algemeen geldt dus dat het asymptotisch gedrag (hoe snel verandert de rekentijd met Hoofdstuk 8
Pagina 8 - 5
de grootte van het probleem) bepaalt of een probleem uitvoerbaar is of niet. Een voorbeeld van een handelbaar probleem is bijvoorbeeld het zogenaamd lineair zoeken in een lijst (met namen bijvoorbeeld). Van de lijst is bekend dat er N namen in staan. Het is onbekend of de lijst is geordend, d.w.z. we weten niet van te voren of de namen alfabetisch zijn gerangschikt. We zoeken naar de naam X en we weten zeker dat de naam in de lijst voorkomt. De vraag is nu: hoe complex is dit probleem ? Om die vraag te kunnen beantwoorden moeten we ons een idee vormen over hoeveel namen uit de lijst we moeten vergelijken met de naam die we zoeken. We weten dat als de gezochte naam X als eerste op de lijst voorkomt er maar 1 vergelijking nodig is geweest. Staat X op plaats 2 dan zijn er 2 vergelijkingen nodig, en staat X op plaats N dan zijn er N vergelijkingen nodig. Dat wil zeggen dat voor dit probleem in het algemene geval voor het aantal te verrichten handelingen geldt: (1+2+3+…+N)/N = 0.5N (N+1)/N = 0.5 (N+1) = O(N)
De orde van grootte van het lineaire zoek probleem is dus recht evenredig met de omvang van de lijst waarin we moeten zoeken. We mogen dus verwachten dat er een redelijk algoritme bestaat om dit zoek-probleem op te lossen. Het is zelfs zo dat er een beter algoritme te formuleren is als we iets aan de eigenschappen van de lijst kunnen sleutelen. Een beter algoritme wil in dit geval zeggen dat het een gunstiger relatie tussen probleem-omvang en benodige rekentijd bezit. Om dit te kunnen bereiken is het nodig dat de lijst is gesorteerd, d.w.z. alfabetisch is geordend (om zover te komen met die lijst is op zich zelf natuurlijk ook weer een probleem, een zg. sorteer probleem, waar in de literatuur zeer veel oplossingen voor worden aangereikt). We hebben dus weer een lijst L met N namen waarin we op zoek zijn naar naam X. L is alfabetisch geordend, en X komt voor in L. Hoe complex is dit probleem, m.a.w. hoeveel vergelijkingen zijn er globaal nodig om X te vinden ? Herhaal M := middelste element uit L Hoofdstuk 8
Pagina 8 - 6
Als X KLEINER DAN M Dan L := bovenste helft van L Anders L := onderste helft van L Eindals Totdat X IS_GELIJK M Eindherhaal Stel dat N = 2k - 1, en k = 3. N is dan gelijk aan 7 Als X gelijk is aan het middelste element (nummer 4) dan is er 1 vergelijking nodig geweest. Indien dat niet het geval is wordt L gelijk aan of de bovenste of de onderste helft van L (met nog maar drie namen). Indien X gelijk is aan de middelste naam (de tweede) dan zijn er 2 vergelijkingen nodig geweest. Indien niet, dan breken we L weer op in of de bovenste of de onderste helft. Hier zit dan nog maar 1 naam in die per definitie (want we hebben afgesproken dat X in de lijst zit) gelijk moet zijn aan de gezochte naam. Dat wil zeggen dat voor dit probleem in het algemene geval voor het aantal te verrichten handelingen geldt: (1x1 + 2x2 + 4x3 + … + (2k-1 x k))/N = ((k-1)x 2k+1)/N = (N+1) x ((2log(N+1)-1)/N) + 1/N = log (N+1) - 1 =
2
O(logN)
De logaritme van N is duidelijker kleiner dan N zelf. We hebben om dit probleem op te lossen bij een gelijke omvang van de lijsten dus minder rekentijd nodig dan met het lineaire zoek probleem.
8.2 NP-problemen In het algemeen geldt dus dat de tijd die nodig is om een probleem op te lossen een functie is van de omvang van het probleem. Bij een probleem dat in polynomiale tijd uitvoerbaar is, een P-probleem, hoort een functie waarbij n (aantal) het grondtal is, b.v. f(n) = n of f(n) = n + n 2. Bij een probleem dat niet in een polynomiale tijd te berekenen is, hoort een
Hoofdstuk 8
Pagina 8 - 7
functie waarbij n in de macht staat, b.v. f(n) = en of f(n) = n + 42n . Een bijzondere klasse van problemen wordt gevormd door gevallen waarvan de status onbekend is. Er bestaan wel algoritmen voor de afzonderlijke gevallen uit deze categorie, maar deze oplossingen zijn geen van alle redelijk. Maar van deze gevallen is daarentegen ook nog niet bewezen dat ze tot de categorie van onhandelbare problemen behoren. Ze zijn in polynomiale tijd te berekenen als we zouden kunnen raden (in plaats van van te voren exact bepalen = determineren) hoe de berekening moet gaan. We noemen een probleem wat tot deze categorie behoort een NP-probleem (NP = Nondeterministisch Polynomiaal). Voorbeelden van NP problemen zijn: Het berekenen van de beste zet bij schaken een lesrooster maken; het bepalen van de kortste weg, als je een gegeven aantal plaatsen moet bezoeken.
8.3 De oplossing Toch willen we voor de NP problemen een oplossing hebben. Dit kan, maar dan moeten we met iets minder tevreden zijn. In veel gevallen kan er namelijk een vuistregel, of een andere truc bedacht worden die [vaak] een goed antwoord geeft. We spreken in zo’n geval van een heuristische (heuriskein – grieks voor ‘ontdekken’) in plaats van een exacte oplossingsmethode. We noemen een methode heuristisch als het op basis van ervaring of logisch redeneren redelijk aannemelijk te maken is dat die methode een goede oplossing voor een probleem oplevert, echter zonder dat we kunnen garanderen dat die oplossing optimaal is. Er zijn talrijke voorbeelden van dergelijke op ervaring berustende vuistregels. Voor de 3 problemen die we boven noemden zouden we met de volgende compromissen tevreden kunen zijn: Bij schaken wordt maar een aantal zetten vooruit bedacht en worden standaard regels gebruikt. Bij lesroosters wordt een rooster gemaakt waar iedereen mee kan leven, het bevat dan nog tussen-uren en lange dagen.
Hoofdstuk 8
Pagina 8 - 8
Bij het vinden van de kortste weg worden de eisen iets verzwakt en wordt gezocht naar een acceptabel korte weg.
8.4 Een vuistregel Even terug naar het probleem waar we dit hoofstuk mee begonnen. Bij onze voorstelling van de eileg competitie tussen twee wespen als spel, zou de beste zet berekend kunnen worden door het uitrekenen van de komplete spelboom. Bij 5 poppen zou het berekenen van de beste zet dan 661215 jaar in beslag nemen. We kunnen echter ook een vuistregel verzinnen die in de meeste gevallen wel voor winst zorgt. Een voorbeeld van een vuistregel is: 1. 2. 3. 4. 5. 6. 7.
Zoek naar poppen met 4 eitjes waarvan er 2 van jezelf zijn en leg er 1 eitje bij. Zoek naar poppen met 3 eitjes waarvan er 1 van jezelf is en leg er 2 eitjes bij. Zoek naar poppen met 1 eitje en leg er 1 eitje bij. Zoek naar een lege pop en leg alle overige eieren. Leg 1 eitje bij poppen met 2 eigen eieren. Leg 1 eitje bij poppen met 2 andere eieren. Leg willekeurig ergens een eitje.
Voor alle duidelijkheid: Dit is één vuistregel die uit 7 regels bestaat welke in volgorde van belangrijkheid gerangschikt zijn. Misschien is er een betere vuistregel te vinden, maar deze vuistregel zal het in de praktijk aardig doen. Het grote voordeel van deze vuistregel is de tijdswinst. Bij 5 poppen zijn er 13 speelbeurten. 13 keer moeten er dus (maximaal) 7 regels over 5 poppen toegepast worden. Er moeten dus 13x7x5 = 455 handelingen verricht worden. Stel dat ook dit keer elke handeling 0.01 seconde duurt, dan zou het spel in 4.55 seconden gespeeld zijn. Hoofdstuk 8
Pagina 8 - 9
Een ander groot voordeel is de hoeveelheid geheugen die de computer aan moet spreken om het probleem op te lossen. Bij de vuistregel levert dit geen enkel probleem op, terwijl bij het berekenen van een hele spelboom er waarschijnlijk een geheugen probleem ontstaat.
Hoofdstuk 8
Pagina 8 - 10
Hoofdstuk 8
