vorige nächste Programm Programm

Beispiele


Missionare und Eingeborene

Zu dem Problem der Missionare und Eingeborenen gibt es viele Lösungen mit verschiedenen Methoden im www zu finden. Beachten Sie aber, dass dieses Problem auch ohne Probleme mit einem der vollständigen Suchverfahren gelöst werden kann.

Das hier angegebene, zweite Beispiel zum A*-Algorithmus stammt aus Oliver Grillmeyer: Exploring Computer Science with Scheme

Grillmeyer widmet sich in seinem Buch in einem umfangreichen Kapitel der "Artificial Intelligence" und darin den Suchproblemen. Eines der dort behandelten Probleme ist das Problem der "missionaries and cannibals", das er mit dem A* - Verfahren bearbeitet. Der etwas bearbeitete Programmcode ist hier mit angegeben.

Das Ergebnis eines Aufrufs:

(((3 3) left (0 0))
 ((2 2) right (1 1))
 ((3 2) left (0 1))
 ((3 0) right (0 3))
 ((3 1) left (0 2))
 ((1 1) right (2 2))
 ((2 2) left (1 1))
 ((0 2) right (3 1))
 ((0 3) left (3 0))
 ((0 1) right (3 2))
 ((1 1) left (2 2))
 ((0 0) right (3 3)))

ist -so hoffe ich- selbst erklärend.