Een combinatorisch zoekalgoritme is een algoritme dat in een computer kan geprogrammeerd worden om specifieke zoekproblemen op te lossen. Een voorbeeld van zo een probleem, een combinatorisch probleem, is het ordenen van een verzameling van 10 elementen. Dat het hier niet om een eenvoudig probleem gaat merken we al aan de vele manieren waarop we de 10 elementen kunnen ordenen. Dit zijn er 3.628.800. We zeggen dat de zoekruimte die ermee overeenkomt zeer groot is. Dit is een algemene eigenschap van combinatorische problemen. Het gaat steeds om een systeem (de verzameling) dat zich in verschillende toestanden (de verschillende ordeningen) kan bevinden. Meestal is de oplossing van het probleem niet de gehele verzameling van toestanden of combinaties, maar slechts een kleine deelverzameling ervan. Het is dan aan de computer om deze deelverzameling te bepalen. In ons voorbeeld zouden de elementen van de verzameling personen kunnen zijn. We zouden dan kunnen eisen dat als twee personen naast elkaar geplaatst worden steeds de jongste links moet staan. In dit geval zal er maar één ordening uit de 3.628.800 mogelijke ordeningen over blijven.
Praktisch kunnen we een combinatorisch probleem altijd oplossen door alle combinaties daadwerkelijk na te gaan en zo uiteindelijk de oplossingen te vinden. Dit is de naïeve versie van het algoritme. Er bestaan er natuurlijk betere. Bij het probleem van de personen kunnen we direkt de correcte oplossing opschrijven. We ordenen ze gewoon van jong naar oud.
We merken al dat we het zelfde probleem dus met naïeve en intelligente algoritmes kunnen oplossen. Hoe intelligenter deze algoritmes worden, hoe moeilijker ze ook te begrijpen worden. Vandaar de nood om deze te visualiseren.

Een voorbeeld: Queens

Het probleem is hier de plaatsing van n koninginnen op een n x n schaakbord, zonder dat ze elkaar kunnen slaan. Door alle mogelijke combinaties of toestanden na te gaan kan de computer tot een oplossing komen, vandaar dat we van een combinatorisch probleem spreken. Een toestand wordt in dit geval eenduidig bepaald door de coördinaten van de vakjes waar een koningin staat. De zoekruimte is hier nog niet zo heel groot daar het niet uitmaakt welke koningin op een bepaald hokje staat. Alle koninginnen zijn hetzelfde.
Het is echter niet nodig om alle combinaties daadwerkelijk na te gaan. Veel combinaties blijken namelijk in een vroeg stadium te kunnen worden uitgeschakeld. In deze zin kan het algoritme dan worden verbeterd, zodat de computer intelligenter wordt en sneller tot een oplossing komt.
Dit probleem werd geïmplementeerd door onze begeleider. Het was een voorbeeld voor ons werk.

Visualisatie

Onze opdracht is niet het uitzoeken van de algoritmes. Deze bestaan meestal reeds en/of worden door onze begeleider geïmplementeerd. Wij zelf zullen zorgen voor de visualisatie. Onder visualisatie verstaan we dat de computer het algoritme stap voor stap uitvoert en na elke stap het tussenresultaat op het scherm laat zien. Dit betekent dat wij het volgende gaan verzorgen:

Het maken van een grafische voorstelling van het probleem op het computerscherm.
Het visualiseren van elke stap die het algoritme beschrijft om tot een oplossing te komen. Dit laatste moet weer op grafische wijze op het scherm worden voorgesteld.

Op deze manier wordt het algoritme ‘gedemonstreerd’. De gebruiker kan door de grafische voorstelling zeer eenvoudig volgen wat het algoritme doet en het vervolgens gemakkelijk doorgronden. Het geeft de toeschouwer dus inzicht in de manier waarop de computer denkt! De toeschouwer kan dan ook verschillende algoritmes vergelijken wat efficiëntie betreft en begrijpt ook waarom het ene algoritme sneller is dan het andere. Hiermee hebben we dan ook ons doel bereikt: de visualisatie van een combinatorisch zoekalgoritme.

Probleemstelling

Het specifieke probleem dat wij gaan aanpakken is een blokkenpuzzel. Dit is zeker een combinatorisch probleem daar de puzzelstukjes op verschillende manieren tegen elkaar kunnen geplaatst worden. Elke manier komt hierbij overeen met een toestand zoals we dit in de inleiding noemden. We leggen eerst even de termen uit opdat geen verwarring mogelijk zou zijn.

Bord: Een puzzel wordt opgelost op een bord met een specifieke vorm. Als vorm komt hier elke veelhoek met hoeken van 90° in aanmerking.
Blokje: De puzzelstukjes. Dit zijn de elementen die we in het bord moeten puzzelen. Het zijn dus ook veelhoekjes met orthogonale ribben.
Kubusje: Omwille van de geometrie kunnen we zowel blokjes als bord opbouwen uit vierkantjes. Daar de blokjes ook een zekere dikte hebben krijgen we kubusjes. Dit hoort eigenlijk al bij de vooropgestelde oplossing, maar we vermelden het hier al voor de volledigheid.

