6 Oplossingen zoeken via Back track -algoritmen

B2: Algoritmen, Datastructuren en Objectprogrammeren

Oplossingen zoeken via Back track -algoritmen

6 Oplossingen zoeken via Back track -algoritmen Veel problemen zijn nìet analytisch op te lossen. We kunnen zo’n probleem vaak echter met een computer in de vorm van brute force -rekenen oplossen. Daarbij moeten we van alle voorstelbare oplossingen nagaan of ze inderdaad werkelijke oplossingen zijn. Een te volgen brute force -aanpak kan dan zijn: ZOLANG NIET alle denkbare mogelijkheden geprobeerd DOE : pak een volgende mogelijkheid en controleer of die een oplossing is

Afhankelijk van het specifieke probleem moet deze aanpak bijgeschaafd en verder uitgewerkt worden. Vaak zul je vóór het controleren van een volgende mogelijkheid eerst wat voorbereidingen moeten treffen en die achteraf weer terugdraaien [vóórdat je de voorbereidingen voor weer een volgende mogelijkheid gaat treffen]. Vaak kan zo’n trial and error-aanpak gemakkelijk op een recursieve formulier geformuleerd worden. Een relatief eenvoudige aanpak daarbij is die met een ‘terugkrabbel’ (back track) -algoritme. Als algemene aanpak voor een back track algoritme zou het volgende sjabloon kunnen gelden: VOOR alle mogelijke pogingen vanuit een ‘punt’ in de richting van het einddoel: doe (systematisch) zo’n poging ; ALS die poging kans op succes heeft DAN voer die interessant lijkende poging dan uit ALS einddoel nu bereikt DAN Hebbes! { en toon resultaat en … ? } ELSE zoek op dezelfde wijze verder in de richting van het einddoel ALS dit doorzoeken niet tot het behalen van het einddoel leidt DAN maak effecten van dit pogen ongedaan {back tracking…} { en ga door met de volgende mogelijke pogingen }

De precieze aanpak hangt af weer van het onderhavige probleem (van wat je dus wilt bereiken) 1. We geven in dit hoofdstuk enige voorbeelden van back track algoritmen. De eerste voorbeelden zijn qua aantal af te zoeken mogelijkheden vrij beperkt. Verderop komt ook een voorbeeld ter sprake waarvan de op mogelijke oplossingen af te zoeken ruimte dusdanig groot is, dat we beperkingen [kwalitatief en/of kwantitatief] willen/moeten/kunnen opleggen aan de op te speuren oplossingen als we de zoektijd ‘acceptabel’ willen houden. We gaan daarmee de richting uit van de AI [Artificiële Intelligentie], waar verfijnde zoekstrategieën vaak nodig zijn om problemen mee aan te pakken.

6.1

Back track voorbeeld:

een schaakbord vol paardensprongen

Beschouw het volgende klassieke schaakprobleem: ‘Is het mogelijk met het paard alle velden van het schaakbord te bezoeken, zonder twee keer op hetzelfde veld terecht te komen?’ In de hiernaast weergegeven figuur is aangeduid hoe een paard (aangegeven met ‘P’) sprongen op een schaakbord kan zetten. Dat blijken (tenzij de randen van het schaakbord dat onmogelijk maken; het paard mag immers niet van het bord ‘afspringen’) 8 mogelijkheden te zijn. Het hart van de benodigde back track algoritme is als volgt:

-2

+2

+1

+2

2

4

1

P

0 +1

0

3

-2 -1

-1

5

8 6

7

PROCEDURE ProbeerVolgendeZet ( sprongnr ., ...) BEGIN Figuur 1 De 8 mogelijke relatieve REPEAT paardsprongen op een schaakbord kies de volgende uit de lijst van mogelijke sprongen ; IF (dat veld ‘op het bord’) AND (nog niet eerder ‘besprongen’) THEN BEGIN markeer die sprong (d.w.z. bezet dat veld) ; { d.w.z. ook het laatste, overgebleven veld nu ‘besprongen’ } IF het gehele bord nu ‘vol’ THEN geslaagd in borddekkende doelstelling ELSE 1

Soms is die aanpak ‘markeer een stap’/ ‘ga (recursief) verder’/ ‘maak eerdere stap ongedaan’ te vervangen door alléén een stap ‘ga (recursief) verder’, waarbij een volgende stap ingebouwd zit in een veranderde waarde van een Value-parameter. 61



BEGIN ProbeerVolgendeZet ( sprongnr + 1 ...,...) ; IF NOT ( geslaagd in die sprong ) THEN maak bezette veld weer vrij { <= back tracking...} END ; END ; UNTIL ( geslaagd in borddekkende doelstelling ) OR ( geen sprongen meer mogelijk ) END

We geven hier een mogelijke Pascal-uitwerking van deze algoritme (een alternatieve uitwerking, waarbij álle mogelijke oplossingen gezocht en getoond worden): Program Paardensprongen;

{ springt over alle velden van een schaakbord }

CONST

Bordgrootte = 5; AantalSprongen = Bordgrootte*Bordgrootte; { = 25 } MogelijkeSprongen = 8; { geldt voor een paard }

TYPE

SprongIndex SprongRichting

= 0..AantalSprongen ; = 1..MogelijkeSprongen ;

SPEELBORD

= ARRAY [ 1..Bordgrootte, 1..Bordgrootte ] OF INTEGER ;

SPRONG

= RECORD dx,dy : INTEGER END;

Sprongtabel = ARRAY [ 1..MogelijkeSprongen ] OF SPRONG; CONST

Verschil : Sprongtabel = ( (dx: 2;dy: 1),(dx: 1;dy: 2), (dx:-1;dy: 2),(dx:-2;dy: 1), (dx:-2;dy:-1),(dx:-1;dy:-2), (dx: 1;dy:-2),(dx: 2;dy:-1) );

PROCEDURE MaakLeegBord ( VAR Bord : SPEELBORD ); VAR Rij,Kolom : INTEGER ; BEGIN FOR Rij := 1 TO Bordgrootte DO FOR Kolom := 1 TO Bordgrootte DO Bord [ Rij, Kolom ] := 0 END ; PROCEDURE ToonBord ( Bord : SPEELBORD ); VAR Rij,Kolom : INTEGER; BEGIN GoToXY ( 1, 4 ) ; FOR Rij := 1 TO Bordgrootte DO BEGIN FOR Kolom := 1 TO Bordgrootte DO write ( Bord [ Rij, Kolom ]:4 ); writeln; writeln END ;

END ; PROCEDURE

ZoekVolgendeSprongMogelijkheid ( Bord : SPEELBORD ; richting : SprongRichting; Xpos,Ypos : INTEGER; VAR nieuweX, nieuweY : INTEGER; VAR IsMogelijk: BOOLEAN );

FUNCTION OpBord( Xpos, Ypos : INTEGER ): BOOLEAN; BEGIN OpBord := ( Xpos>0 ) AND ( Xpos <= Bordgrootte ) AND ( Ypos>0 ) AND ( Ypos <= Bordgrootte ) END ; FUNCTION VeldLeeg( Xpos, Ypos : INTEGER ): BOOLEAN; BEGIN VeldLeeg := ( Bord [ Xpos, Ypos ] = 0 ); END ; BEGIN nieuweX := XPos + Verschil [ richting ].dx; nieuweY := Ypos + Verschil [ richting ].dy; IsMogelijk := (OpBord(NieuweX, NieuweY) AND VeldLeeg(NieuweX, NieuweY)) END ; 62



PROCEDURE

