Algemeen
Deze opdracht bestaat uit twee delen, die beide gaan over breadth-first en depth-first search.
In het eerste deel zijn de functies die uit een toestand de nieuwe toestanden maken gegeven, en is het de bedoeling dat je een bfs en dfs zoekalgoritme schrijft/programmeert. Dit moet met een zgn. queueing-function (ook bij dfs).
In het tweede deel kun je dan de zoekalgoritmen uit deel 1 gebruiken in een ander probleem, waarbij je zelf de code moet schrijven die nieuwe toestanden berekent.
Voor opdracht 1 zullen we het water jug probleem gebruiken. Het probleem is als volgt. Je hebt twee kannen, één 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. Doel is om in de grote kan 2 liter water te krijgen. Dit kan door kannen te vullen en water over te gieten van de ene naar de andere kan, of door kannen weer leeg te gooien.
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.
De delen van het programma die gegeven zijn bevatten een functie die testen of het doel bereikt is, en een functie die gegeven een toestand een lijst toestanden oplevert die daar van uit bereikbaar zijn. Probeer in je oplossing voor dfs en bfs alleen van deze functie's gebruik te maken, zodat ze ook voor hele andere probleemruimten inzetbaar zijn.
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.
Bij de tweede opdracht is het de bedoeling om juist de functies te schrijven die bepalen welke toestanden bereikt kunnen worden vanuite een bepaalde toestand, en om te testen of het doel bereikt is. Het probleem is in dit geval het missionarissen en kannibalen probleem, dat in het boek op blz. 67-68 wordt beschreven.
Opdracht is dus, om met functie die je al voor de eerste opdracht geschreven hebt deze puzzel met dfs en bfs op te lossen, en hierbij dezelfde informatie af te drukken als bij de eerste opdracht.
De code van beide programma's en een klein verslagje moeten ingeleverd worden. Als je het mailt naar Freek (freeks@tcw3.ppsw.rug.nl ), dan graag alle drie de onderdelen als attachment. Papieren versies kunnen ingeleverd worden in Freek's postvakje bij het secretariaat. Bovenaan elk onderdeel graag namen + studentnummers vermelden.
Het verslagje kan, zeker als je voldoende commentaar aan de code hebt toegevoegd, bondig blijven. In dit verslag moet een algemene omschrijving van het probleem en het programma gegeven worden. Geef in het verslag ook voorbeelden van uitvoer van de programma's.