We vatten het probleem dus redelijk algemeen op. We onderscheiden een aantal blokjes die de computer in het bord moet plaatsen. We geven een voorbeeld.

De bedoeling is om de gegeven blokjes in het voorgestelde kruis (bord) te puzzelen. Hierbij mogen de blokjes gedraaid (geroteerd) en omgekeerd (gespiegeld) worden, wat een bijkomende moeilijkheid geeft en dus een vergroting van de zoekruimte. Wij kozen voor de eenvoud voor een vlakke puzzel. Dit hoeft echter niet het geval te zijn. Men kan zich bijvoorbeeld een puzzel indenken waarbij men, met een aantal blokjes, een balletje moet samenstellen. Dit is eigenlijk hetzelfde probleem, doch in een hogere dimensie.
Natuurlijk is een blokken puzzel maar één voorbeeld. We hadden ook puzzels kunnen beschouwen waar het de bedoeling is om een tekening samen te stellen, zoals bijvoorbeeld bij legpuzzels het geval is. Een ander soort puzzels dat hier ook niet aan bod komt, zijn de puzzels waarbij het resultaat reeds bekend is, maar waarbij we de oplossings-methode moeten zoeken. Een voorbeeld hiervan zijn schuifpuzzels. Bij het oplossen van puzzels gebruikt de mens zijn intuïtie. De computer heeft die niet. Hij moet voor elke zet steunen op een algoritme. De bedoeling is dat we dit algoritme visualiseren.

Vooropgestelde oplossing

Hier beschrijven we de oplossing zoals voorgesteld bij het voorontwerp. Bepaalde zaken zijn in de uiteindelijke realisatie gewijzigd. Deze wijzigingen worden besproken in hoofdstuk 5.

Visualisatie van de blokjes op het computerscherm.

Zoals gezegd zullen we ons beperken tot een tweedimensionale puzzel. Dit omdat een driedimensionale puzzel moeilijk is voor te stellen en aanleiding zou geven tot een zeer grote zoekruimte.
Om de blokjes in het computergeheugen voor te stellen zullen we ze opbouwen uit kleinere identieke onderdelen. Hiervoor kiezen we kubusjes omdat deze in de geometrie van de blokjes en het bord passen en bovendien symmetrisch zijn. Het op het scherm tonen van de puzzel gebeurt in militair perspectief. Deze driedimensionale voorstelling heeft als voordeel dat we blokjes over elkaar kunnen laten schuiven in verschillende lagen. Telkens als een blokje in een opening in een lager gelegen laag past, zal het er in vallen en zijn we een stapje dichter bij de oplossing van de puzzel.
Om de blokjes van elkaar te kunnen onderscheiden gebruiken we kleuren. Elk blokje krijgt een kleur voor het bovenvlak en een andere kleur voor de zijvlakken. Als we bijvoorbeeld over 16 kleuren beschikken, dan zijn er op deze manier ongeveer 16 x 16 blokjes mogelijk.

Voorstelling van het bord

Het bord zelf stellen we voor als een rechthoekig blokje met in het midden een opening die de vorm heeft van de puzzel (het kruis uit het voorbeeld). De bedoeling is dan om deze opening te vullen met de andere blokjes.
Bij de voorstelling op het scherm zullen de blokjes die passen net op gelijke hoogte komen met het bord. Dit heeft als voordeel dat het bord niet achter de blokjes verborgen wordt en viceversa.

Visualisatie van het algoritme

In de volgende stap moeten we het algoritme dat de computer volgt om de puzzel op te lossen visualiseren. Er bestaan verschillende algoritmes om de blokkenpuzzel op te lossen. Het is niet de bedoeling dat wij hieruit de beste kiezen. We zullen ze allemaal visualiseren zodat de toeschouwer elke methode kan begrijpen en met de overige vergelijken. We leggen nu elk algoritme uit en bespreken de manier waarop we het gaan visualiseren.

Naive

Bij het eerste algoritme genereert de computer één voor één alle combinaties. Een combinatie wordt hier bepaald door de posities en rotaties van alle blokjes. Enkele van al deze combinaties zijn oplossingen van de gegeven puzzel. Door telkens een controle door te voeren kan de computer nagaan of hij een oplossing heeft gevonden.
Praktisch komt dit er op neer dat de computer eerst alle blokjes in de linker-achter-hoek van het bord zal plaatsen. Tijdens de controle zal de computer merken dat dit niet de oplossing is. Er mogen immers geen twee blokjes op dezelfde plaats staan. Hij zal dit verhelpen door het bovenste blokje te verplaatsen enz...
Om aan te geven dat alle blokjes op dezelfde positie staan zullen we ze in de 3D-weergave op het computerscherm op elkaar stapelen. De blokjes bewegen zo in lagen. Als er maar één laag meer overblijft is de oplossing gevonden.

