Weihnachtsmann rot

Aufgabe vom 8. Dezember

Schicht im Schacht

Autoren: Jan Hackfeld, Julie Meißner, Miriam Schlöter

Projekt: Design and Operation of Infrastructure Networks under Uncertainty; DFG SPP 1736 ”Algorithms for Big Data“

Aufgabe:

Einige Tage vor Weihnachten ist der Weihnachtsmann fast fertig, die Geschenkeauslieferungstour für den diesjährigen 24. Dezember zu planen. Wie in jedem Jahr beginnt er auf den Fiji-Inseln und arbeitet sich dann durch alle Zeitzonen, um auf Hawaii die letzten Familien zu besuchen. Jetzt fehlt noch das letzte Hochhaus, in dem er drei Familien besuchen möchte.




Stockwerk



Familie Aloha 1. Stock



Familie Baako 6. Stock



Familie Calahan 9. Stock



Der Weihnachtsmann erklärt Rudolph: „Dieses Haus lässt meine weißen Haare grau werden! Ich habe den Zettel verloren, auf dem steht, wann die Familien jeweils zu den Großeltern fahren. Jetzt weiß ich nur noch, dass alle Familien zwischen 14.30 Uhr und 17.00 Uhr abfahren und, da sie den Bus nehmen, ihre Abfahrtszeit ein Vielfaches von 10 Minuten nach 14.30 Uhr ist.

Wir müssen auf einem Balkon im 5. Stock landen und von dort wieder abfliegen, denn nur dort gibt es einen Zugang über den Lüftungsschacht in alle Wohnungen. Der ist wiederum derart eng, dass ich ganze 5 Minuten brauche, um von einem Stockwerk in ein benachbartes zu kriechen. Mit welcher Strategie kann ich denn jetzt alle Geschenke verteilen ohne gesehen zu werden? Wir wollen doch auch noch am hawaiianischen Strand Weihnachten feiern.“

„Mhmm...“, überlegt Rudolph. Doch nach einiger Zeit beginnt seine Nase zu leuchten und er schlägt vor: „Also, du brauchst 5 Minuten um im Schacht ein Stockwerk zu kriechen, die Geschenke kannst du bei den Familien blitzschnell unter den Baum legen, sodass wir die Zeit dafür vernachlässigen können. Außerdem hörst du, egal wo du im Schacht bist, wann sich welche der drei Familien auf den Weg macht, was nur alle 10 Minuten der Fall sein kann. In dem Moment, in dem die Familie die Wohnung verlässt, kannst du die Geschenke in die Wohnung bringen ohne entdeckt zu werden. Allerdings hast du diese Information nicht vorweg, da du deinen Zettel verloren hast und musst daher schon Entscheidungen treffen, bevor dir alle Informationen vorliegen. Wir brauchen also eine Strategie-ohne-Vorwissen, die darauf reagiert, wann die Familien abfahren.

Um zu entscheiden, wie gut unsere Strategie-ohne-Vorwissen ist, können wir uns mit der Zeit vergleichen, um die wir abfliegen können, wenn du deinen Zettel nicht verloren hättest und du alle Abfahrtszeiten der Familien kennen würdest. In diesem Fall können wir eine optimale Strategie-mit-Vorwissen angeben, die bei gegebenen Abfahrtszeiten angibt, wie du durch den Schacht kriechen solltest, damit du möglichst schnell mit dem Verteilen der Geschenke fertig bist. Die Zeit, die wir bei einer Strategie-ohne-Vorwissen später abfliegen können als bei der Strategie-mit-Vorwissen, soll dabei selbst im ungünstigsten Fall möglichst gering sein.“

Der Weihnachtsmann und Rudoph machen eine Reihe von Beobachtungen über eine optimale Strategie-ohne-Vorwissen. Bei welcher der folgenden Aussagen haben sie einen Fehler gemacht?

Die Aufgabe als PDF runterladen (flagge nl NL Download)

