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

Ähnliche Inhalte

Hier findest Du weitere Inhalte zu dem von Dir gewählten Thema. Bei diesen Vorschlägen handelt es sich um eine Auswahl an Inhalten, welche wir insgesamt für Dich auf der LeanBase zur Verfügung stellen.

Wertstrom Engineering: Typen- und variantenreiche Produktion

Wertstrom Engineering: Typen- und variantenreiche Produktion

Buch auf LeanBooks
Kategorie: Wertstrommanagement

von Wolfgang Schweizer

In eigener Sache - LeanDigitalConference

In eigener Sache - LeanDigitalConference

Beitrag auf LeanPublishing
am 16. 04. 2020 um 04:30 Uhr
Kanal: LeanMagazin

Wir hoffen, es geht Euch gut und die Auswirkungen der aktuellen Situation sind für Euch einigermaßen erträglich.Wir nutzen die Zeit, um Ideen umzusetzen, welche wir ursprünglich für einen späteren...

Falsche Ziele führen in die falsche Richtung

Falsche Ziele führen in die falsche Richtung

Beitrag auf LeanPublishing
am 28. 12. 2020 um 04:30 Uhr
Kanal: LeanMagazin

Viele Unternehmen werden den Anschluss an die Zukunft allein deshalb verpassen, weil sie in überholten Zielfindungsprozessen verharren. Vor allem die Kurzfristfalle gefährdet das Überleben am Markt.

Respekt: Die Geschichte einer gelebten Lean-Kultur

Respekt: Die Geschichte einer gelebten Lean-Kultur

Buch auf LeanBooks
Kategorie: Allgemein

von Freddy Balle & Michael Balle

Durchlaufzeit

Eintrag im LeanLexicon
Wie Dr. Nemo die Selbstreflexion versteht - Folge 65

Wie Dr. Nemo die Selbstreflexion versteht - Folge 65

Podcast auf LeanPublishing
am 10. 06. 2018 um 16:40 Uhr
Kanal: Interview mit Dr. h.c. Any Nemo

„Wo waren wir nochmal vor der Urlaubspause stehengeblieben?“, fragte der Interviewer Elvira, die ihn lächelnd und mit sanftem, fast unauffällig gebräuntem Teint empfing....

#019 | Autonomie und Bindung

#019 | Autonomie und Bindung

Podcast auf LeanPublishing
am 23. 05. 2019 um 05:30 Uhr
Kanal: LeanMagazin

Warum wir selbstbestimmte Arbeit brauchen. Menschen streben in ihrem Leben nach einer Balance aus Autonomie und Bindung. Arbeitgeber zerstören diese Balance, indem sie vorwiegend auf Bindung...

Das richtige Werkzeug für den Job - Teil 2

Das richtige Werkzeug für den Job - Teil 2

Beitrag auf LeanPublishing
am 10. 05. 2021 um 04:30 Uhr
Kanal: LeanMagazin

Im ersten Teil hat Peter Rubarth, Senior Agil Coach bei der solarisBank AG das Cynefin Framework vorgestellt. In diesem 2. Teil geht er darauf ein wie das Cynefin Framework helfen kann, die...