Bij de controle ziet de computer dat het bovenste blokje fout ligt. Dit maken we duidelijk in de visualisatie door er een rood kruis over te tekenen. Vervolgens wordt het blokje verplaatst (of geroteerd indien alle mogelijke posities zijn nagegaan). Dit algoritme is zeer naïef en heeft een grote zoekruimte. Er zijn immers zeer veel combinaties mogelijk. Al deze combinaties nagaan is zelfs voor een computer veel werk. Daarom zullen we intelligentere algoritmes nodig hebben.

Java demo van het naive algoritme

Coroutining

Een combinatie waarbij twee blokjes op dezelfde positie (boven elkaar) staan kan geen oplossing voor de puzzel zijn. Hiermee gaan we bij deze versie van het algoritme rekening houden. De computer plaatst hier de blokjes één voor één en bij elk geplaatst blokje controleert hij of alles nog klopt. Vandaar de naam 'Coroutining'. De genereer-routine en de test-routine werken nauwer samen dan bij 'Naïve'. Daar was het immers zo dat steeds een gehele oplossing werd gegenereerd en dan pas gecontroleerd.
Door telkens de controle door te voeren zullen we steeds met slechts één laag blokjes werken. Het volgende blokje zal de computer over deze laag schuiven tot het bij een opening komt waar het in past. Hier zal de computer het blokje dan in plaatsen en zal hij verder gaan met een volgend blokje. Hierdoor kan het niet meer gebeuren dat de computer, na een hele combinatie gegenereerd te hebben, moet concluderen dat het eerste blokje van die combinatie al verkeerd lag.
De visualisatie is bij dit algoritme grotendeels analoog aan die van de naïve methode. Het verschil zit hem zoals gezegd in het feit dat geen stapels blokjes meer voorkomen omdat er geen blokjes meer zijn die op dezelfde positie van het bord staan.

Coroutining without doubles

Deze uitbreiding van het vorige algoritme steunt op het feit dat symmetrische blokjes door rotatie en/of spiegeling op zichzelf kunnen worden afgebeeld. Tussen de acht mogelijke rotaties van een blokje zullen dan identieke vormen voorkomen. Deze identieke vormen kunnen we schrappen bij het oplossen van de puzzel. Dit verkleint de zoekruimte omdat er bijvoorbeeld voor een blokje met twee aan twee identieke rotaties er maar 4 rotaties ipv 8 moeten uitgeprobeerd worden.

De visualisatie is ook bij dit algoritme grotendeels dezelfde als bij het vorige. Er is echter een kleine uitbreiding noodzakelijk. Wanneer de computer een blokje in een rotatie tegenkomt die identiek is met een voorgaande, dan tekenen we deze rotatie en zetten er een ‘vogeltje’ (Ö checkmark) bij. Dit kunnen we vergelijken met een lijst van mogelijkheden waarvan we de reeds beschouwde aanduiden met een kruisje of met een vogeltje. Daarna gaat de computer verder met de volgende rotaties en blokjes.

Java demo van het Coroutining algoritme

De keuze van de programmeertaal

Bij de keuze van een programmeertaal kijken we eerst naar de doelstelling. Belangrijke kenmerken van een taal zijn de snelheid, de functionaliteit en de vorm van programmeren.
Een uitstekende taal om onze algoritmes in te programmeren is Prolog. De grootste reden daarvoor is dat men abstractie kan maken van hoe men een algoritme gaat implementeren. Men geeft aan hoe een resultaat er moet uitzien en niet hoe men tot dat resultaat moet komen.
Omdat Prolog enkel tekst-georiënteerd werkt kunnen we er moeilijk de visualisatie mee maken. Zo komen we bij Tcl/Tk. We kozen voor Tcl/Tk omdat dit een taal is waarin men gemakkelijk grafisch kan werken. Enkele ondersteunde elementen zijn de windows (vensters) met popup-menu’s (rolmenu’s), de frames (kaders om objecten in te groeperen), de buttons (knoppen),...
Nu hebben we dus twee aparte programmeertalen, Prolog en Tcl/Tk. Deze twee talen moeten met elkaar kunnen communiceren. Deze functie is gelukkig reeds beschikbaar in een bibliotheek.
Download page voor de TclTk-Prolog bibliotheek (FREE)

De uiteindelijke realisatie

Algemene voorstelling

De voorstelling van de blokjes blijft zoals voorgesteld bij het ontwerp. We tonen naast het voorgestelde perspectief ook nog een bovenaanzicht. Verder hebben we besloten om de gebruiker een overzicht van alle blokjes met hun rotaties te geven bovenaan het venster. We delen de beschikbare ruimte op in evenveel rechthoeken als er blokjes zijn. Dit doen we zodanig dat we in elk rechthoekje de verschillende rotaties van één blokje kunnen plaatsen. De gebruiker kan nu beter het programma volgen en daarenboven levert deze manier van werken ook nog een aantal voordelen op wat de verdere visualisatie betreft.

