Hasen, Füchse und Logikbäume

Hasen, Füchse und Logikbäume

Im folgenden Beitrag will ich eine mögliche Anwendungsform eines Logikbaums (Entscheidungsbaum) vorstellen, um ein Transport- und/oder Optimierungsproblem zu lösen. Beginnen möchte ich dazu mit einem kleinen Rätsel, welches dann als Anschauungsgegenstand dienen soll.

#leanmagazin
am 30. 01. 2020 um 05:30 Uhr in LeanMagazin von Thomas Zabrodsky


Vorstellung des Rätsels und Aufgabenstellung

In einem Wald ist ein Feuer ausgebrochen. Die Tiere fliehen vor den Flammen. Dabei bildet sich eine kleine Gruppe, die aus drei Hasen und drei Füchsen besteht. Gemeinsam erreichen sie einen großen Fluss, der ihnen den Weg abschneidet. Der Fluss ist zu breit und zu tief, als dass die Tiere hinüberschwimmen könnten. Während die Flamen näherkommen, entdecken sie ein kleines Floß, welches sie zur Flucht nutzen können. 

Unsere Aufgabe ist es nun, alle Tiere mit möglichst wenig Fahrten sicher auf die andere Uferseite zu bringen, wobei wir folgende Bedingungen beachten müssen.

  1. Es haben auf dem Floß max. zwei Tiere Platz. Das Floß kann aber nur fahren, wenn min. ein Tier an Bord ist, um es zu steuern. D.h. zum Beispiel nach der ersten Fahrt ans andere Ufer, muss auch ein Tier an Bord sein, um es zurückzubringen.
  2. Immer wenn die Hasen an einem Ufer in Unterzahl geraten – also zum Beispiel drei Füchse und zwei Hasen oder zwei Füchse und ein Hase – geht mit den Füchsen der Raubtierinstinkt durch, was das Ende für die jeweiligen Hasen bedeutet. Dies gilt auch, wenn zum Beispiel ein Hase am Ufer wartet und zwei Füchse mit dem Floß ankommen.
  3. Die Tiere können nicht hinüberschwimmen oder das Feuer mit dem Flusswasser löschen.

Ich würde vor dem Weiterlesen vorschlagen, sich vielleicht selbst kurz ein paar Gedanken zu machen, wie man die Tiere in möglichst wenig Zügen sicher auf die andere Seite bringen könnte.

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.


Kommentare

Bisher hat niemand einen Kommentar hinterlassen.

Kommentar schreiben

Melde Dich an, um einen Kommentar zu hinterlassen.

Teilen