ProbeerSprong ( VAR Bord : SPEELBORD ; Sprongnr : SprongIndex ; Xpos, Ypos : INTEGER ) ; VAR Richting : SprongRichting ; NieuweX, NieuweY : INTEGER ; SprongIsMogelijk : BOOLEAN ; BEGIN Bord [ Xpos, Ypos ] := Sprongnr ; { bij binnenkomst: bezet dit veld } IF sprongnr = AantalSprongen THEN ToonBord ( Bord ) { Hebbes ! } ELSE BEGIN FOR Richting := 1 TO MogelijkeSprongen DO BEGIN ZoekVolgendeSprongMogelijkheid ( Bord, Richting, Xpos, Ypos, NieuweX, NieuweY, SprongIsMogelijk ); IF SprongIsMogelijk THEN ProbeerSprong ( Bord, Sprongnr + 1, NieuweX, NieuweY ) ; END; END ; Bord [ Xpos, Ypos ] := 0;

{ bij terugkeer : geef veld weer vrij } { hoeft niet i.g.v. 'Value'-parameter }

END ; PROCEDURE GaAlleSprongMogelijkhedenNa ( Bord : SPEELBORD ) ; VAR Rij, Kolom : INTEGER ; BEGIN { Probeer 1e sprong vanuit alle mogelijke uitgangsposities op bord: } FOR Rij := 1 TO Bordgrootte DO FOR Kolom := 1 TO Bordgrootte DO ProbeerSprong ( Bord, 1, Rij, Kolom ) END ; VAR

SchaakBord : SPEELBORD ;

{ globale variabele

}

BEGIN ClrScr ; writeln ( 'Het paard probeert al back-trackend alle velden van een' ); writeln ( 'schaakbord van ', Bordgrootte, ' bij ', Bordgrootte, ' aan te doen...'); MaakLeegBord ( SchaakBord ) ; GaAlleSprongMogelijkhedenNa ( SchaakBord ) END.

Bij uitvoering van dit programma blijkt duidelijk dat het wel dan niet vinden van een (eind)oplossing afhangt van de gekozen dimensies voor het schaakbord. N.B. Indien we hiervoor in de procedure ‘ProbeerSprong’ de parameter ‘Bord’ nìet als VAR -parameter hadden gedefinieerd, maar als Value-parameter, dan zouden geprobeerde sprongen bij terugkeer uit recursie automatisch verloren gaan (ofwel: worden teruggedraaid). Het verschijnsel, dat back tracking kan worden vervangen door een simpele recursie met Value-parameters komt (zoals al eerder vermeld in een voetnoot) vaker voor!

6.2

De muis in de doolhof op zoek naar kaas

(met een minimum-waarde)

6.2.1 Probleemdefinitie • Er is een doolhof met daarin een kaas op een willekeurige plek. • Er is een muis op een willekeurige plek in de doolhof. • We willen de kortste afstand van de muis tot aan de kaas weten. We hebben hier te maken met een ‘uitbreiding’ van het Figuur 1 De muis in de doolhof normale back track-en. Het gaat hierbij niet alleen over het vinden van een (of alle) oplossing, maar om het vinden van die ene oplossing, die de kortste loopweg voor de muis oplevert. 63



6.2.2 Mogelijke probleemoplossingen a. De muis gaat zijn/haar neus achterna. Dit werkt niet, want de computermuis kan niet ruiken en de computerrepresentatie van de kaas verspreidt geen geur. b. Laten we de doolhof voorstellen als een plein met tegels. Op één van de tegels ligt een kaas. Op één van de tegels zit een muis. Op een deel van de tegels staan muren. Laat de muis nu systematisch alle tegels afzoeken naar de kaas. Daarvoor zijn twee mogelijke aanpakken: b.1.) De ‘Veegmethode’ De plein-veeg-methode, waarbij we rij voor rij alle tegels van het plein afzoeken (‘vegen’) is ongeschikt. Op een open plein zouden we weliswaar de kaas vinden, maar we komen in de problemen door de aard van een doolhof. Ook is de kortste afstand niet eenvoudig te bepalen door het aantal tegels van de oorspronkelijke plaats van de muis tot de plaats van de kaas te berekenen, immers er kunnen wel eens muren op staan. b.2.) Zoeken in alle richtingen Beginnend bij de oorspronkelijke plaats van de muis zoeken we in alle richtingen een weg naar de kaas. Van alle mogelijke wegen kiezen we dan de kortste weg. De kortste weg vanaf de oorspronkelijke plaats is één stap meer dan de kortste weg vanaf de buurtegels. Voor elk van de vrije buurtegels wordt de lengte van de kortste weg vanaf dat veld bepaald. Op elke volgende tegel herhalen we dit zoeken in alle richtingen. Een bezwaar dat direct in het oog springt is dat we heel makkelijk in cirkeltjes kunnen gaan ronddraaien. Dit kunnen we voorkomen door te noteren of we de betreffende tegel al bezocht hebben. Bovendien moeten we de afstand in tegels bijhouden.

6.2.3 De gegevensstructuur De voor de handliggende gegevensstructuur voor de doolhof is een matrix. In deze matrixelementen moeten we vier verschillende mogelijkheden noteren, namelijk: vrij, muur, kaas en muis. TYPE STATUS = ( Vrij, Muur, Muis, Kaas ); VAR Doolhof = ARRAY [ 1..n, 1..m ] OF STATUS ;

Een sjabloon voor het bepalen van de ‘kortste weglengte vanaf’ is: PROCEDURE kortste weglengte vanaf {Meegeven: x en y, de positie van waaruit de kortste weg moet worden gezocht} {Opleveren: de lengte van de kortste weg} BEGIN IF reeds bij kaas THEN lengte van de kortste weg := 0 ELSE BEGIN zet muis op lege aangrenzende pleintegel neem de minimumafstand uit de vier richtingen haal muis weer terug van die tegel lengte van de kortste weg := minimum + 1 END END

met als verfijnde uitwerking van ‘neem de minimumafstand uit de vier richtingen’: ga uit van een minimumafstand := oneindig groot ; kijk of minimumafstand kleiner wordt voor een muis naar het noorden ; kijk of minimumafstand kleiner wordt voor een muis naar het oosten ; kijk of minimumafstand kleiner wordt voor een muis naar het zuiden ; kijk of minimumafstand kleiner wordt voor een muis naar het westen.

waarbij ‘kijk of minimumafstand kleiner wordt voor een muis naar het noorden’ als volgt kan worden uitgewerkt: (naar noorden: een regel naar boven op het beeldscherm): IF kan gaan naar (kolom, regel + 1) THEN minimumwaarde van ( minimum totnogtoe, kortste weglengte vanaf( kolom, regel+1 ));

idem voor naar het oosten, zuiden en westen. Om te onderzoeken of de muis een stap in een bepaalde richting kan maken, moet die plaats (= pleintegel) vrij zijn of daarop de kaas liggen. Het kan nìet als er een muur staat! 64


Sjabloon:


FUNCTION kan gaan naar {Meegeven: kolom- en regelnummer van de pleintegel, waar de muis naar toe wil; } {Functie moet opleveren : True/False (Boolean)} BEGIN IF binnen doolhof THEN TERUG GEVEN: ( doolhof [ kolom, regel ] = vrij of kaas ) ELSE TERUG GEVEN: FALSE END { kan gaan naar }

Hier volgt de Pascal uitwerking tot een (bijna volledig) programma: program

Muis_in_het_doolhof;

TYPE

STATUS = ( Vrij, Muur, Muis, Kaas ) ;

VAR

Doolhof = ARRAY [ 1..n, 1..m ] OF STATUS ; { Hier moeten nog declaraties van constanten en variabelen komen en initialisatie van het doolhof}

