vorige Programm

Missionare und Kannibalen


Ein Anwendungsbeispiel für Tiefensuche mit backtracking

Bei der Anwendung der uninformierten vollständigen Suchverfahren Tiefensuche und Breitensuche ergibt sich in der Regel das Konzept des GT (Generate and Test).
Dabei werden zunächst im Suchgraphen (Baum) alle Möglichkeiten generiert. Der Unterschied zwischen Tiefensuche und Breitensuche besteht allein in der Frage der Reihenfolge, bei der Tiefensuche mit dem dabei in der Regel verwendeten backtracking kommt als weiterer Unterschied hinzu, dass jeweils nur der aktuelle Knoten weiter expandiert wird, so dass immer nur ein Pfad gehalten wird.
Sind die Wege vollständig generiert, befindet man sich im Baum also in einem Blatt ( wenn der Suchraum keinen Baum darstellt, lässt sich durch Einführen einer besucht-Liste daraus einer erzeugen ), dann wird dieses Blatt daraufhin getestet, ob es eine Lösung des Problems darstellt oder nicht.
Wir untersuchen dieses Konzept am Beispiel der Missionare und Kannibalen.

Beschreibung der Aufgabe:

Auf der einen Seite eines Flusses befinden sich drei Missionare und drei Kannibalen und Bwie das in solchen Fällen eben immer so istB ein Boot, das gerade einmal zwei Personen tragen kann. Sobald sich bei der Abfahrt des Bootes auf einer Seite mehr Kannibalen als Missionare befinden, wird die Kannibalen die Fresslust übermannen, sie werden sich auf die Missionare stürzen und sie verzehren. Der missionarische Eifer geht nun nicht so weit, dass die Missionare das akzeptieren und sie suchen daher nach einer Reihenfolge, die es ihnen ermöglicht den Fluss zu überqueren, ohne dass einer von ihnen gefressen wird.

GT (Generate and Test) bedeutet in diesem konkreten Fall, dass unter Beachtung der besucht - Liste solange generiert wird, bis alle Missionare und Kannibalen über den Fluss gekommen sind und dann die einschränkenden Bedingungen ( constraints ) getestet werden, hier also, ob einer der Zwischenzustände unzulässig war. Gerade bei diesem Beispiel merkt man sehr schnell, dass dies Vorgehen einen verschwenderischer Umgang mit der Problemlösezeit, bei der Breitensuche mit dem Speicher, darstellt. Da es in diesem Beispiel nicht darum geht, zu sehen, ob denn der Endzustand zulässig ist, der ist eigentlich in seinen Anforderungen trivial, sondern gerade die zu ihm führenden Zwischenzustände die "Qualität" der Lösung ausmachen, ist es nicht sinnvoll, das Testen der Bedingungen erst am Schluss durchzuführen. Schon während des Generierens lässt sich prüfen, ob der aktuelle Zustand zulässig ist. Stellt man nun fest, dass dieser aktuelle Zustand unzulässig ist, dann schneidet man nun schon beim Generieren die Teile des eigentlich dort zu generierenden Graphen ab, da nun schon bekannt ist, dass sie nicht zu einer Lösung führen können. Dieses modifizierte Verfahren bezeichnet man als hierarchisches Generate und Test. Es führt in der Regel zu einer deutlichen Verbesserung des Verfahrens, macht in vielen Fällen so erst eine Lösung real möglich. Beachten Sie aber, dass es nicht bei allen Problemen anwendbar ist, da es auch Probleme gibt, bei denen die Qualität eines Pfades erst geprüft werden kann, wenn er vollständig vorliegt, wenn man also in einem Blatt des Suchraumes angekommen ist.

Zur Lösung im Fall der drei Missionare und drei Kannibalen noch einige Vorbemerkungen:

Bei der vorgegebenen Problemstellung muss vor und nach einem Transport die Summe der Missionare und der Kannibalen beider Seiten jeweils konstant 3 sein, so dass nur eine Seite verwaltet werden muss.

Es werden beim Generieren der Nachfolger zunächst alle Zustände generiert und dann die unzulässigen aussortiert. Dies geschieht in den Funktionen links-OK und rechts-OK. Das eigentliche Suchverfahren ist eine vollständige Tiefensuche mit backtracking und Verwaltung eeiner besucht - Liste.

 


Anmerkung 1: Varianten des Problems

Es gibt hier bei der Problemstellung zwei verschiedene Varianten. Die "strenge" Forderung ist, dass auf jeder Seite zu jeder Zeit die Zahl Missionare größer oder gleich der Zahl der Kannibalen sein muss. Die schärfere Forderung führt zu einer deutlich geringeren Zahl von Lösungen, fast geht sogar der Charakter eines Suchproblems verloren.

Anmerkung 2: suboptimale

In vielen Fällen wird einer der Kannibalen als ein Fährmann bezeichnet. Da er sich in seiner "Fress - Funktion" nicht von den anderen unterscheidet, ist das für die Lösung der ersten Variante belanglos.