De bedoeling van deze opdracht is dat je een 'generiek' zoekalgoritme implementeert dat in staat is om een boom te doorzoeken door middel van een breadth-first-search en een depth-first-search. In het tweede deel van de opdracht gebruik je deze functie op een nieuw probleem.
In het eerste deel is de successorfunctie (die bij een toestand de nieuwe opvolger-toestanden maakt) al gegeven. Het is de bedoeling dat je een bfs- en dfs-zoekalgoritme schrijft. Hiervoor maak je gebruik van lijsten met toestanden (queueing).
In het tweede deel kun je dan de zoekalgoritmen uit deel 1 gebruiken in een ander probleem. Het is de bedoeling dat je voor het nieuwe probleem zelf de successor-, goal- en initialisatiefuncties implementeert.
Het is de bedoeling dat we een zoekalgoritme schrijven aan de hand van een probleem. Ons voorbeeldprobleem is de klassieke 'waterjug'-puzzel:
Je hebt een kan van vier liter en één van drie liter. De kannen bevatten geen maatstrepen. Verder heb je een kraan waar je ongelimiteerd water uit kun tappen. Nu heb je, om onduidelijke redenen, 2 liter water nodig in de grote kan. Hiervoor heb je drie mogelijke operaties:
De opdracht is om een functie dfs en een functie bfs te schrijven, die als parameters de begintoestand en maximale zoekdiepte krijgen. Het programma moet de volgende informatie geven:
Een deel van het programma is al gegeven, en wel in een Lisp-, een Prolog- en een Pascal-versie:
Het volgende is al gegeven in deze bestanden: de goaltest, de initialisatie en de successorfunctie (die vanuit iedere staat de mogelijke nieuwe toestanden oplevert). In de pascal-versie is ook een handige functie gegeven voor het aan elkaar plakken van twee lijsten. Belangrijk: probeer in je oplossing voor dfs en bfs alleen van deze functies gebruik te maken. Het is namelijk de bedoeling dat je deze functie(s) bij de volgende opdracht opnieuw gebruikt, op een ander probleem.
Wat niet gegeven is, is een methode om het pad door de boom naar de huidige toestand bij te houden. Ook is er geen code om de huidige diepte in de boom te bepalen, of het aantal doorzochte knopen te tellen. Bedenk hiervoor zelf een oplossing. Het is mogelijk dat je hiervoor de gegeven code enigszins moet aanpassen.
Let er bij het schrijven van je programma op dat je nette, leesbare code schrijft. Zorg er ook voor dat je genoeg commentaar bij de code hebt staan. Code die onleesbaar is, zal niet worden geaccepteerd. Zie ook een paar aanwijzingen over stijl.
Omdat afgelopen dinsdag bleek dat de meeste studenten de cursus Voortgezet Programmeren niet gevolgd hebben, is besloten dat de opdracht nu toch wel in prolog gedaan kan worden. De beschikbare code staat hierboven. Je vindt hier nog wat info over sicstus prolog.
Het zoekalgoritme kun je het best baseren op figuur 3.10 uit het boek. Als je dit goed doet, hoef je maar 1 functie te schrijven, waarin dfs en bfs maar één statement van elkaar verschillen.
Houd verder in je programma rekening met het feit, dat je ook in een toestand kunt komen waar je al eerder in bent geweest, hetgeen uiteraard vermeden moet worden. Door op een slimme manier te 'snoeien' in je boom, is het mogelijk om veel efficienter te zoeken. Mijn eigen oplossing van het waterjug-probleem doorzoekt maar 18 knopen bij een zoekdiepte van 7 (dfs), en 9 bij een diepte van 9 (dfs).
Er is nu een werkende pascal compiler op linux. Zie hier.
In deze opdracht gebruik je de code uit deel a voor een ander probleem. Hiervoor herschrijf je de drie functies die je probleemruimte definieren, namelijk de goaltest, de initialisatie en de successorfunctie. Pas deze functies aan voor het 'missionarissen en kannibalen'-probleem, zoals dat in het boek op blz. 67-68 wordt beschreven.
Het is dus de bedoeling dat je een programma schrijft dat hetzelfde doet als dat in opdracht 1a, maar nu voor het missionarissen en kannibalen-probleem.
Lever het volgende in:
Vermeld bovenaan elk bestand/onderdeel je namen + studentnummers.
Laatst gewijzigd: donderdag 26 april 2001