Voorstelling van de blokjes met rotatie

In de uiteindelijke realisatie is er bij elk algoritme de keuze om de dubbels te beschouwen of niet. We beschouwen dit dus niet meer als een apart algoritme, doch eerder als een optie bij de verschillende algoritmes. De visualisatie is bijgevolg anders dan voorgesteld bij het ontwerp. We plaatsen alle blokjes met al hun rotaties bovenaan het venster. Wanneer de computer dan een bepaald blokje beschouwt, tekent hij er een vierkantje rond. Dit vierkantje is groen bij het blokje waarmee hij werkt en rood bij een reeds geplaatst blokje. Als dusdanig weet de gebruiker steeds waar de computer juist mee bezig is.

Voorstelling van de dubbels

Tussen de rotaties van de verschillende blokjes vinden we vaak dezelfde vormen of dubbels terug. duiden we aan door de gepaste rotaties te doorkruisen bovenaan het scherm. Deze rotaties zal de computer nooit beschouwen, en dit is nu ook voor de gebruiker duidelijk.

De verschillende algoritmes

De verschillende algoritmes zijn beschikbaar via het menu 'Algorithm'. Hier kunnen we kiezen uit 5 verschillende algoritmes : 'Naive' , 'Coroutining', 'Space Checking', 'Friend Space' en ''. VerderSmart One is er nog de optie of we 'Doubles' toelaten of niet. (Doubles slaat hier op de rotaties die dubbel zijn).

Naive

We vatten hier nog even samen hoe het naïve algoritme werkt. De computer genereert een mogelijkheid en controleert of ze de oplossing is. Hij zet de blokjes dus gewoon ergens neer en hoopt dat hij zo de oplossing vindt. Dit willen we ook tot uiting laten komen in onze visualisatie en dus tonen we de blokjes op het scherm zoals reeds beschreven. Het enige dat in de definitieve versie van het programma anders is dan in het ontwerp is dat we geen kruis tekenen bij een foute combinatie. Het brengt immers niet veel bij tot de visualisatie. Het is enerzijds altijd hetzelfde blokje dat overkruist zou worden, namelijk het laatste. Anderzijds ziet de gebruiker zelf wel wanneer we de oplossing nog niet bereikt hebben. Daarom tonen we gewoon hoe de computer de blokjes verschuift en wanneer de computer hiermee stopt, hebben we de oplossing gevonden.
Bovenaan het venster tonen we van elk blokje de rotatie die het algoritme beschouwt.

Java demo van het naive algoritme

Coroutining

De visualisatie van het coroutining algoritme verandert principieel niet. De visualisatie is dezelfde als bij het naïve algoritme, met dit verschil dat we maar met 2 lagen werken : de laag van de blokjes die passen en deze van het blokje dat niet past. Deze visualisatie sluit, evenals deze van het vorige algoritme, sterk aan bij de realiteit.

Java demo van het Coroutining algoritme

Space Checking

Wanneer we het coroutining algoritme bekijken, merken we een fenomeen op dat zich regelmatig voordoet. De computer plaatst vaak een blokje waardoor hij een vrij gebied insluit waar geen ander blokje meer in past. Hij gaat dan gewoon verder met zoeken, terwijl dit eigenlijk nutteloos is. We weten immers op voorhand dat dit geen oplossing kan geven. Daarom voeren we een test in die zulke gevallen opspoort. De redenering achter een eerste, eenvoudige test is als volgt : wanneer we ergens een vrij plaatsje vinden in het bord, dan weten we dat dit in de oplossing bezet zal moeten worden. Dan rijst de vraag of er rond dit vrij plaatsje nog genoeg andere vrije plaatsjes zijn zodanig dat we met een bepaald blokje dit vrije plaatsje kunnen bezetten. We beschouwen de hoogtes en breedtes van alle blokjes en nemen uit deze verzameling het maximum (we noemen dit n). We beschouwen nu rond het vrij plaatsje een vierkant met het vrij plaatsje in het midden en met zijde 2n-1. Dan weten we dat welk blokje we ook plaatsen om het vrije plaatsje onder te stoppen, alle kubusjes van dit blokje liggen dan binnen dit vierkant. Dit geldt ook als we de blokjes mogen roteren of spiegelen. We tellen vervolgens alle vrije plaatsjes binnen dit vierkant en vergelijken het met het aantal kubusjes van het kleinste blokje. Als het gevonden aantal kleiner is, dan weten we zeker dat we fout zitten. Als het groter of gelijk is, dan kunnen we geen conclusie trekken en doen we gewoon voort.