FUNCTION Kan_gaan_naar( kolom, regel : INTEGER ) : BOOLEAN ; BEGIN IF {binnen_doolhof} (kolom >= 1) AND (kolom <= n) AND (regel >= 1) AND (regel <= m) THEN Kan_gaan_naar := (doolhof[kolom,regel] = vrij) OR (doolhof[kolom,regel] = kaas) ELSE Kan_gaan_naar := FALSE; END ; PROCEDURE Kortste ( VAR Minimum : Integer; TeTestenWaarde : Integer); BEGIN IF TeTestenWaarde < Minimum THEN Minimum := TeTestenWaarde END ; FUNCTION Kortste_weglengte_vanaf( kolom, regel : INTEGER ) : INTEGER ; VAR Minimum : Integer; BEGIN IF { reeds bij kaas: } Doolhof[ kolom, regel] = Kaas THEN Kortste_weglengte_vanaf := 0 ELSE BEGIN { bezet tegel met muis } Doolhof[ kolom, regel] := Muis; { neem het minimum van de vier richtingen } minimum := oneindig ; { oneindig: erg groot getal } { een muis naar : } { noorden } IF kan_gaan_naar( kolom, regel + 1) THEN Kortste ( minimum, Kortste_weglengte_vanaf( { oosten } IF kan_gaan_naar( kolom + 1, regel) THEN Kortste ( minimum, Kortste_weglengte_vanaf( { zuiden } IF kan_gaan_naar( kolom, regel - 1) THEN Kortste ( minimum, Kortste_weglengte_vanaf( { westen } IF kan_gaan_naar( kolom - 1, regel) THEN Kortste ( minimum, Kortste_weglengte_vanaf(

kolom, regel +1)); kolom +1, regel)); kolom, regel -1)); kolom -1, regel));

{ keer terug (‘back tracking..’): geef de pleintegel weer vrij: } Doolhof[ kolom, regel ] := Vrij; Kortste_weglengte_vanaf := minimum + 1; END END; BEGIN { hoofd programma } Writeln(‘Kortste weglengte vanaf (12,3) = ‘, Kortste_weglengte_vanaf(2,3)) END .

De muis zal nu alle wegen naar de kaas vinden. De algoritme zal termineren wanneer alle mogelijke wegen afgetast zijn. • Het de functie mag alleen worden aangeroepen vanaf een tegel binnen het doolhof. • de functie mag alleen worden aangeroepen vanaf een tegel die vrij is of waarop de kaas ligt. 65



Zoals het programma boven is geschreven is deze controle vijf keer nodig. Het is verstandiger deze controle te plaatsen aan het begin van de functie. De FUNCTION ‘Kortste_weglengte_vanaf’ wordt dan gewijzigd in onderstaande FUNCTION ‘Kortste_weglengte_via’. FUNCTION Kortste_weglengte_via ( x, y : INTEGER ): INTEGER ; VAR Minimum : INTEGER; BEGIN IF {NOT binnen doolhof} NOT ((x >= 1) AND (x <= n) AND (y >= 1) AND (y <= n)) { oneindig: heel grote constante} THEN Kortste_weglengte_via := oneindig ELSE CASE Doolhof[ x, y ] OF Vrij : BEGIN { zet muis op die tegel } Doolhof [x, y] := Muis; { neem het minimum van de vier richtingen: } Minimum := Kortste_weglengte_via (x + 1, y ); Kortste ( Minimum, Kortste_weglengte_via ( x - 1, y ) ); Kortste ( Minimum, Kortste_weglengte_via (x, y +1) ); Kortste ( Minimum, Kortste_weglengte_via (x, y - 1) ) { haal muis weer terug van Doolhof[x, y] := Vrij Kortste_weglengte_via END; Muur, Muis : Kortste_weglengte_via Kaas : Kortste_weglengte_via END {Case} END;

die tegel en geef hem dus weer vrij: } ; := 1 + Minimum := oneindig; := 0

We laten de functie de kortste afstand tot de kaas aangeven. Dit komt overeen met de kleinste recursie-diepte. (Waarom niet andersom, de afgelegde afstand vanaf de oude muispositie?) Als de kaas gevonden is wordt de lengte van de terugweg (kortste_weglengte_vanaf) 0. Bij het terugkeren uit de recursie wordt de terugweg steeds één opgehoogd. Vraag: Welke waarde krijgt die lengte van de terugweg? Terugweg krijgt de waarde van het aantal stappen van de laatst gevonden weg naar de kaas. Als we de kortste weg willen weten moeten we het minimum van de terugwegen bijhouden.

6.3

Probleemschets: “het stabiele huwelijk”

(met complexe voorwaarden)

Een bekend probleem uit de literatuur over back tracking is dat van het zogenaamde ‘stabiele huwelijk’. Hoe houd je relaties ‘stabiel’ als er verschil in voorkeuren tussen personen zitten? Stel je de situatie voor dat een groepje jongens (Cor, Jan, Jos en Ron) en meisjes (Ine, Lia, Mia en Ria) een avondje uit willen. Maar wie gaat er met wie? Ze stellen allemaal een lijstje op van hun voorkeur: De voorkeur van de jongens: 1 2 3 4

Cor : Jan : Jos : Ron :

Mia , Ine , Lia , Ria Lia , Ria , Mia , Ine Lia , Ine , Mia , Ria Ria , Lia , Ine , Mia

De voorkeur van de meisjes: 1 2 3 4

Ine : Jan , Jos , Cor , Ron Lia : Ron , Jos , Cor , Jan Mia : Cor , Jan , Jos , Ron Ria : Jos , Jan , Cor , Ron

Een mogelijke oplossing vanuit de jongens gezien is: Cor en Mia, Jan en Lia, Jos en Ine, Ron en Ria. Een mogelijke oplossing vanuit de meisjes gezien is: Ine en Jan, Lia en Ron, Mia en Cor, Ria en Jos. Geven we de jongens zoveel mogelijk hun eerste keus dan gebeurt er waarschijnlijk het volgende: Cor en Mia zullen tevreden zijn. Lia heeft Jan als laatste voorkeur en zal dus ontevreden zijn. Ine heeft Jos op de tweede plaats . . . moet kunnen? Ria heeft Ron op de laatste plaats en zal dus ook ontevreden zijn. Jos ziet echter Lia meer zitten dan Ine en bovendien heeft Lia Jos veel liever dan de haar opgedrongen Jan. Ine vindt het heerlijk dat Lia heibel maakt, want nu komt Jan vrij. Helaas, jammer voor Ine, want Jan moet niets van haar hebben. Ria ziet Jan alleen en grijpt haar kans om van Ron af te komen. Voor Ron en Ine ontstaat er nu een 66



onbevredigende situatie, want zij moeten elkaar niet zo erg. Ron besluit achter z’n tweede keus, Lia aan te gaan en dit lukt. Lia vindt Ron geweldig en laat Jos in de steek. De treurende Ine en de verlaten Jos keren in elkaars armen terug. Je ziet waarschijnlijk het probleem annex de vraagstelling al zitten: “Welke parencombinatie moet gemaakt worden om te komen tot een stabiele situatie, waarbij iedereen relatief/optimaal tevreden/gelukkig is?” Voor een uitwerking van dit probleem met complexe voorwaarden verwijzen we naar die literatuur.

6.4

Varianten, aanpassingen en uitbreidingen bij back track-algoritmen

