Hasen, Füchse und Logikbäume

Lösung mittels Logikbaum

Was genau ist nun ein Logikbaum (Entscheidungsbaum) und wie kann man damit die vorliegende Fragestellung beantworten?

Logikbäume gibt es in verschiedenen Anwendungsformen. Sie bieten aber immer die Möglichkeit, die Komplexität einer Frage zu reduzieren und sie in „einfachere“ Teilfragen aufzusplitten.
Die Aufteilung der Fragestellung in ihre einzelnen Bestandteile erlaubt es, die Situation mit ihren verschiedenen Ästen zu visualisieren und zu strukturieren. Das Problem wird damit greifbarer.
D.h. es kann Schritt für Schritt geprüft werden, welche Auswahlmöglichkeiten zu jedem gegeben Zeitpunkt vorliegen und welche davon am zielführendsten sind. In diesem Zusammenhang können Logikbäume auch zur Optimierung eingesetzt werden.

Für unser vorliegendes Beispiel bedeutet dies.

Bei der ersten Überfahrt können wir zwischen fünf Möglichkeiten wählen. Einen Fuchs oder einen Hasen alleine loszuschicken, wäre nicht zielführend, da es jemanden braucht, der das Floß nach dem ersten Turn zurückfährt. Die Variante mit zwei Hasen über den Fluss zu fahren, würde zum frühen Ableben des verbleibenden Hasen führen. So sind noch zwei Optionen übrig. Entweder fahren zwei Füchse oder jeweils ein Hase und ein Fuchs los. Beides kann zu einer effizienten Lösung in elf Zügen führen. Um Zeit zu sparen, sehen wir uns die Lösung mit einem Hasen und einem Fuchs an. 1. H+F rüber Die Lösung für zwei Füchse finden sie am Ende des Beitrags.

Nun stehen uns zwei Wege offen. Entweder fährt der Hase oder der Fuchs zurück. Fährt der Fuchs zurück, heißt es auf der anderen Seite – drei Füchse zu zwei Hasen – was wieder zu einem vorzeitigen Ende führen würde. So folgt 2. H zurück.

Ein Fuchs ist nun auf der sicheren Seite und auf der anderen Seite sind zwei Füchse und drei Hasen. Fahren zwei Hasen, stirbt der zurückbleibende Hase. Fährt ein Hase und ein Fuchs, dann stirbt der fahrende Hase, sobald er drüben ankommt, da er dann alleine mit zwei Füchsen wäre. Somit bleibt nur die Möglichkeit, dass zwei Füchse den Fluss überqueren. 3. F+F rüber.

Nun muss einer der drei Füchse, das Boot zurückbringen. 4. F zurück.

Da auf der anderen Seite zwei Füchse warten, ist der einzig gangbare Weg, dass nun zwei Hasen auf die andere Seite fahren. 5. H+H rüber. Die anderen Alternativen würden wieder zum Umkommen eines Hasen führen.

Aktuell sind damit zwei Füchse und zwei Hasen auf der sicheren Seite. Wenn zwei Hasen zurückfahren, wäre dies nicht sinnvoll, da dies den vorherigen Schritt einfach wieder rückgängig machen würde. Wenn zwei Füchse zurückfahren, würde dies das Ende des dort wartenden Hasen bedeuten. Nur ein Tier zu schicken, hätte ebenfalls das Ende eines Hasen zur Folge. Der einzige mögliche Weg ist, dass ein Hase und ein Fuchs zurückfahren. 6. H+F zurück.

Falls nun ein Tier alleine fahren würde, hätte dies wieder das Ende eines Hasen zur Folge. Einen Hasen und einen Fuchs loszuschicken, hat keinen Zweck, da dies wieder den vorherigen Zug negieren würde. Wenn zwei Füchse aufbrechen, wäre dies für den Hasen auf der anderen Seite lebensgefährlich. So ist es nur zielführend, dass nun zwei Hasen über den Fluss fahren. 7. H+H rüber.

Nun ist es fast geschafft, es geht in den folgenden Schritten nur noch darum, dass der Fuchs, der bereits auf der sicheren Seite steht, seine beiden Kumpel nachholt. 8. F zurück 9. F+F rüber 10. F zurück 11. F+F rüber.

Alle Tiere haben nun sicher das andere Ufer erreicht und werden nun wohl getrennte Wege gehen. Die Anwendung des Logikbaumes hat es uns erlaubt, systematisch die Komplexität der Fragestellung zu reduzieren, ihr eine Struktur zu geben und die einzelnen Bestandteile fassbar zu machen. Logikbäume können auch in verschiedenen anderen Bereichen wie Kostenrechnung, Prozessplanung, Kundenklassifikationen, maschinellem Lernen, … etc. eine wertvolle Anwendung finden.

Abschließend finden sie hier noch die Lösung, falls man beim ersten Zug mit zwei Füchsen startet. 1. F+F rüber, 2. F zurück, 3. F+F rüber, 4. F zurück, 5. H+H rüber, 6. H+F zurück, 7. H+H rüber, 8. F zurück, 9. F+F rüber, 10. F zurück, 11 F+F rüber.