Op de tekening zien we dit een beetje verduidelijkt. In deze tekening is n gelijk aan 3 en dus 2n-1 gelijk aan 5. Het is eenvoudig te controleren dat elk blokje dat het vrije blokje met het dik kruis over bedekt, binnen het beschouwde vierkant valt (wat buiten het vierkant valt is niet getekend). De test slaagt hier terecht. De tekening toont reeds een deel van de visualisatie die bij het geschetste algoritme hoort. Wat de plaatsing van de blokjes betreft is dit algoritme hetzelfde als het coroutining algoritme, hetgeen ook geldt voor de visualisatie ervan. De visualisatie van het 'Space Checking' is echter nieuw. Het vrije vlakje dat we beschouwen kruisen we aan (in het geel). We tekenen daarna ook het vierkant. Vervolgens kruisen we elk vrij plaatsje binnen dit vierkant eveneens aan (in het groen). Faalt de test, dan verandert het kruis boven het vrij plaatsje van kleur (het wordt rood), anders blijft het geel. We tonen ook een boodschap die vertelt of de test geslaagd is of niet en waarom wel of waarom niet. Daarna verwijderen we alle kruisjes en het vierkant. Deze manier van werken moet ervoor zorgen dat de gebruiker in een oogopslag kan zien waar het schoentje knelt.

Friend Check

De test uit het 'Space Checking' algoritme is echter niet efficiënt. We beschouwen daarvoor een (fictief) voorbeeld dat dit onmiddelijk duidelijk maakt. Er staan reeds 4 blokjes van 1 op 1 op het

bord. De test uit het vorige algoritme zal waarschijnlijk deze situatie als een mogelijkheid aanzien, terwijl er niet veel voor nodig is om te weten dat dit niet zo is. Het volgend algoritme zal hiermee rekening houden. Het enige dat verandert t.o.v. het vorige algoritme is de test. We beschouwen nu geen vierkant meer rond het vrij plaatsje. We gaan echter zoeken naar een veld van aaneengesloten vrije plaatsjes die ook het eerste bevat. Dit gebeurt door vanuit het vrije blokje in elke richting te zoeken naar andere, aangrenzende vrije blokjes. Als we er zo vinden dan zoeken we verder vanuit het nieuwe vrij blokje naar nog andere vrije blokjes, enz. Het aantal vrije plaatsjes dat in het gevonden veld zit wordt vergeleken met het minimum van de groottes van de nog niet geplaatste blokjes. Wanneer de test faalt, weten we dat we fout zitten.

Het is duidelijk dat we op deze manier telkens een kleiner aantal vrije plaatsjes krijgen en dus strenger selecteren dan het Space Checking algoritme. Om nog efficiënter te werk te gaan, houden we gedurende de test bij welke vrije plaatsjes we reeds gecontroleerd hebben met inbegrip van deze die in het gevonden, vrije veld zitten. Deze testen we later niet meer zodat we geen overbodige controles doen. We visualiseren deze test op analoge manier als de vorige test, d.w.z. we kruisen het vrije plaatsje dat we beschouwen aan in een bepaalde kleur en kruisen vervolgens elk vlakje uit het vrije veld aan met een andere kleur. Faalt de test, dan kleuren we het kruisje boven het beschouwde vrije vlakje rood. Er verschijnt verder nog een boodschap die uitleg geeft over het falen of slagen van de test. Deze visualisatie maakt het eenvoudig de test te volgen en onmiddelijk te begrijpen waarom de test faalt.

Java demo van het space algoritme

Smart One

Al de vorige algoritmes kunnen opgedeeld worden in 2 groepen wat betreft de manier waarop de blokjes op het bord geplaatst worden. Het naïve algoritme plaats alle blokjes op het bord, of ze nu passen of niet. 'Coroutining', 'Space Checking' en 'Friend Check' gaan anders te werk : ze plaatsen de blokjes één voor één en plaatsen pas een volgend blokje als het vorige past. Wat het feitelijk doet is kijken waar het blokje geplaatst kan worden. Ondanks de vrij goede test van het algoritme 'Friend Space' blijven er vrij veel gaten over waar waarschijnlijk geen blokje meer in kan. We kunnen dit op 2 manieren verhelpen : een waterdichte test ontwerpen of de blokjes op een andere manier plaatsen. De eerste oplossing is niet mogelijk daar dit neerkomt op het oplossen van de puzzel. We weten immers pas zeker dat we op de goede weg zitten als we al een deel van de oplossing hebben. Dit laatste weten we pas als we de oplossing hebben gevonden. De tweede oplossing daarentegen biedt wel mogelijkheden. We gaan het bord rij per rij een plaatsje per plaatsje af tot we een vrij plaatsje vinden. Vervolgens proberen we een blokje te plaatsen zodat dit plaatsje bezet wordt. Als dusdanig proberen we alle gaten op te vullen. Vervolgens voeren we een test uit. Hierop komen we later nog terug. Als de test slaagt, dan zoeken we opnieuw een vrij plaatsje op de reeds beschreven manier. We proberen dan weer een blokje te plaatsen op dit vrij plaatsje. Dit gaat door tot we de oplossing gevonden hebben. Merk op dat deze methode zich bij het plaatsen van de blokjes op het bord niet houdt aan de volgorde waarin deze opgegeven zijn. Het zoekt telkens een blokje dat past, doet er niet toe welk. Met als gevolg dat de tijd nodig voor het oplossen minder afhankelijk is van de volgorde van de blokjes of van de rotaties. Het is ook veel efficiënter dan al de vorige algoritmes vanwege het feit dat de meeste gaten opgevuld worden. Eigenlijk maakt dit een bijkomende test in vele gevallen onnodig : als er geen gaten zijn, dan kunnen ze ook moeilijk te klein zijn. Toch voeren we een test in die nog iets verfijnd is tegenover deze uit het 'Friend Space' algoritme. We redeneren als volgt : we zoeken een veld van aaneengesloten vrije plaatsjes. In dit veld zal, indien we tot een oplossing willen komen, een aantal van de blokjes geplaatst moeten worden. Een nodige voorwaarde hiervoor is dat het aantal vrije vlakjes in het gevonden veld te schrijven moet zijn als een som van de groottes van 1 of meerdere blokjes. Daarom genereren we in het begin een lijst met alle mogelijke sommen van groottes van blokjes. We geven hier een voorbeeld : stel we hebben drie blokjes met groottes 3, 3 en 2. De lijst van alle mogelijke sommen vinden we bijvoorbeeld als volgt :