We hebben in voorgaande bespreking voorbeelden gezien van het via back tracking vinden van: • ‘gewoon alle’ oplossingen (zoals bij de paarden op het schaakbord) • de minimum- of maximumwaarde (zoals bij de muis in het doolhof) • een optimale situatie, waarbij gebruik gemaakt werd van een complexe samenhang tussen grootheden (zoals bij het ‘stabiele huwelijk-probleem’, waarbij die samenhang in tabelvorm aangegeven w erd). Eerder hebben we (in een voetnoot) ook al aangegeven, dat de sequentie ‘zet een stap’ / ‘ga (recursief) verder zoeken’ / ‘maak de laatste stap ongedaan’ (het eigenlijke ‘ back tracken’), soms ook vervangen kan worden door een aanpak, waarbij een verandering (lees: een volgende stap) ook doorgevoerd kan worden door in de recursieve aanroep van de ‘ga verder zoeken’-procedure een Value-parameter een zodanige (andere) waarde mee te geven, dat het gehele proces van de vervolgstap geïsoleerd blijft tot de volgende incarnatie van de recursief aangeroepen procedure (een aanroep als ‘probeer ( diepte + 1)’ verandert immers niets aan de lokale waarde van ‘diepte’). In zo’n geval hoeven we zo’n vervolgstap (uiteraard: afhankelijk van de verdere uitwerking) binnen de procedure zelf, niet meer ongedaan te maken. Meerdere aanpassingen zijn mogelijk. Zo kan als je bijvoorbeeld op zoek bent naar het minimum van een waarde die door volgende recursieve aanroepen slechts groter kan worden (zoals in iets van : probeer := lokaal_bepaalde_waarde + probeer ( vervolgstap) ) het recursieve vervolgproces afgebroken worden als je reeds een waarde gevonden hebt, die reeds groter is dan een al eerder gevonden (voorlopige) waarde. Immers: de huidige waarde zou dan via recursie alleen maar nog verder kunnen toenemen, terwijl we op zoek zijn naar een mogelijk kleinere waarde dan die al gevonden voorlopig-minimale-waarde. Dit is een voorbeeld van het afkappen van bepaalde delen van het trial-and-error back track zoekproces.

Heuristieken In hommenage aan Archimedes (juist, die van de kreet ‘Eureka’) gebruikt men het woord heuristiek voor een strategie, methode, vuistregel of truc, die ertoe de dient de zoekruimte op een acceptabele manier te beperken. Soms blijkt al spoedig, dat het vervolgen van een eerder ingeslagen zoekweg ongewenste eindresultaten oplevert. Zo’n zoekweg kun je dan afkappen en al back trackend ‘op je schreden terugkeren’. Stel je bijvoorbeeld voor, dat je voor de muis op zoek naar kaas al een (voorlopig) kortste zoekweg hebt gevonden van ’20 tegels’. Als je dan ‘ergens’ bij het volgen van een andere zoekweg al op een totale weglengte van 22 bent gekomen en nog steeds niet bij de kaas bent aangeland, dan kun je terugkrabbelen van de huidige zoekweg, omdat die nooit een kortere weglengte dan de eerder gevonden 20 kan opleveren. Om deze aanpak te kunnen uitvoeren is het nodig om op de een of andere manier (bijvoorbeeld via een extra parameter) bij te houden welke weg de muis al heeft afgelegd. Het vinden van slimme heuristieken en/of vuistregels (bijvoorbeeld: “als het hard waait en de muis ruikt toch kaas, dan kan hij het beste gaan zoeken in de richting waar de wind vandaan komt”). Het kan zijn dat voor zo’n slim zoeken de te gebruiken datastructuur aangepast moet worden. Zoals al eerder opgemerkt: een aantal van deze zoekstrategieën komen uit de hoek van de kunstmatige intelligentie. Bij de uitwerking van het volgende voorbeeld bespreken we onder meer het ‘eerst in de diepte zoeken’ ( depth first) [al dan niet met een branch and bound-strategie] of ‘eerst in de breedte zoeken’ ( breadth first). Daarnaast bestaan o.a. de ‘best first’-aanpak en het zogenaamde A*-algoritme, maar beiden blijven hier onbesproken. Alle aanpakken hebben hun specifieke aanpakken, voordelen, nadelen en voorwaarden.

67


6.5


Probleem: de schuifpuzzel

We gaan proberen oplossingen te vinden voor het bekende (?) probleem van ‘de schuifpuzzel’, waarbij je moet proberen genummerde vakjes binnen een vierkant frame Beginsituatie Eindsituatie zodanig te verschuiven, dat een geordende situatie ontstaat, waarbij het lege vakje zich helemaal rechtsonder in het vierkant 1 2 3 1 2 3 Hoe te bevindt en de overige vakjes zodanig zitten, dat de nummers van schuiven? links naar rechts en van boven naar beneden steeds toenemen 4 5 4 5 6 (voor een 3x3-voorbeeld zie de getoonde figuuur hiernaast, waar het ‘lege veld’ via een kleurtje is aangegeven). 6 7 8 7 8 Verschuivingen van het lege elementje (vakje) kan hooguit in vier richtingen plaatsvinden: opwaarts, neerwaarts, naar rechts en naar links. Beginsituatie Er staat ‘hooguit in vier richtingen’, omdat e en verschuiving nooit zodanig kan zijn, dat het lege vakje van het 1 2 3 speelvierkant zou verdwijnen [zo kan vanuit die eindsituatie 4 5 het lege vakje hooguit naar boven of naar links verplaatst 6 7 8 worden]. mogelijke verschuivingen Het gebezigde woordgebruik doet misschien ietwat vreemd op rechts neer links aan: het ‘lege vakje’ schuift [in de figuur] naar boven omdat je in werkelijkheid het vakje met nummer ‘2’ naar beneden 1 3 1 2 3 1 2 3 1 2 3 schuift. We zullen ons verder houden aan dat woordgebruik 4 2 5 4 5 4 7 5 4 5 waarin we met het ‘lege vakje’ schuiven. 6

7

8

6

7

8

6

8

6

7

8

We stellen ons nu de vraag: hoeveel verschuivingen (en welke) moet je minimaal doen om de getoonde beginsituatie om te zetten naar de eindsituatie? We zullen het fenomeen van ‘schuiven met het lege vakje’ eerst duidelijker moeten analiseren. Als we ons beperken tot een 2x2-vierkant, bekijk dan eens de volgende achtereenvolgende verschuivingen waarbij we uiteindelijk weer in de uitgangssituatie terug komen (het lege vakje is aangegeven met een ‘-‘): - 1 2 3

rechts

1 2 3

neer

links

1 3 2 3 2 - 1

op

1 3 - 2

- 2 3 1

rechts

op

- 3 1 2 2 3 1

rechts

neer

3 1 2

2 1 3 -

neer

links

links

3 2 1 -

2 1 - 3

op

- 1 2 3

Je kunt daarin zien, dat [in dit geval] we pas na 12 verschuivingen in de beginsituatie zijn terug gekomen en dat ondertussen al verschillende keren het lege vakje ‘linksboven’, dus op dezelfde plek als in de uitgangssituatie, is ‘langs gekomen’. Kortom: als we een bepaalde situatie willen beschrijven, kunnen we daarvoor niet alleen de positie van het lege vakje aangeven, maar moeten we de gehele inhoud van het puzzel-vierkant beschrijven. We gaan voor ons probleem een oplossingsprogramma ontwikkelen en beginnen met de volgende aanzetten: CONST

Hoogte = 3 ; { of 2 } Breedte = Hoogte ;

TYPE

TMATRIX = ARRAY [ 1..Hoogte, 1..Breedte

] OF BYTE ;

TRICHTING = ( Op, Rechts, Neer, Links ) ;

{ in klokrichting }

We leggen de eerder getoonde begin- en eindsituatie van ons puzzelveld op een ‘inzichtelijke manier’ als volgt vast via getypeerde constanten: CONST

