9. Strategieën en oplossingsmethoden ___________________________________________
In dit hoofdstuk wordt nog even terug gekeken naar alle voorgaande hoofdstukken. We herhalen globaal de structuren en geven enkele richtlijnen voor het ontwerpen van algoritmen (geen regels, want die bestaan niet). Ook worden er nog enkele belangrijke strategieën behandeld.
In de vorige hoofdstukken zijn een aantal oplossingsmethoden behandeld. Het is echter nog onduidelijk wanneer je welke methode moet gebruiken. Wanneer moet ik nu recursie gebruiken en wanneer niet, wanneer moet ik naar een vuistregel zoeken, wanneer moet ik met lussen werken? Dit zijn vragen waar je nu nog geen duidelijk antwoord op gekregen hebt. Het is ook zeer moeilijk om hier een antwoord op te geven, want voor elke regel die je verzint zijn tientallen voorbeelden te noemen die het tegendeel bewijzen. Toch zullen we een poging wagen om licht in de duisternis brengen.
9.1 Enkele tips Om te beginnen moet je, voordat je een algoritme gaat maken, je verdiept hebben in het probleem. Enkele tips die je hierbij kunt gebruiken zijn:
☞ ☞ ☞
Formuleer het probleem duidelijk en begrijp het volkomen. Begrijpen waarom een probleem een probleem is vormt het begin van het vinden van een oplossing. Maak verborgen regels en gegevens zichtbaar. Soms zijn er bij een bepaald probleem een aantal gegevens die als bekend beschouwd worden. Probeer inzicht in dit soort gegevens te krijgen. Verkrijg inzicht in het probleem.Vaak kun je door het probleem te tekenen of op een andere manier te visualiseren een goed inzicht krijgen in het probleem. Een goed voorbeeld hiervan is de spelboom van het wespenspel (hoofdstuk 8). Bij dit spel was een Toestand-actie-diagram getekend. Dit is een diagram waarin bij elke toestand wordt nagegaan welke acties er ondernomen kunnen worden. Hier is bijvoorbeeld 00 00 de begintoestand. De acties die wesp1 kan ondernemen zijn: 2 eitjes in pop1, 2 eitjes in pop2 of 1 eitje in pop1 en 1 eitje in pop2. Deze drie acties zorgen ervoor dat er drie nieuwe toestanden ontstaan. Vanuit deze toestanden kan je weer 3 acties ondernemen enz.... Ook kan je het probleem gewoon enkele keren na-spelen om inzicht te krijgen in alle mogelijkheden en de problemen.
Pagina 9 - 2
☞ ☞ ☞
Verwijder overbodig detail. Verdeel en heers: Probeer het probleem in subproblemen te verdelen en los deze subproblemen zoveel mogelijk op. Combineer de subproblemen en verkrijg zo je antwoord. Van achter naar voren werken (van de oplossing af terugredeneren). Vaak weet je van een eenvoudig voorbeeld wat het antwoord moet zijn en kan je voor dit voorbeeld terugredeneren wat de werkwijze moet zijn. Dit verhoogt soms het inzicht en kan leiden tot een snelle oplossing. Nadat je hebt nagedacht over de structuur van je probleem en de structuur van je gegevens, kan je na gaan denken over de structuur van je algoritme. We zullen in de komende paragrafen enkele richtlijnen geven die je kunnen helpen bij het maken van algoritmen. Pas wel goed op, de richtlijnen zijn globaal en er zijn dan ook zeer veel uitzonderingen.
9.2 Zoek en Doorloop 9.2.1 De enkele lus Wanneer je je informatie hebt opgeslagen in vectoren en je wilt een bewerking hiermee doen waarbij alle elementen binnen de vector 1 maal gebruikt worden, dan is het raadzaam om dit binnen een lus te doen met een teller. Voorbeeld: Van een rij ('Vet' uit paragraaf 3.6) willen we weten welk getal het meeste voorkomt en hoe vaak het voorkomt. ‘Vet’ WORDT 25,40,30,25,60,55,30,25,30,28,34,45 PROGRAM ‘VOORKOM PARAM OUTPUT’ {geeft van de rij Vet welk getal N := LENGTE PARAM { het aantal teller := 1 { een teller aantal := 0 { het aantal
Herhaal
het meest voorkomt en hoe vaak} elementen } } maal van voorkomen}
tal := SOM PARAM[teller] IS PARAM
Als Dan
aantal KLEINER DAN tal aantal := tal nummer := teller
{ aantal wordt nieuwe frekwentie} { en in nummer komt de index te staan}
teller := teller + 1
{ ga naar het volgend element uit Vet }
Eindals Totdat
teller IS N
Eindherhaal
OUTPUT := nummer, aantal
{ controleer of alle elementen geweest zijn }
Pagina 9 - 3
Ook bij problemen waarbij een bewerking een aantal keer herhaald moet worden is het handig om een enkele lus te gebruiken. Dit komt voor bij o.a. discrete tijd modellen en het berekenen en tekenen van functies. Eigenlijk is het bovenstaande voorbeeld niet helemaal eerlijk. In de enkele lus zit nog een lus verborgen. Om dat in te zien moet je eens precies nagaan wat er in de zevende regel gebeurt. Daarvoor zijn twee dingen nodig. In de eerste plaats moet je weten wat de module SOM doet. Dat kun je naslaan in hoofdstuk 11. In de tweede plaats moet je weten wat het preciese resultaat is van PARAM[teller] IS PARAM. Zie je de verborgen lus nu ?
9.2.2 De dubbele lus Een dubbele lus wordt gebruikt bij gegevens die opgeslagen zijn in een vector, waarbij de gegevens binnen de vector meerdere keren vergeleken moeten worden. Ook bij matrices worden vaak 2 lussen gebruikt. In buitenste lus wordt dan het aantal rijen bij gehouden terwijl in de binnenste lus de kolommen worden bijgehouden. Voorbeeld: Het is misschien een beetje saai, maar om het verschil duidelijk te maken met de enkele vector, zullen we in dit voorbeeld een matrix maken waarbij elke rij verschillende plaatsen in het waddengebied zijn. De kolommen zijn de verschillende zeehonden. z.h.1
z.h. 2
z.h. 3
z.h. 4
Plaats1
25
40
30
25
Plaats2
60
55
30
25
Plaats3
30
28
34
45
Als we nu willen weten hoe vaak een bepaald gewicht voorkomt, dan moet het programma er als volgt uitzien. ‘Vet’ WORDT 3 4 ARRAY 25,40,30,25,60,55,30,25,30,28,34,45 PROGRAM ‘VOORKOMMATRIX PARAM OUTPUT’ {geeft van de matrix Vet hoe vaak getal PARAM voorkomt} N := LENGTE PARAM R := N1] { het aantal rijen } K := N[2] { het aantal kolommen} RijTel := 1 { een teller voor de rijen } KolTel:= 1 { een teller voor de kolommen } aantal := 0 { het aantal maal van voorkomen} LEES ‘gew’ { Geef het bepaalde gewicht }
Herhaal Herhaal Als
PARAM[RijTel;KolTel] IS_GELIJK gew { verhoog aantal als gewicht in Vet voorkomt.... }
Pagina 9 - 4
Dan
aantal := aantal + 1
Eindals
KolTel := KolTel + 1 { ga naar de volgende kolom in Vet }
Totdat
KolTel IS K
{ controleer of alle kolommen geweest zijn }
RijTel := RijTel + 1
{ ga naar volgende rij }
RijTel IS R
{ controleer of alle rijen geweest zijn }
Eindherhaal Totdat
Eindherhaal
OUTPUT := aantal
9.3 Verdeel en heers Vaak kunnen we een probleem oplossen door het op te delen in kleinere problemen van dezelfde soort, die op hun beurt ook weer opgedeeld kunnen worden. Later kan dan nadat alle deelproblemen opgelost zijn het uiteindelijke antwoord gegeven worden. Voor dit soort problemen wordt vaak recursie gebruikt. Toch moet je oppassen met het gebruik van recursie. Vaak zijn oplossingen met een lusstructuur beter te overzien en beter uit te voeren. Voorbeeld: We kunnen in de vector met VET op een recursieve manier het minimum vinden. ‘Vet’ WORDT 25,40,30,25,60,55,30,25,30,28,34,45 PROGRAM ‘MINIMUM PARAM OUTPUT’ { geeft het minimum van VECTOR } vector:=PARAM lengte:=LENGTE vector
Als Dan
lengte GROTER DAN1 lengte_1 := RONDAF lengte GEDEELD 2 lengte_2 := lengte MIN lengte_1 V1 := vector[RIJ lengte_1] V2 := vector[lengte_1 +RIJ lengte_2] MIN1 := MINIMUM V1,lengte_1 MIN2 := MINIMUM V2,lengte_2
Als Dan
MIN1 KLEINER DAN MIN2 OUTPUT := MIN1
Anders
OUTPUT := MIN2
Eindals Anders
OUTPUT := VECTOR
Eindals
Hier wordt het minimum van een vector opgedeeld in het vinden van het minimum van de eerste helft van de vector en het vinden van het minimum van de tweede helft. Het minimum is dan het kleinste getal van deze twee minima.
Pagina 9 - 5 Dit kan ook met een lus opgelost worden: PROGRAM ‘MINIMUM PARAM OUTPUT’ { Geeft het minimum van VECTOR } vector:=PARAM lengte:=LENGTE vector M := vector[1] Teller := 1
Herhaal Als Dan
M KLEINER DAN vector[Teller] M := vector[Teller]
Eindals
Teller := Teller + 1
Totdat
Teller IS lengte PLUS 1
Eindherhaal OUTPUT := M
Merk 2 dingen op. 1. Een uitzondering: We hebben voor een vectorbewerking toch een recursief algoritme gebruikt. 2. In dit geval de lus-methode toch wenselijker en overzichtelijker is, hoewel je het probleem kan opdelen in twee deelproblemen. Conclusie: Richtlijnen bestaan wel, regels echter niet.
9.4 Gulzige en Dynamische algoritmen voorbeeld: Olifanten in Afrika Probleemstelling: In Afrika leeft de afrikaanse olifant (Loxodonta africana a f r i c a n a ). In het regenseizoen verblijft de olifant op hoger gelegen gebieden. In deze gebieden staan de favoriete voedsel bronnen van de olifanten: bomen. Bomen bevatten veel koolhydraten en zijn vezelrijk. In het droge seizoen wordt het in deze hoger gelegen gebieden te droog. De olifant kan dan geen water meer drinken en de bomen leveren ook steeds minder voedsel. Dit is voor de olifanten het teken om naar lager gelegen gebieden te trekken. Nu beginnen de problemen pas echt. Tussen de hoge en lage gebieden leeft een groot aantal boeren. Deze stellen het niet op prijs wanneer een kudde olifanten hun achtertuin om komt ploegen. Om dit probleem te voorkomen wordt al een aantal jaar geprobeerd om het pad dat de olifanten nemen te begrijpen, zodat deze situatie veranderd kan worden. Enkele hypothesen voor het pad van de Olifant zijn: 1-Hij neemt de kortste weg naar de lager gelegen gebieden. 2-Hij neemt elke keer de weg naar de dichtstbijzijnde drinkplaats en gaat zo richting B. 3-Hij neemt de kortste weg, maar hij neemt in zijn route een aantal drinkplaatsen op.
Pagina 9 - 6 Gegeven is het volgende kaartje: Hypothese 1 is niet zo moeilijk te onderzoeken. Om te kijken of dit zo is trek je een lijn van A naar B, en je kijkt of de olifanten niet te veel van deze lijn afwijken. Hypothese 2 (hij neemt elke keer de weg naar de dichtstbijzijnde drinkplaats en gaat zo richting B) kunnen we oplossen met een zogenaamd gulzig algoritme (Greedy Algorithm). Dit algoritme zoekt in elke toestand wat de beste volgende stap is (zonder daarbij verder te kijken dan die volgende stap). In dit geval zou dat het volgende algoritme opleveren:
B
30
24
20 26
30
28
20
24
28
50
28
20
30 36 26 22
32 34 26
A = Hoger gelegen plaats B = Lager gelegen plaats = Waterplaats 28 = Begaanbaar pad met lengte 28
30 32
24
A
Herhaal Als dichtstbijzijnde nog niet bezochte waterplaats dichterbij dan B Dan Ga naar dichtstbijzijnde nog niet bezochte waterplaats Anders Ga naar B Eindals Totdat Olifant in B Eindherhaal. Het pad dat de olifant dan aflegt is in het volgende kaartje afgebeeld: De afstand die de olifant dan afgelegd heeft is: 24 + 26 + 22 +20 + 24 + 26 + 30 = 172 km. Merk op dat de afgelopen afstand nog meevalt. Door de kortste afstand te nemen naar de volgende waterplaats zou het kunnen zijn dat de olifanten een veel grotere omweg moeten nemen. Hypothese 3 (hij neemt de kortste weg, maar hij neemt in zijn route een aantal drinkplaatsen op) kunnen we oplossen met een dynamisch algoritme. Het probleem wordt daartoe eerst verdeeld in stadia. Per stadium gaat het algoritme gaat alle mogelijke oplossingen na, en onthoudt hoe goed de oplossing is. Nadat alle oplossingen per stadium gegenereerd zijn is de beste totale oplossing bekend.
B
30
24
20 26
30
28
20
24
28
50
28
20
30 36 26 22
32 34 26
30 32
24
De oplossing kan dus met een verdeel A en heers methode bereikt worden. Immers de kortste afstand van A naar B is het minimum van (32 + de kortste afstand van knoop1 naar B) en (24 + de kortste afstand van knoop2 naar B) en voor knoop1 en knoop2 geldt het zelfde enz... Het verschil met de ‘echte’ verdeel en heers benadering zit hem in het feit
Pagina 9 - 7 dat we alle berekeningen van ‘tussen’ afstanden op kunnen slaan in een tabel, met het doel om ze op te kunenn zoeken (ipv opnieuw uit te rekenen) als we ze later in het programma weer een keer nodig hebben. Merk op: het probleem van knoop1 en knoop2 zijn deelproblemen van het probleem voor A. PROGRAM ‘KORTSTEPAD OUTPUT PARAM’ {Berekend de kortste afstand van knoop ALBEZOCHTEKNOPEN:=PARAM[1] KNOOP:=PARAM[2] {Om te voorkomen dat het blijft gaan} ALBEZOCHTEKNOPEN := ALBEZOCHTEKNOPEN, LENGTE := 1000 { Neem een extreem
KNOOP naar het eindpunt B} algoritme in cirkeltjes rond KNOOP grote lengte }
Herhaal voor elk pad dat leidt naar buurknoop die niet in ALBEZOCHTEKNOPEN zit Als pad leidt naar B Dan L := lengte van het pad naar B {Basis geval} Anders {Recursieve aanroep met buurknoop} L := lengte pad + KORTSTEPAD buurknoop PLAK ALBEZOCHTEKNOPEN Eindals Als {Als de lengte korter dan de tot nu toe gevonden} L KLEINER DAN LENGTE Dan {Maak lengte de kortste lengte} LENGTE := L Eindals Eindherhaal OUTPUT := LENGTE
{Geef kortste lengte terug}
Omdat het algoritme van te voren niet weet hoeveel buurknopen een knoop heeft moet in het recursieve algoritme een lus aangebracht worden. Deze stopt als alle buurknopen bestudeerd zijn. Het pad dat de olifanten dan lopen is in het plaatje hiernaast te zien: 32+34+30+30+20=14
Pagina 9 - 8