3 doet mee	3 doet mee	2 doet mee	binaire code	decimale code	som
nee	nee	ja	0 0 1	1	0+0+2
nee	ja	nee	0 1 0	2	0+3+0
nee	ja	ja	0 1 1	3	0+3+2
ja	nee	nee	1 0 0	4	3+0+0
ja	nee	ja	1 0 1	5	3+0+2
ja	ja	nee	1 1 0	6	3+3+0
ja	ja	ja	1 1 1	7	3+3+2

Dit levert ons volgende lijst van getallen (zonder dubbels) : {2, 3, 5, 6, 8}. Wanneer we nu een veld vinden van grootte 5 dan weten we dat hierin enkel blokje 2 en 3 passen of blokje 1 en 3. Wanneer we een veld van grootte 7 vinden, weten we dat dit niet mogelijk is. Een eventuele verbetering kan erin bestaan om de lijst aan te passen naarmate er blokjes geplaatst worden. Dit wordt nog niet geïmplementeerd. De visualisatie van deze test blijft volledig analoog aan deze van het vorig algoritme. Enkel de boodschap die getoond wordt, moet aangepast worden. Wanneer de computer een blokje tracht te plaatsen op een bepaald vrij plaatsje dan kruisen we dit plaatsje aan. Vervolgens tonen we hoe de computer het blokje beweegt over dit kruisje tot het blokje past. Omdat het blokje het getekende kruisje overlapt, tekenen we dit nog eens opnieuw over het kubusje dat vlak boven het vrije plaatsje staat en dus ook boven het eerst getekende kruisje. We krijgen zo een verzorgde weergave van wat er eigenlijk gebeurt.

Java demo van het 'Smart One' algoritme

Verdere opties bij het programma

Het programma heeft verder nog een aantal opties die beschikbaar zijn via het menu en het geheel gebruiksvriendelijk moeten maken.

Het Command - menu

'Load' is de eerste optie uit dit menu. Wanneer we hierop klikken, krijgen we een nieuw venstertje (een message-box) dat toelaat een nieuwe puzzel te laden. Dit was in eerste instantie niet de opdracht, doch het was handig bij het testen en geeft meer mogelijkheden naar de gebruiker toe. 'Start' is de volgende keuzemogelijkheid. Deze start het algoritme dat in het 'Algorithm' menu is aangeduid. Het algoritme kan gestopt worden via de keuze 'Stop' uit hetzelfde menu. Daarna kan men het algoritme niet meer laten voortgaan in tegenstelling tot de menu-optie 'Pause'. Wanneer we hierop klikken, pauzeert het algoritme en wordt de checkbox horende bij deze menu-optie 'gechecked'. Nogmaals aanklikken van deze optie doet het algoritme voortgaan en 'uncheckt' de checkbox. Als laatste optie vinden we hier 'Exit'. Dit stopt het algoritme dat eventueel nog bezig is en sluit het programma af.

Het Algorithm - menu

De eerste vijf checkboxjes laten ons toe om te kiezen uit een bepaald algoritme. Slechts één algoritme kan tegelijkertijd actief zijn. De optie Doubles vertelt het aangeduide algoritme om al of niet dubbels toe te laten.

Het Speed - menu

Hier kunnen we kiezen uit een aantal snelheden. Deze keuze bepaalt de wachttijd tussen de verschillende stappen van de visualisatie. We dienen wel op te merken dat de tijdsverschillen niet zeer groot zijn.

Het Visualisation - menu