{ we initialiseren hier de speelborden via getypeerde constanten } BeginSituatie : TMATRIX = ( (1,2,3), (4,0,5), (6,7,8) ) ; EindSituatie : TMATRIX = ( (1,2,3), (4,5,6), (7,8,0) ) ;

Omdat we willen voorkomen dat we ‘in cirkeltjes gaan draaien’ zullen we de gehele geschiedenis van reeds doorlopen speelvelden moeten onthouden. Omdat dat weleens flink veel kan worden, doen we dat op de Heap via een lineaire lijst van records. Bovendien zullen we die geschiedenis-lijst [na het uitkomen bij de eindsituatie] gebruiken om te laten zien via welke tussenstadia we daar gekomen zijn. We definiëren: 68



PSITUATIE = ^TSITUATIE ; TSITUATIE = RECORD Matrix : TMATRIX ; Vervolg : PSITUATIE END ;

We definiëren als ‘wortel-pointer’ van die geschiedenis -lijst: VAR Historie en zullen die vaak als parameter bij procedure-aanroepen meegeven.

: PSITUATIE ;

We verwachten vaak met de positie van [vooral] het lege veld te moeten gaan werken en definiëren een positierecordstructuur: TPOSITIE = RECORD X, Y : END ;

BYTE

Om succesvol met een back tracking-procedure [en een aansturend hoofdprogramma] aan de slag te kunnen gaan, verwachten we de volgende procedures en functies nodig te hebben: PROCEDURE FUNCTION FUNCTION PROCEDURE PROCEDURE FUNCTION PROCEDURE

ToonSituatie ( Bord : TMATRIX ) ; ZijnGelijk ( Matrix1, Matrix2 : TMATRIX ) : BOOLEAN ; AlEerderGehad ( Bord : TMATRIX ; Historie: PSITUATIE ) : BOOLEAN ; BepaalPositieLegePlaats( Matrix: TMATRIX; VAR LegePlek: TPOSITIE); VerschuifLegePlek ( VAR Matrix : TMATRIX ; Richting : TRICHTING ); VerschuivingMogelijk ( Matrix: TMATRIX; Richting: TRICHTING ) : BOOLEAN ; VoegSituatieToe ( Bord : TMATRIX; VAR Historie : PSITUATIE ) ;

Voor toepassen van het back track-mechanisme (‘terug krabbelen’) zal zeker nodig zijn: PROCEDURE VerschuifLegePlekTerug (VAR Matrix: TMATRIX; Richting: TRICHTING); PROCEDURE VerwijderLaatstGeprobeerdeSituatie ( VAR Historie : PSITUATIE ) ;

Voor het uiteindelijk tonen van het hele oplossingstraject maken we: PROCEDURE

ToonVerloop ( Historie : PSITUATIE ) ;

en het eigenlijke back track-algoritme plaatsen we tenslotte in: PROCEDURE

ProbeerVerschuiving ( VAR SpeelVeld : TMATRIX; VAR Historie : PSITUATIE ) ;

Deze procedure roepen we aan vanuit het hoofdprogramma: Historie := NIL ; VoegSituatieToe ( BeginSituatie, Historie ) ; ProbeerVerschuiving ( Beginsituatie, Historie ) ;

en zoeken dan maar . . . (houd een flinke pot koffie bij de hand). Van de genoemde basisprocedures geven we hier [mogelijke] uitwerkingen: PROCEDURE ToonSituatie ( Bord : TMATRIX ) ; VAR Xpositie, Ypositie : BYTE ; BEGIN FOR Ypositie := 1 TO Hoogte DO BEGIN FOR Xpositie := 1 TO Breedte DO IF Bord [ Ypositie, Xpositie ] = 0 { de 'lege plek' } THEN Write ( '.' ) ELSE Write ( Bord [ Ypositie, Xpositie ] ) ; Write ( ' | ' ) { of: Writeln voor als we een mooie matrix willen} END ; Writeln { ( '----' ) als scheidingstekens i.g.v. weergave als matrix} END ; FUNCTION ZijnGelijk ( Matrix1, Matrix2 : TMATRIX ) : BOOLEAN ; VAR Xpositie, Ypositie : BYTE ; VoorlopigGelijk : BOOLEAN ; BEGIN

69



VoorlopigGelijk := TRUE ; FOR Xpositie := 1 TO Breedte DO { kan efficiënter, maar dan meer code } FOR Ypositie := 1 TO Hoogte DO IF Matrix1 [ Ypositie, Xpositie] <> Matrix2 [ Ypositie, Xpositie ] THEN VoorlopigGelijk := FALSE ; ZijnGelijk := VoorlopigGelijk END ; PROCEDURE BepaalPositieLegePlaats ( Matrix: TMATRIX; VAR LegePlek: TPOSITIE ) ; VAR Xpositie, Ypositie : BYTE ; BEGIN FOR Xpositie := 1 TO Breedte DO { kan efficiënter, maar dan meer code } FOR Ypositie := 1 TO Hoogte DO IF Matrix [ Ypositie, Xpositie ] = 0 THEN BEGIN LegePlek.X := Xpositie ; LegePlek.Y := Ypositie ; END END ; PROCEDURE BEGIN { Matrix Matrix END ;

Verwissel ( VAR Matrix: TMATRIX; LegePlek, NieuwePlek: TPOSITIE ) ; dit is een hulp-procedure ! } [ LegePlek.Y, LegePlek.X] := Matrix [ NieuwePlek.Y, NieuwePlek.X]; [ NieuwePlek.Y, NieuwePlek.X ] := 0 { geen 'echt verwisselen' nodig }

PROCEDURE VerschuifLegePlek ( VAR Matrix : TMATRIX ; Richting : TRICHTING ) ; VAR Leeg, Nieuw: TPOSITIE ; BEGIN BepaalPositieLegePlaats ( Matrix, Leeg ) ; CASE Richting OF Op : BEGIN Nieuw.Y := Leeg.Y - 1 ; Nieuw.X := Leeg.X END ; Neer : BEGIN Nieuw.Y := Leeg.Y + 1 ; Nieuw.X := Leeg.X END ; Rechts : BEGIN Nieuw.X := Leeg.X + 1 ; Nieuw.Y := Leeg.Y END ; Links : BEGIN Nieuw.X := Leeg.X - 1 ; Nieuw.Y := Leeg.Y END ; END ; { aanroepen ‘hulp’-procedure } Verwissel ( Matrix, Leeg, Nieuw ) END ; PROCEDURE VerschuifLegePlekTerug (VAR Matrix: TMATRIX; Richting: TRICHTING ); BEGIN CASE Richting OF Op : VerschuifLegePlek ( Matrix, Neer ) ; Neer : VerschuifLegePlek ( Matrix, Op ) ; Rechts: VerschuifLegePlek ( Matrix, Links ) ; Links : VerschuifLegePlek ( Matrix, Rechts ) ; END ; END ; FUNCTION VerschuivingMogelijk ( Matrix: TMATRIX; Richting: TRICHTING) : BOOLEAN; VAR LegePlek : TPOSITIE ; BEGIN BepaalPositieLegePlaats ( Matrix, LegePlek ) ; CASE Richting OF Op : VerschuivingMogelijk := ( LegePlek.Y > 1 ) ; Neer : VerschuivingMogelijk := ( LegePlek.Y < Hoogte ) ; Rechts : VerschuivingMogelijk := ( LegePlek.X < Breedte ) ; Links : VerschuivingMogelijk := ( LegePlek.X > 1 ) ; END END ; PROCEDURE VoegSituatieToe ( Bord : TMATRIX; VAR Historie : PSITUATIE ) ; VAR NaarNieuwRecord : PSITUATIE ; BEGIN New ( NaarNieuwRecord ) ; NaarNieuwRecord^.Matrix := Bord ; NaarNieuwRecord^.Vervolg := Historie ; { LIFO-stack } Historie := NaarNieuwRecord ; END ; PROCEDURE ToonVerloop ( Historie : PSITUATIE ) ; BEGIN IF Historie = NIL THEN { eventueel: Writeln ( 'Einde/NIL!' ) } ELSE BEGIN ToonVerloop ( Historie^.Vervolg ) ; { achterste element eerst tonen } ToonSituatie ( Historie^.Matrix ) ; END

