© Julia Nurit Schönnagel, MATH+
Autor*in: Svenja M. Griesbach
Projekt: Information Design for Bayesian Networks (AA3-9)
Aufgabe
Um sich für den 24. Dezember fit zu machen, war der Weihnachtsmann ein paar Tage in den Bergen wandern. Als er an der Haupthütte mit der roten Tür angekommen ist, fällt ihm jedoch auf, dass er in einer der kleineren Hütten ein paar Wunschzettel verbummelt hat. Diese muss er natürlich schnell wiederfinden. Leider weiß er nicht mehr genau, in welcher der sechs Hütten er die Wunschzettel vergessen hat; er weiß nur, dass sie auf jeden Fall in einer der Hütten liegen müssen. Da der Weihnachtsmann während seiner Wanderung nicht in allen Hütten pausiert hat, kann er immerhin zwei der sechs Hütten ausschließen. Bei den anderen vier Hütten kann er wenigstens die Wahrscheinlichkeit angeben, mit der die Wunschzettel dort jeweils liegen.
Der Weihnachtsmann ruft umgehend Rudolf mit seinem superschnellen Schlitten zu Hilfe, denn er hat keine Zeit zu verlieren. Als die beiden sich gerade auf die Socken machen wollen, sehen sie, dass hoher Schnee die Pisten blockiert. Die Pisten müssen also zunächst geräumt werden, bevor sie mit dem Schlitten befahren werden können. Dafür steht nur ein einziges magisches Räumfahrzeug zur Verfügung, dass die Pisten nacheinander, allerdings in völlig beliebiger Reihenfolge räumen kann. Zusätzlich zur Räumung der einzelnen Pisten vergeht also keine Zeit. Auf seiner Landkarte (s. Abb. 1) kann der Weihnachtsmann ablesen, wie lange es jeweils dauert, die Pisten zu räumen. Sobald eine Piste vom hohen Schnee befreit ist, können der Weihnachtsmann und Rudolf in ihrem blitzschnellen Schlitten von einem Ende dieser Piste zum anderen düsen, ohne Zeit zu verlieren.
Die beiden starten in der Haupthütte mit der roten Tür. Sobald der Weihnachtsmann die Wunschzettel in einer der Hütten gefunden hat, brechen sie die Suche und auch die Räumung der Pisten ab.
In welcher Reihenfolge sollte der Weihnachtsmann die Pisten räumen lassen, damit er die Wunschzettel im Durchschnitt möglichst schnell findet?
Abbildung 1: Die Landkarte des Weihnachtsmanns. Eingezeichnet sind die Haupthütte mit der roten Tür, die umgebenen Hütten (jeweils mit der Wahrscheinlichkeit, mit welcher die Wunschzettel dort liegen) sowie die Pisten (mit der jeweiligen Räumungsdauer) zwischen den Hütten.
Antwortmöglichkeiten:
- blau, pink, rot, grün, lila
- blau, pink, lila, rot, grün
- blau, lila, schwarz, grün, pink
- blau, lila, pink, rot, grün
- blau, rot, lila, grün, pink
- rot, grün, orange, gelb, blau, lila
- rot, blau, lila, pink, grün
- rot, blau, pink, lila, grün
- rot, orange, gelb, grün, blau, lila
- rot, orange, gelb, blau, lila, schwarz
Projektbezug:
Das mathematische Problem hinter diesem Rätsel nennt sich Expanding Search, dabei kann die Suche jederzeit an einem beliebigen zuvor erreichten Knotenpunkt eines Graphen fortgesetzt werden.
Im Projekt AA 3-9 Information Design for Bayesian Networks betrachten wir ganz ähnliche Netzwerke wie die Landkarte des Weihnachtsmanns: Bayes’sche Netzwerke sind gerichtete Graphen, die aus gewichteten Kanten (hier die Pisten mit der Räumungsdauer) und Knoten (die Hütten) mit einer bedingten Wahrscheinlichkeitsverteilung (repräsentiert durch die Verlustwahrscheinlichkeiten) bestehen.