Computational Thinking
Online Algorithmen[Was ist es wert, die Zukunft zu kennen?]
Kurt MehlhornKonstantinos Panagiotou
Der Weihnachtsmann konnte leider nicht kommen
Bisher…
• In allen Problemen, die wir gesehen haben, war die Eingabe immer vollständig spezifiziert– Sortieren– Kürzeste Wege, Eulertour, …– Kompression
Aber…
• Manchmal ist die Eingabe nicht im Voraus vollständig bekannt
• Entscheidungen müssen getroffen werden, ohne zu wissen „was kommt“
• Beispiele– Börse– Logistik (zB Post, Amazon)– Aufträge/Anfragen
Online Probleme/Algorithmen
• Daten werden schrittweise verfügbar• Es gibt keine Information über die zukünftigen
Daten• Die Daten müssen sofort verarbeitet werden• Entscheidungen, die getroffen werden, sind
nicht umkehrbar
Diskussion
• Das Modell ist recht restriktiv• In der Praxis sind oft einige Informationen
bekannt– Finanzwelt: Annahmen über Kursverläufe– Logistik: Verteilung der Aufträge
• Solches Wissen kann im Modell berücksichtigt werden
Bin Packing
Beispiel
• Im Bin Packing geht es darum, Gegenstände in Behälter (= Bins) unterzubringen
• Man möchte so wenig Bins wie möglich verwenden
• Schneiden von Teilen• Spedition
Das Problem
• Eine vereinfachte Annahme
• BinPacking– Eingabe: n Objekte mit Größen – Ausgabe: Eine Packung der Objekte in Bins der Größe 1
• Online: die Größen werden eine nach der anderen aufgedeckt, und der Gegenstand muss sofort in einen Bin platziert werden.
Ein einfacher Algorithmus
NextFit• Es gibt immer einen einzigen aktiven Bin• Falls das nächste Element in den aktiven Bin
passt, so wird es dort eingefügt• Sonst wird der Bin geschlossen, und ein neuer,
leerer Bin wird aktiv
• Geschlossene Bins werden nie wieder betrachtet
Beispiel
0.4 0.1 0.9 0.3 0.2
Ein besserer (?) Algorithmus
Warum sollten man Bins schließen?
FirstFit• Falls das nächste Element in irgendeinen Bin
passt, so wird es dort eingefügt• Ansonsten wird es in einen neuen, leeren Bin
eingefügt
Beispiel
0.4 0.1 0.9 0.3 0.2
Wie gut sind diese Algorithmen?
• Vergleich mit einem optimalen Algorithmus• Dieser Algorithmus kennt die Zukunft– Alle Größen sind im Voraus bekannt– Er berechnet die kleinste Anzahl Bins, die benötigt
werden
• Der kompetitive Faktor eines Algorithmus ALG ist definiert als
Beispiele (I)
• Alle Gegenstände sind groß
Beispiele (II)
• 8 Gegenstände mit Größe • 8 mit Größe
Die Reihenfolge ist wichtig!• Angenommen die Elemente kommen
abwechselnd
NextFit
FirstFit
FirstFit kann schlecht sein
• 0.15 + 0.34 + 0.51 = 1• Instanz: 6 x 0.15, 6 x 0.34, 6 x 0.51
Analyse von NextFit
• Nehmen wir an, NextFit hätte b Bins benutzt• Seien die Gewichte der Bins • Dann gilt:
• Außerdem gilt:
• Da aber in jedem Bin Gewicht höchstens 1 passt, folgt daraus
Geht es besser?
• Wie gut kann ein online Algorithmus sein?• Kann man einen Algorithmus angeben, der
immer die beste Lösung konstruiert?
• Nein!
Das Gegenbeispiel (I)
• Angenommen, wir haben Gegenstände mit Gewicht
• Optimale Lösung: Bins• Sei BinPac ein beliebiger Online Algorithmus
• Dann benutzt BinPac bins
• Also gilt:
Das Gegenbeispiel (II)
• Angenommen wir haben Gegenstände – haben Gewicht – haben Gewicht
• Optimale Lösung: Bins
• Was macht BinPac?• Die Bins können aufgefüllt werden.• Die restlichen Gegenstände benötigen nochmal
so viele Bins
ZusammenfassungInstanz I• mit Gewicht
• Optimal = • Bins:
Instanz II• mit Gewicht mit Gewicht • Optimal = • Bins:
Also…
• … kann es keinen online Algorithmus geben, der einen kompetitiven Faktor kleiner als hat!
• FirstFit: der Faktor ist 1.7.• Übrigens: BinPacking ist NP-vollständig!
Scheduling
Scheduling
• Gegeben sind– Maschinen– Jobs
• Beispiele– Fabriken und Aufträge– Aufzüge und Menschen
Problemformulierung• Maschinen• Jobs, mit Bearbeitungszeiten • Problem: minimiere die totale Bearbeitungszeit ( =
der Zeitpunkt, an dem alle Jobs abgearbeitet wurden)
• Online Problem– die Bearbeitungszeiten sind nicht alle zu Beginn bekannt– wird bekannt, sobald der te Job einer Maschine
zugeordnet wurde
Der Algorithmus
• Verteile die Jobs nach folgender Regel:„Job wird der Maschine zugeordnet, die
aktuell die geringste Last hat“
0.4 0.1 0.9 0.3 0.2
Wie gut ist der Algorithmus?
• Wie vorher: vergleiche die Leistung des Algorithmus mit einem optimalen Algorithmus, der alle Bearbeitungszeiten schon zu Beginn kennt
Die obere Schranke
𝑝𝑙
𝑡 𝑙 𝑇
Die untere Schranke
• Kann der Algorithmus wirklich so schlecht werden?
• Ja!• Instanz:– Jobs der Länge 1, ein Job der Länge – Die kurzen Jobs kommen zuerst
Experten
Das Problem
• Wir möchten eine Vorhersage machen– Wird es morgen regnen?– Wird der DAX steigen?
• Es gibt n Experten, die wir befragen können– Ja/Nein Antworten
• Am Ende des Tages erfahren wir, wer Recht hatte
• Wie können wir möglichst viele richtige Vorhersagen machen?
Eine Idee
• Jeder der Experten bekommt ein Gewicht:
– Zu Beginn sind alle Gewichte = 1– Gesamtgewicht =
• Wir fragen alle Experten, und bilden die Summe aller „Nein“-Sager und aller „Ja“-Sager
• Wir wählen die Antwort mit dem größeren Gewicht
Wie lernen wir?
• Am Ende des Tages werden die Gewichte angepasst
• Jeder, der eine falsche Prognose gemacht hat, wird „bestraft“: das Gewicht wird mit multipliziert
• Bei richtigen Prognosen passiert nichts.
Beispiel𝑤1𝑤2𝑤3𝑤4𝑤5
Tag 1Tag 2Tag 3Tag 4
Wie gut ist das?
• Wir vergleichen die Anzahl unserer richtigen Prognosen mit der des besten Experten
• Sei die Anzahl falscher Prognosen des ten Experten nach Tagen
• Sei die Anzahl unserer falscher Prognosen• Was können wir über die Relation dieser ‘s
sagen?
Eine allgemeine Schranke
• Sei das Gesamtgewicht am ten Tag• Dann ist• Angenommen, wir haben am Tag die falsche
Prognose gemacht• Dann ist das Gesamtgewicht der Experten die
falsch prognostiziert haben • Nach der Aktualisierung:
Also…
Andererseits
• Jedesmal wenn ein Experte einen Fehler macht, wird sein Gewicht mit mit multipliziert
• Somit
Zusammenfassung
• Online Probleme– Eingabe wird nach und nach bekannt gemacht– Entscheidungen können nicht rückgängig gemacht
werden• Kompetitiver Faktor