De None - optie geeft het algoritme de instructie om niets te visualiseren. Bijgevolg lost de computer het algoritme op zonder tijd te verliezen aan het tekenen van de blokjes hetgeen nogal tijdrovend is. Wanneer de puzzel opgelost is, tonen we in een venster hoeveel tijd de computer nodig had om de puzzel op te lossen. Dit laat de gebruiker toe om de verschillende algoritmes te vergelijken qua efficiëntie.
De Each Brick - optie vertelt het algoritme om enkel de blokjes te tonen die reeds passen. We zien dus niet hoe de computer de blokjes probeert te passen. We zien enkel het resultaat van zijn zoekwerk.
Als de Each Rotation - optie aangeduid is toont de computer hoe hij zoekt. Dit doet hij door in de lijst bovenaan het venster met een vierkantje aan te duiden met welke blokjes en welke rotaties hij aan het werken is. Deze visualisatie is minimaal maar laat toch toe het algoritme te volgen.
Enkel wanneer de Each Position - optie aan staat, toont de computer de visualisatie zoals aangegeven bij de bespreking van de verschillende algoritmes. Hij laat de blokjes over elkaar schuiven. Dit toont volledig wat de computer doet.
Een kleine uitbreiding krijgen we wanneer we de Let's Fly - optie aan zetten. Wanneer de computer dan een nieuw blokje of rotatie nodig heeft, laat hij een blokje vliegen uit de lijst bovenaan naar het bovenaanzicht. Het brengt eigenlijk niets bij tot de visualisatie en staat er enkel bij omdat het mooier is.
Wat de visualisatie van de test betreft kan je een eerste optie No Space Checking kiezen. Deze toont totaal niets van de test die hij uitvoert. We kunnen opmaken of de test geslaagd is uit de volgende stap die de computer onderneemt. Wanneer hij het blokje direct verplaatst dan faalde de test, anders slaagde hij. Aldus kunnen we alles nog altijd volgen.
De computer toont iets meer wanneer we de optie Space Errors gekozen hebben. Dan visualiseert hij de test zoals besproken in het visualisatie gedeelte enkel en alleen wanneer deze faalt.
Slechts wanneer de Space Checking optie aangeduid staat, visualiseert hij de test telkens als hij hem uitvoert. Hier kunnen we zien waarom de test slaagt of faalt.
De reden waarom we kunnen kiezen tussen verschillende visualisaties is dat de volledige visualisatie soms nogal traag is en het vervelend wordt om te wachten. Dan kunnen we een eenvoudigere visualisatie kiezen en zo het algoritme versnellen en het toch nog kunnen volgen.

Het View - menu

Het View - menu heeft slechts twee opties. De computer toont normaal twee aanzichten : een vooraanzicht (het militair perspectief) en een bovenaanzicht. Via de opties uit dit menu kunnen we een van beide of allebei uitschakelen. De bedoeling was om de visualisatie eventueel te versnellen doordat de computer minder werk zou hebben. Het effect is echter niet zeer groot.

Het Help - menu

Uit het Help - menu kan de gebruiker een aantal onderwerpen kiezen waarover hij uitleg wil. Op de onderwerpen die daarin aan bod komen, zullen we hier niet ingaan. Het is grotendeels hetzelfde als hetgeen hier besproken staat, doch in een aangepaste versie. Het gehele programma is geschreven in het Engels evenals de Help (Engels is nu eenmaal de meest gebruikte taal in de computerwereld en dus konden wij het niet laten).

Moeilijkheden tijdens de implementatiefase

Een belangrijke moeilijkheid bij het samen ontwerpen van programma's is het werk verdelen. Iedereen werkt aan een bepaald onderdeel van het programma en die onderdelen moeten dan samen een werkend programma vormen. Dit geldt vooral voor de samenwerking tussen Tcl/Tk en Prolog : het Prolog-programma roept procedures van Tcl/Tk aan om een puzzel te tekenen, daarbij is het natuurlijk belangrijk dat de juiste procedure met de juiste parameters aangeroepen wordt.

Een ander probleem is dat het programma redelijk traag is. Dat is gedeeltelijk verbeterd. Bij het inladen van een puzzel moeten nog steeds veel tijdrovende berekeningen uitgevoerd worden voor de 3D-projectie. Dit zou in feite nog meer geoptimaliseerd kunnen worden door die gegevens in het puzzel-bestand op te nemen.

Op een bepaald moment hadden we ook een probleem dat te wijten is aan het feit dat ons programma op twee systemen draait: Unix en Windows. De Windows-versie gebruikt namelijk een bibliotheek van functies (een Dynamic Link Library) voor de communicatie tussen het Prolog- en het Tcl/Tk-programma. De Unix-versie gebruikt ook zo'n bibliotheek, maar die twee bibliotheken zijn niet volledig compatibel. Zodus moesten we onze programma's aanpassen zodat we een lichtjes gewijzigde versie draaien op de Unix-computers.

