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).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.
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.
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.