70



END ; FUNCTION AlEerderGehad ( Bord : TMATRIX ; Historie: PSITUATIE ) : BOOLEAN ; BEGIN IF Historie = NIL THEN AlEerderGehad := FALSE ELSE IF ZijnGelijk ( Bord, Historie^.Matrix ) THEN AlEerderGehad := TRUE ELSE AlEerderGehad := AlEerderGehad ( Bord, Historie^.Vervolg ) END ; PROCEDURE VerwijderLaatstGeprobeerdeSituatie ( VAR Historie : PSITUATIE ) ; VAR Hulp : PSITUATIE ; BEGIN Hulp := Historie ; IF Historie = NIL THEN Writeln ( 'Historie leeg; er kan niets verwijderd worden!' ) ELSE BEGIN Historie := Historie^.Vervolg ; Dispose ( Hulp ) { LIFO-stack! } END ; END ;

Voordat we ons nu richten op het back trackende hart van het programma, geven we hier eerst het aansturend hoofdprogramma: VAR Historie

: PSITUATIE ;

BEGIN Historie := NIL ; Write ( 'Beginsituatie: ' ) ; ToonSituatie ( BeginSituatie ) ; Write ( 'Eindsituatie : ' ) ; ToonSituatie ( EindSituatie ) ; VoegSituatieToe ( BeginSituatie, Historie ) ;

ProbeerVerschuiving ( BeginSituatie, Historie ) ; Writeln ( Chr(13) + 'Dat was het dan ... ') ; { alleen de Beginsituatie zit nog in de 'Historie-lijst': } VerwijderLaatstGeprobeerdeSituatie ( Historie ) END.

Het enige wat dit hoofdprogramma eigenlijk doet, is om de beginsituatie als eerste in de lineaire lijst van ‘al behandelde speelveldsituaties’ op de Heap zetten en vervolgens de back trackende procedure ProbeerVerschuiving ( . . .) aan te roepen. De rest van het hoofdprogramma is te zien als ‘randversiering’. En dan nu de back trackende hoofdmoot (althans: in een eerste versie; andere versies volgen): { 1e versie: } PROCEDURE

ProbeerVerschuiving ( SpeelVeld : TMATRIX; VAR Historie : PSITUATIE ) ;

VAR Richting : TRICHTING ; BEGIN { oplossing gevonden ! } IF ZijnGelijk ( SpeelVeld, EindSituatie ) THEN BEGIN Writeln ( Chr(13) +'Eindsituatie gevonden via de verschuivingen: '); ToonVerloop ( Historie ) ; Write ( 'Oplossing gevonden; druk op <Enter> '); Readln ; END ELSE FOR Richting := Op TO Links DO { alle richtingen bekijken } BEGIN IF VerschuivingMogelijk ( SpeelVeld, Richting ) THEN BEGIN { en dan nu 'echt': } VerschuifLegePlek ( SpeelVeld, Richting ) ;

IF NOT AlEerderGehad ( SpeelVeld, Historie ) THEN BEGIN VoegSituatieToe ( SpeelVeld, Historie ) ;

{

}

ProbeerVerschuiving ( SpeelVeld, Historie ); VerwijderLaatstGeprobeerdeSituatie ( Historie ) END

71



{ ELSE Writeln ( ‘Al eerder gehad; niet toegevoegd! ‘ ) } ; VerschuifLegePlekTerug ( SpeelVeld, Richting ) END ; END ; END ;

Hopelijk is de naamgeving zodanig betekenisvol gekozen, dat je zelfstandig in staat bent de werking van deze procedure te doorgronden.

Indien we het programma eerst eens loslaten op de volgende 2x2-speelveldsituatie: BeginSituatie : TMATRIX = ( (0,1), (3,2) ) ; EindSituatie : TMATRIX = ( (3,0), (2,1) ) ;

dan geeft ons programma de volgende uitvoer (let op: een ‘punt’ (‘.’) staat voor ‘ leeg’ veld ): Beginsituatie: .1 | 32 | Eindsituatie : 3. | 21 | Eindsituatie gevonden via de verschuivingen: .1 | 32 | 1. | 32 | 12 | 3. | 12 | .3 | .2 | 13 | 2. | 13 | 23 | 1. | 23 | .1 | .3 | 21 | 3. | 21 | Eindsituatie gevonden via de verschuivingen: .1 | 32 | 31 | .2 | 31 | 2. | 3. | 21 | Dat was het dan ...

Ga voor jezelf na dat deze twee oplossingen te verwachten waren. Als je echter uitgaat van de volgende situatie: BeginSituatie : TMATRIX = ( (1,0), (2,3) ) ; EindSituatie : TMATRIX = ( (3,0), (2,1) ) ;

dan vindt het programma géén verschuivingsoplossing! Ga zelf na dat dat ook dit terecht is. En dan nu het ‘echte werk’ met de gegeven 3x3-schuifpuzzel begin- en eindsituatie . . . . Als je het programma daarmee opstart, meldt het zich na een paar minuten met de teleurstellende boodschap ‘Stack overflow’ (en dat terwijl het stack segment al op de maximale 64 kB was gezet). Na het inbouwen van een ‘recursiediepte-tellertje’ bleek die stack overflow zich voor te doen bij een recursiediepte van meer dan 1000. Veranderen van de eerste parameter (‘SpeelVeld’) van de procedure van ‘ Value’-parameter naar ‘Var’-parameter levert een paar honderd eenheden extra aan recursiediepte op, maar blijft de Stack overflow-melding opleveren. Als je voor die recursiediepte een begrenzing inbouwt van maximaal 200, dan komt er uiteraard géén stack overflow-melding meer. Je ziet aan het getoonde recursiediepte-tellertje, dat die diepte bijna steeds zo tussen de 190 en die maximale 200 zit. Het duurt een hele kop thee voordat het programma zich eindelijk meldt met een gevonden schuif-oplossing op een recursiediepte van 196! En daarna kun je het weer verder laten zwoegen . . . Maar eigenlijk zijn deze uitkomsten niet interessant; niemand lijkt geïnteresseerd om 196 schuif-bewegingen te gaan maken bij dat puzzelspel. Waarom duurt dat zoeken zo lang; wat gebeurt er en vooral: “Zijn er niet op een gemakkelijkere wijze korte(re) oplossingen te vinden?”.

6.5.1 Depth First-zoeken Het probleem is, dat onze ProbeerVerschuiving(. . .)-procedure een typische zogenaamde Depth First-aanpak heeft (dat geldt trouwens voor alle tot nog toe in dit hoofdstuk behandelde voorbeelden). Hij begint bijvoorbeeld als eerste stap met proberen in de ‘omhoog’-richting te gaan en als dat kan, probeert hij in de volgende procedure-incarnatie ook weer ‘omhoog’ te gaan etc.. Als hij met dat ‘omhoog’ proberen te gaan op 72



