Fun
Dateiversion:
diesen Beitrag diskutieren,
ergänzen, eine Frage stellen
Menü einblenden
 

Kannibalen und Missionare

Transportproblem (Spiel)

 

Dieses Problem wurde 1982 als Testaufgabe von Prof. Krause formuliert...
es gilt als eines der klassischen Logik-Probleme und findet auch in der Psychologie Anwendung

5 Kannibalen und 5 Missionare befinden sich am Ufer eines Flusses. Um zur anderen Seite zu gelangen steht ihnen ein Boot zur Verfügung. Das Boot bietet Platz für maximal 2 Personen. Die Missionare werden von den Kannibalen gefressen, sobald sie an einem der beiden Ufer in der Minderheit sind. Das Boot kann nicht allein fahren und muss immer mit mindestens einer Person besetzt sein.

Bringen sie beide Parteien in möglichst wenig Schritten an das andere Ufer ohne das einer der Missionare verfrühstückt wird.

TIPP: um auf den "Dreh" zu kommen, versuchen sie zunächst das gleiche Problem für 2 Kannibalen und 2 Missionare bei einem Boot mit 2 Sitzen. Sie können beliebig viele Szenarien schaffen, wenn sie die Anzahl der Personen und die Zahl der Plätze im Boot verändern. Sobald sie wissen wie's geht, können sie das Spiel auch für 6 Personen und ein Boot mit 3 Plätzen versuchen.

* INFORMATIK: dieses Problem wird in der Informatik gern als Übungsaufgabe für Prolog gestellt (was einfach ist) oder als Aufgabe zum Finden eines Lösungsalgorithmus (was nicht so einfach ist). Beachten sie im 2. Fall, dass sich für den naiven Ansatz des Lösungsalgorithmus zum Finden einer idealen Lösung, eine Kaskade der Aufrufe ergeben kann. Versuchen sie eine geschickte Approximation. Lesen sie dazu zum Beispiel in der Literatur unter dem Stichwort "evolutionäre Algorithmen", wie sie einen Spielzug bewerten und annehmen bzw. ablehnen können, ohne alle nachfolgenden Züge ausführen zu müssen. Achten sie außerdem darauf, dass möglicherweise Schleifen von Spielzügen entstehen können, die eliminiert werden müssen. Hinweis: dieses Problem ist den bekannten "Türmen von Hanoi" sehr ähnlich. Möglicherweise finden sie hier einen geeigneten Ansatz. Das serielle Optimum des gesuchten Algorithmus liegt (vermutlich) bei O(log n).