Antwortmöglichkeiten:
(Lösung als PDF herunterladen)

  1. Es reicht aus, um 14.30 Uhr auf dem Balkon im 5. Stock zu landen.

  2. Wenn die Familien Aloha und Baako als erste zeitgleich das Haus verlassen, darf der Weihnachtsmann nicht sofort in den 6. Stock kriechen.

  3. Selbst wenn Familie Baako mindestens 50 Minuten nach Familie Aloha und Familie Calahan abfährt, ist der Weihnachtsmann mit jeder optimalen Strategie-ohne-Vorwissen im ungünstigsten Fall 20 Minuten später fertig als mit einer optimalen Strategie-mit-Vorwissen.

  4. Es gibt eine optimale Strategie-ohne-Vorwissen, die in dem Fall, dass die Familien die Wohnungen erst um 17.00 Uhr gleichzeitig verlassen, zur gleichen Zeit fertig ist wie jede optimale Strategie-mit-Vorwissen.

  5. Wenn vor 15.00 Uhr noch keine Familie abgefahren ist, muss sich der Weihnachtsmann um 15.00 immer noch im 5. Stock befinden.

  6. Es gibt eine Strategie-ohne-Vorwissen, mit der der Weihnachtsmann höchstens 20 Minuten später als mit jeder optimalen Strategie-mit-Vorwissen abfliegt.

  7. Wenn der Weihnachtsmann die Geschenke bisher ausschließlich im 9. Stock schon verteilt hat, darf er anschließend nicht im 6. Stock darauf warten, dass Familie Baako oder Familie Aloha ihre Wohnung verlassen.

  8. Egal wann die Familien genau ihre Wohnungen verlassen, kann der Weihnachtsmann bis spätestens 18.00 Uhr vom 5. Stock abfliegen.

  9. Es existiert eine optimale Strategie-ohne-Vorwissen, mit der der Weihnachtsmann zur gleichen Zeit abfliegt wie in einer optimalen Strategie-mit-Vorwissen, falls Familie Aloha mindestens 60 Minuten nach Familie Calahan die Wohnung verlässt.

  10. Wenn Familie Aloha 60 Minuten vor Familie Calahan abfährt, dann kann der Weihnachtsmann bis spätestens 17.20 Uhr abfliegen.

Sie müssen sich einloggen um die Aufgaben abgeben zu können.

Projektbezug:
In der Diskreten Optimierung beschäftigen wir uns mit Techniken, mit denen man aus einer sehr großen, aber meist endlichen Menge möglicher Lösungen eine optimale Lösung finden kann. Diese Weihnachtskalender-Aufgabe lässt sich noch gut mit einem Blatt Papier und einem Stift lösen. Wenn die Anzahl der Stockwerke und Familien aber deutlich größer wäre, ließe sich ein solches Problem nur noch mit geeigneten Algorithmen auf einem Computer lösen. Eine besondere Herausforderung dabei ist, dass der Weihnachtsmann in dieser Aufgabe Entscheidungen treffen muss, ohne dass ihm bereits die vollständigen Informationen über alle Abfahrtszeiten vorliegen. Das Teilgebiet der Diskreten Optimierung, das sich mit Problemen dieser Art beschäftigt, nennt man Online-Optimierung und was wir in dieser Aufgabe eine Strategie-ohne-Vorwissen genannt haben, nennt man üblicherweise einen Online-Algorithmus. In der Online-Optimierung suchen wir nach möglichst guten Algorithmen für Probleme, bei denen man mit Teilinformationen schon Entscheidungen treffen muss, die sich auf die Qualität der kompletten Lösung auswirken. In einem Projekt, das uns zu dieser Aufgabe inspiriert hat, haben wir uns mit Algorithmen beschäftigt, um zum Beispiel einen Industriefahrstuhl zu steuern, der verschiedene Produkte in ein hohes Regal einsortiert.