recursiediepte ‘n’ daarvan weerhouden wordt [doordat dat òf niet mogelijk is, òf dat die situatie zich al heeft voorgedaan], dan zal hij op die diepte ‘n’ gaan proberen om in de volgende richting verder te gaan en zodoende daar weer méér recursiediepte te winnen. Als we zeer ruwweg stellen, dat op iedere recursiediepte van de vier bestaande richtingen er gemiddeld twéé mogelijk zijn, dan neemt het aantal af te zoeken mogelijkheden exponentieel toe (als 2n). Onze opmerking van daarstraks, dat bij een maximale recursiediepte van 200 het tellertje vooral tussen de 190 en de 200 stond, hoeft nu dus niet meer te verbazen . . . Of nog een andere kwantitatieve overweging: bij een 3x3-speelveld hebben we (inclusief het lege veld) te maken met 9 vakjes die in 9! (= 362880) mogelijke permutatie-vormen kunnen voorkomen [het kan zijn dat hier wat aspecten over het hoofd gezien worden, maar het is duidelijk, dat het om een enorm grote zoekruimte gaat]. Het is dan weinig zinvol om via verbeteringen van technische details (bijvoorbeeld door het optimalizeren van een aantal procedures of door samen met elke situatie [bijvoorbeeld in een record] steeds op te slaan wat de positie van het lege veld is, zodat we niet steeds weer de procedure BepaalPositieLegePlaats(. . .) hoeven aan te roepen) te proberen het zoekproces toch wat (een factor 2?) sneller te laten verlopen. We moeten op zoek gaan naar (artificieel) intelligentere zoekstrategieën om gerichter tot een oplossing te komen. Daarvoor moeten we eerst goed inzicht hebben in wat we eigenlijk aan het doen zijn. In de hiernaast weergegeven figuur wordt een zeer ruw model geschetst van wat er aan de hand is. Via de smalle driehoeken wordt aangegeven, dat boven aan de top van zo’n driehoek een ‘oplossing’ zit en dat het donkere gebied daaronder niet meer hoeft te worden afgezocht (want ‘onder’ een gevonden oplossing ga je niet zoeken). Oplossingen die liggen binnen het gebied dat aangegeven is met ‘Stack overflow-gebied’ kunnen we [met onze recursieve aanpak] niet vinden.

Aantal zoekpaden (ruwweg logaritmische schaal) ‘beste oplossing’ (d.w.z. met kleinste recursiediepte)

Recursiediepte Stack overflow - gebied

Volgorde bij het doorlopen van de zoekpaden

De Depth First-aanpak is in het algemeen de meest eenvoudige manier indien we ‘alle’ oplossingen willen bepalen. Wat ons vaak waarschijnlijk het meest interesseert, is de vraag naar de ‘beste’ oplossing (in deze specifieke situatie betekent ‘beste’: met het kleinste aantal verschuivingen en dus met de kleinste recursiediepte); hoe kunnen we die zo snel mogelijk vinden? Daar zijn een aantal bekende mogelijkheden voor, waarvan we er hierna een aantal bespreken.

6.5.2 De Branch and Bound-aanpak We vermeldden eerder al, dat we [om stack overflow te voorkomen] een recursiediepte-tellertje hadden ingebouwd en dat we de ‘Depth First’-aanpak afbraken als die verder dan de door ons toegestane maximum diepte wilde gaan. Het idee achter ‘Branch and Bound’ is, om zodra we op een bepaalde recursiediepte (‘n’) een eerste oplossing gevonden hebben [en op zoek zijn naar de beste oplossing], we die diepte (‘n’) van de g evonden oplossing als nieuw toegestane maximum recursiediepte nemen. We verhinderen zo dat we ‘slechtere oplossingen’ vinden en gaan alleen verder met de hoop op betere. Aantal zoekpaden (ruwweg logaritmische schaal) We beperken onze af te lopen zoekruimte op deze manier erg ingrijpend. Schematisch is door middel van ‘beste oplossing’ (d.w.z. met kleinste een vetgekleurde lijn de grens van het nog af te lopen recursiediepte) zoekgebied in de volgende figuur aangegeven. Alleen Beginwaarde recursiegrens het gebied linksboven van die vetgekleurde lijn wordt afgezocht. Recursiediepte

We tonen de om dit doel te bereiken aangepaste ProbeerVerschuiving(. . .)-procedure en het eveneens aangepaste hoofdprogramma [let vooral op de functie van de parameters ‘Diepte’ en ‘KortsteTotNogToe’ ]:

Stack overflow - gebied


{ 2e versie: } PROCEDURE

ProbeerVerschuiving ( {VAR} SpeelVeld : TMATRIX; VAR Historie : PSITUATIE; Diepte: INTEGER;

VAR KortsteTotNogToe : INTEGER ) ; VAR Richting : TRICHTING ; BEGIN GotoXY (1, 25 ); Write ( 'Recursiediepte=', diepte ) ;

73

{om te tonen: 'het loopt'}


{


IF ZijnGelijk ( SpeelVeld, EindSituatie ) THEN BEGIN Writeln ( Chr(13) +'Eindsituatie gevonden via de verschuivingen: '); } KortsteTotNogToe := Diepte ; { aanpassen Branch and Bound-grens } ToonVerloop ( Historie ) ; Write ( 'Oplossing gevonden bij recursiediepte: ', Diepte, '. Druk op <Enter> ..'); Readln ; END ELSE

{

}

IF KortsteTotNogToe > Diepte THEN

{Branch and Bound: verder?}

FOR Richting := Op TO Links DO BEGIN IF VerschuivingMogelijk ( SpeelVeld, Richting ) THEN BEGIN { en dan nu 'echt': } VerschuifLegePlek ( SpeelVeld, Richting ) ;

IF NOT AlEerderGehad ( SpeelVeld, Historie ) THEN BEGIN VoegSituatieToe ( SpeelVeld, Historie ) ;

{

ProbeerVerschuiving ( SpeelVeld, Historie, diepte + 1, KortsteTotNogToe );

}

VerwijderLaatstGeprobeerdeSituatie ( Historie ) END ; VerschuifLegePlekTerug ( SpeelVeld, Richting ) END ; END ; END ;

VAR Historie

: PSITUATIE ;

RelatiefSnelste : INTEGER ; BEGIN ClrScr ;

{ hoofdprogramma }

RelatiefSnelste := 100 ;

{ of bij geen stack problemen : MaxInt } Historie := NIL ; Writeln ( 'Beginsituatie: ' ) ; ToonSituatie ( BeginSituatie ) ; Writeln ( 'Eindsituatie : ' ) ; ToonSituatie ( EindSituatie ) ; Write ( 'Starten ... druk op <Enter> .. ') ; Readln ; VoegSituatieToe ( BeginSituatie, Historie ) ;

ProbeerVerschuiving ( BeginSituatie, Historie, 0, RelatiefSnelste ); Writeln ( Chr(13) + 'Dat was het dan ... ') ; { alleen de Beginsituatie zit nog in de 'Historie-lijst': } VerwijderLaatstGeprobeerdeSituatie ( Historie ) ; Readln END.