Experimenten

Vier op een rij

Download page voor 'Vier op een rij'.

Om in de voor ons nieuwe programmeertaal te leren werken, beginnen we met een klein programmaatje: vier op een rij. Onze begeleider implementeert een algoritme in Prolog, dat 'denkt' en reageert op zetten van een menselijke speler. De opdracht is nu ervoor te zorgen dat de speler een mooi scherm krijgt waarop het spelbord staat afgebeeld. Hij moet kunnen aanduiden op welke positie hij een zet wil doen en moet ook de tegenzet van de computer kunnen zien. Wanneer we aan dit programma beginnen, zijn er drie grote stukken te onderscheiden:

de grafische weergave van een bord met schijfjes
de menubalk met de eraan gekoppelde functies
de verbinding met Prolog

De grafische weergave van een bord met de schijfjes

Zoals vooraf gezegd is Tcl/Tk een grafisch-gerichte programmeertaal waarin we kunnen werken met frames. Er wordt zo één frame gemaakt voor het bord. Hier plaatsen we de verschillende buttons en een canvas op. Een canvas is een soort vlak waar we grafische objecten (de schijfjes) op kunnen voorstellen. In Tcl/Tk is het in het algemeen mogelijk om aan ieder object een bepaalde functie toe te kennen. Je kunt er bijvoorbeeld voor zorgen dat een bepaald schijfje rood wordt wanneer er met de linkermuisknop op wordt gedrukt. Zo kunnen we eender welke procedure toekennen aan eender welk object.

De menubalk met de eraan gekoppelde functies

In de menubalk kunnen we weer hetzelfde principe toepassen. Wanneer een bepaald menu aangeklikt wordt, moet een bepaalde functie uitgevoerd worden. Wij hebben bij de implementatie gekozen voor popup-menu's. De popup-menu's bevatten o.a. de commando's om een spelbord op te slaan en in te laden.

De verbinding met Prolog

Telkens wanneer de computer een zet moet doen, stuurt het Tcl/Tk programma het hele spelbord door naar Prolog en vraagt het Prolog-algoritme om een zet. Deze zet wordt dan weer teruggestuurd zodat Tcl/Tk het spelbord kan aanpassen. Bij de implementatie moet men er wel nog voor zorgen dat het spelbordformaat van Tcl/Tk geconverteerd wordt naar het spelbordformaat van Prolog.

Tijdsmetingen

Als volgend experiment deden we enkele tijdsmetingen. Uit het visualisatiegedeelte leerden we dat er meestal verschillende oplossingsstrategieën voor eenzelfde probleem zijn. We voelden hier reeds intuïtief aan welke strategie het meest intelligent was. Dit kwantitatief uitdrukken kunnen we doen door alle algoritmes éénzelfde puzzel te laten oplossen en de tijd die ze elk hiervoor nodig hebben in een grafiek uit te zetten. Omdat de resultaten nogal ver uit elkaar liggen gebruikten we voor de naïve algoritmes de volgende eenvoudige puzzel op een 4x4 veld:

Voor de snellere algoritmes gebruikten we een moeilijkere opgave. De gevonden waarden kunnen dus niet rechtstreeks vergeleken worden. Ze geven echter duidelijk weer dat er grote verschillen in uitvoeringstijd bestaan tussen de verschillende algoritmes. Hieruit blijkt dat niet enkel correctheid, maar zeker ook snelheid een rol speelt bij de keuze van een algoritme.
Wat we ook nog willen opmerken is dat de snelheid van de computer en de versie van de programmeertaal (Prolog) zelf hier een zeer grote rol spelen. Daarom hebben we gekozen voor een relatieve, vergelijkende tijdsmeting.

Besluit

De opdracht van ons projectwerk is de visualisatie van combinatorische zoekalgoritmes.
Deze algoritmes zoeken de oplossing van combinatorische problemen. Wij kozen als combinatorisch probleem een vlakke puzzel. Elk puzzelstukje zal hierbij worden opgebouwd uit één laag kubusjes.
De bedoeling is verschillende versies van het combinatorisch algoritme op de puzzel los te laten. Door onze grafische visualisatie op het puzzelbord kan de gebruiker de verschillen tussen en de voor- of nadelen van de verschillende algoritmes evalueren.
Naar ons inziens is de uiteindelijke realisatie redelijk geslaagd.
Verder zal de praktijk moeten uitwijzen of de visualisatie duidelijk is en of ons doel bereikt is: het begrijpbaar voorstellen van combinatorische zoekalgoritmes.

Dankwoord

Graag zouden wij de faculteit willen danken voor het invoeren van het vak 'Projectwerk'. We vonden het zeer boeiend en leerzaam, vooral omwille van het praktische accent. Ook willen wij een dankwoord aan onze begeleider Lic. Vandecasteele Henk richten. We vonden de door hem gestelde opdracht heel interessant. Ook de begeleiding en samenwerking verliep prima.

Home