Als we het programma in deze aangepaste vorm laten lopen, dan duurt het bij een initiële recursiediepte-grens van 100 nog eeeeerrrrrrggggg lang [en komen er veel oplossingen van bijvoorbeeld diepte 96 (3x), 94, 92, 90 (2x), 86 (7x), etc.]; bij starten met een maximale diepte van 50 duurt het nog steeds eeerrrggg lang [met oplossingen zoals 48 (3x), 44, 42, 40, 38, 36 (2x), 34 . .], starten met een maximale recursiediepte van 25 levert [cpu op 300 MHz] binnen ongeveer 2 minuten als oplossingen op: 22 verschuivingen (2x), 20 (2x), 16 en als kortste: 14 verschuivingen. Die gevonden beste oplossing wordt als volgt op het beelscherm getoond: Eindsituatie gevonden via de verschuivingen: 123 | 4.5 | 678 | 123 | 45. | 678 | 123 | 458 | 67. | 123 | 458 | 6.7 | 123 | 458 | .67 | 123 | .58 | 467 | 123 | 5.8 | 467 | 123 | 568 | 4.7 | 123 | 568 | 47. | 123 | 56. | 478 | 123 | 5.6 | 478 | 123 | .56 | 478 | 123 | 456 | .78 |

74



123 | 456 | 7.8 | 123 | 456 | 78. | Oplossing gevonden bij recursiediepte: 14. Druk op <Enter> ..

En met : “Dat was het dan ... ” geeft het programma aan geen kortere oplossingen te hebben ontdekt. Tja, maar hoe weet je nu of je moet starten met een maximale recursiediepte van 100, 50, . . ?

6.5.3 Breadth First zoeken Een andere oplossings-zoekstrategie is om niet de (recursie-) diepte in te duiken, maar om (‘horizontale’) ‘laag -na-laag’ van bovenuit de ‘punt’ van de zoekruimte te zoeken. Deze zoekstrategie wordt ‘Breadth First’ genoemd (‘eerst in de breedte’). De implementatie van een echte ‘ Breadth First’aanpak is ietwat gecompliceerder 2. Als je op een bepaald recursie-niveau meerdere vervolgwegen aantreft, dan zet je die ‘achteraan’ op een FIFO-stack [waar de vervolgmogelijkheden van het huidige recursie-niveau nog als eerste aan de beurt moeten komen].

Breadth Firstaanpak (laag na laag)

Aantal zoekpaden (ruwweg logaritmische schaal) ‘beste oplossing’ (d.w.z. met kleinste recursiediepte)

Recursiediepte Stack overflow - gebied


Het volgende is beslist géén formele Breadth First-aanpak, is waarschijnlijk zeker minder (ca. een factor 2?) efficiënt dan een échte Breadth First, maar vindt in ons geval toch binnen een paar seconden de beste oplossing (die op de kleinste recursiediepte 14). Plaats daarvoor de aanroep van de ProbeerVerschuiving-procedure in een kleine herhalingsconstructie als: { stukje van een 3e versie: } FOR Diepte := 1 TO 25 DO { of bijvoorbeeld: MaxInt } BEGIN RelatiefSnelste := Diepte; ProbeerVerschuiving ( BeginSituatie, Historie, 1, RelatiefSnelste ) ; END ;

Je begint op deze wijze steeds boven in de top van de zoekruimte en moet helaas voor een diepte van bijvoorbeeld 12 eerst alle eraan voorafgaande niveau’s steeds opnieuw doorlopen (terwijl bij een echte Breadth First-aanpak die vorige niveau’s op de FIFO -stack zouden zijn gezet). N.B. Deze herhalingsconstructie levert problemen op met het laten beëindigen van het programma (maar dat is hier geen expliciet leerdoel; verzin er zelf maar een betere constructie voor).

2

Althans: implementatie is gecompliceerder als we dat met een 3e generatietaal als Pascal doen. In specifiek op Artificial Intelligence toegespitste talen als Prolog is zoeken via Breadth First net relatief eenvoudig te implementeren. 75


6.6


Practicumopdracht over back tracking: treintrajecten

In de I:\voorb2ld-directory tref je het TEXT-bestand ‘Verbind.txt’ aan, waarin van een aantal (10 à 15) trajecten tussen treinstations de reisafstand in (gehele) km is aangegeven. De via zo’n ‘traject’ bereikbare plaatsen zijn (o.a.): Nijmegen, Elst, Arnhem, Ede-Wageningen, Utrecht, Amsterdam, Haarlem, Den Bosch, Venlo, Roermond en Maastricht (je kunt dit bestand naar eigen smaak uitbreiden en/of aanpassen). Schrijf nu een ‘backtrackend’ programma, dat gebruik maakt van de volgende Types en Record -structuur: TYPE

PLAATS = STRING [ 15 ] ; TRAJECT = RECORD eerste, tweede : afstand : END ;

PLAATS ; REAL

TRAJECTEN = ARRAY [ 1 .. Max_aantal ] OF TRAJECT ;

De trajectgegevens in het TEXT-bestand staan steeds in de volgorde: ‘eerste plaats’, , ‘tweede plaats’, , ‘onderlinge afstand’ . a)

Schrijf nu allereerst een procedure ‘Vul_Trajectrij’, die de trajectgegevens zoals aanwezig in het bestand ‘Verbind.txt’ een voor een inleest en in een ‘trajectenrij’ stopt. Uiteraard moet bijgehouden worden hoeveel trajectgegevens worden ingelezen. Test de procedure uit.

b) En dan de kern van deze opgave: maak een procedure ‘Probeer_Verbinding (.....)’, die al back trackend [volgens de Depth First-aanpak] gaat proberen een verbindend traject tot stand te brengen tussen een bij oproep meegegeven beginstation en een (eveneens meegegeven) eindstation. Zorg ervoor, dat de procedure bij houdt, wat bij een correct traject het afgelegde traject is (plaats daarvoor de namen van de ‘aangedane stations’ in een ‘afgelegd_traject’ -string) en dat de procedure ook de totaalafstand voor dat afgelegde traject bijhoudt (als getal). Als beperkende voorwaarde geldt uiteraard, dat een trein gedurende zo’n traject niet ‘in rondjes’ mag gaan rijden’ en daarom een reeds op dat traject ‘gepasseerd station’ niet nog een keer mag aan doen. (Je kunt daarvoor desgewenst de ‘Pos’-functie gebruiken om te bepalen of de naam van een bepaald station al voorkomt in die afgelegd_traject-string.) Laat als je al back trackend ‘op de plek (= station) van bestemming’ bent aangekomen, het afgelegde traject en de bijbehorende totale reisafstand zien. Test je procedure uit. c)

Je hebt (waarschijnlijk) ontdekt, dat de gevonden reistrajecten tussen begin- en eindstation beslist niet op een voor een gebruiker voor de hand liggende wijze op het scherm verschijnen. Maak daarom een [eveneens Depth First] variant op je procedure ‘Probeer_verbinding (......)’ (noem hem ook anders, zodat je beide procedures in je code kunt inleveren), waarbij telkens bij het vinden van een nieuw toegestaan traject, de trajectstring (inclusief reisafstand) op zo’n manier in een dynamische lineaire lijst wordt opgenomen, dat trajecten daarin geordend worden naar toenemende reisafstand. Laat vervolgens -als alle trajecten bepaald zijn- die trajecten (inclusief afstand) naar toenemende reisafstand op het scherm verschijnen (dus met eerst het kortste traject etc.). Test je procedure uit.

d) Pas in je oplossing van onderdeel c) nu het branch and bound-principe op een ietwat aangepaste wijze toe, zodat je daarmee [een derde versie van de ‘Probeer_verbinding (......)’-procedure] zo snel mogelijk het kortste traject (in km) tussen twee opgegeven plaatsen vindt, maar ook nog steeds trajecten die tot 20 kilometer langer kunnen zijn (dit is niet zo’n vreemd idee; ook de NS -Reisplanner vermeldt af en toe immers: “U reist via een omweg . . .”). Let er op, dat het branch and bound-principe hier niet op de recursiediepte moet werken, maar op de totale reisafstand!

76

6 Oplossingen zoeken via Back track -algoritmen

Recommend Documents