Wiederholung

1 / 23

Online Algorithmen

• Eigenschaften von Online Algorithmen

• Unvollständige (Vorab-)Information• Sequentielle Anfragen• Abarbeitung der aktuellen Anfragen

ohne Information über zukünftige Anfragen

• Beispiele: Paging, Bin-Packing, Kürzeste Wege

• Definition: Ein Online Algorithmus ist eine Funktion A :

I∗ → O, die jeder Anfrage bzw. Anfragesequenz Σ ∈ I n auf

der Basis bekannter Informationen eine Antwort bzw.

Antwortsequenz Ω aus On+1 zuordnet. Die Kostenfunktion

c ordnet dem Paar (Σ,Ω) Kosten zu, die die Güte der

Lösung A(Σ) für das gegebene Online Problem P(I , O, c)bestimmen.

2 / 23

Online Algorithmen — Kompetitivität

• Kompetitivität( [engl.] to compete = wettstreiten )

• Idee Vergleiche die Kosten der Lösung A(Σ) mit den

Kosten der optimalen Lösung OPT (Σ) :

c(Σ, A(Σ))

c(Σ, OPT (Σ))

(OPT (P) = OPT (P ′) — Optimale Lösung entspricht

Offline Lösung.)

• Bestimme Worst Case Ratio

maxΣ∈Inc(Σ, A(Σ))

c(Σ, OPT (Σ))

• Ein Online Algorithmus A ist k-kompetitiv, wenn gilt:

∀Σ ∈ Inc(Σ, A(Σ)) ≤ k ∗ c(Σ, OPT (Σ)) + a

3 / 23

Online Kürzeste Wege Probleme

• Allgemeines Canadian Traveller Problem

Gegeben: Graph G = (V , E ), Startknoten s, Zielknoten t ,

Kostenfunktion c Beliebig viele Kanten können beliebig

lange blockiert sein.

Gesucht: Reisestrategie, die an Knoten v aufgrund der

aktuell bekannten Blockaden möglichst günstigen

nächsten Knoten ausgibt !

• Offline Lösung:

• Blockierte Kanten aus G löschen (G → G′)• Dijkstra’s Algorithmus auf G′

• Optimale, eindeutige Lösung

• Keine günstige Online Lösung ! (→ Zusatzannahmen)

4 / 23

Recoverable CTP

• Recoverable Canadian Traveller Problem

Gegeben: Graph G = (V , E ), Startknoten s, Zielknoten t ,

Kostenfunktion c, Recoverfunktion tr Beliebig viele Kanten

e ∈ E können für tr (e) blockiert sein.

Gesucht: Reisestrategie, die an Knoten v aufgrund der

aktuell bekannten Blockaden möglichst günstigen

nächsten Knoten ausgibt !

• Bedingungen an tr :

• tr (e) ≤ c(e′), für alle Kantenpaare (e, e′) → Bereist man

eine Kante, so sind alle zuvor festgestellten Blockaden

behoben, es sei denn, sie wurden erneut blockiert.• tr (v ) ≥ tr (e

′), für alle adjazenten Kanten → Wartet man an

einem Knoten tr (v ), so sind anschliessend alle Kantenwieder frei, es sei denn, sie wurden erneut blockiert.

• Immernoch keine günstige Online Lösung

5 / 23

Stochastisches Recoverable CTP

(srCTP)• Zusätzliche Information : Stauprognosen für bestimmte

Strassen

• Stochastisches Recoverable Canadian Traveller Problem

Gegeben: Graph G = (V , E ), Startknoten s, Zielknoten t ,

Kostenfunktion c, Recoverfunktion tr ,

Blockadewahrscheinlickeit p Beliebig viele Kanten e ∈ E

können mit Wahrscheinlichkeit p(e) für tr (e) blockiert sein.

Gesucht: Reisestrategie, die an Knoten v aufgrund der

aktuell bekannten Blockaden möglichst günstigen

nächsten Knoten ausgibt !

• Lösungsidee: Dijkstra-ähnlicher Algorithmus mit neuer

Kostenfunktion und mehreren alternativen Kanten an

jedem Knoten v .

• Neue Kostenfunktion Erwartete Reisezeit E (v , t ) von

Knoten v nach Zielknoten t6 / 23

srCTP — Algorithmus, Idee

• Beginne bei Zielknoten t mit E (t , t ) = 0, PL(t ) = ∅

• Setze für v 6= t ∈ V E (v , t ) = ∞, PL(t ) = ∅

• Suche u ∈ V mit minimaler E (u, t )• Füge jede Kante (u, ui ) in PL(ui ) ein• Sortiere PL(ui ) nach c(u, ui ) + E(u)• Bestimme minimales E(ui , t ) aus neuer PL(ui )

7 / 23

srCTP — Prioritätslisten

• Prioritätslisten PL(v ) verwalten die adjazenten Kanten zu

v geordnet nach Erwartete Reisezeit E (v , t )

• PL(v ) sind vorläufig, solange v nicht bearbeitet wurde

• PL(v ) gibt die Strategie an mit der ein Reisender von vausgehend den günstigsten Weg zu t bestimmt:

• Wähle 1. Kante in PL(v ), falls blockiert 2. Kante . . .

• PL(v ) verwaltet gleichzeitig einen Index i , so so dass diei−te Kante der Schleife (v , v ) entspricht.

• Wird (v , v ) gewählt, so wartete der Reisende an v .• Index i erziehlt die minimale E(v , t ).

8 / 23

srCTP — Minimale erwartete

Reisezeit E (v , t )

• Erwartete Reisezeit: Eh(x , t ) = αh+Phw (x ,xh)1−Ph

• mit:

• p(x , yi ) : Blockadewahrscheinlichkeit der zu x adjazenten

Kante (x , yi )• qi = 1 − pi : Wahrscheinlichkeit, dass Kante (x , yi ) nicht

blockiert ist• P0 = 1, Pi =

∏ij=1

pj : Wahrscheinlichkeit, dass alle zu xadjazenten Kanten (x , y1) bis (x , yi ) blockiert sind

• αi =∑

j=1Pj−1qj ((w (x , xj ) + E(xj ), t ):

Summe aller erwarteten Reisezeiten „für alle Fälle“ — 1.Kante ist blockiert, 1. und 2.Kante ist blockiert, . . .

• Finde Kantenindex h aus PL(x) so dass Eh(x , t ) minimal

unter allen Präfixen von PL(x).

9 / 23

srCTP-Algorithmus nach Bar-Noy

und Schieber

(1) setze

E (t , t ) := 0

PL(t ) := newPrior (t )

E (v , t ) := newETT (s, v ) für (s, v ) ∈ E

E (v , t ) := ∞ für (s, v ) /∈ E

PL(v ) := ∅

M = s

(2) bestimme u /∈ M mit E (u, t ) = minE (v , t ) : v /∈ M

(3) setze M = M ∪ u

(4) für alle v ∈ V mit (u, v ) ∈ E

(5) falls E (v , t ) > newETT(u, v ) setze

E (v , t ) = newETT(u, v )

PL(v ) := newPrior (u, v )

(6) falls M 6= V , gehe zu (2)

10 / 23

srCTP-Algorithmus - Tipp

• Wann sollte ein Reisender lieber an Knoten v tr (v )abwarten ?

• Die Option Abwarten muss in die Prioritätsliste PL(v )eingehen.

• Einfache Lösung:Vor Beginn des Algorithmus an jedem Knoten eine„Schleife“ einbauen, d.h.

• eine Kante e = (v , v ), v ∈ V mit• t (e) = tr (v ) zu G hinzufügen.

11 / 23

srCTP-Algorithmus — Laufzeit(1)

• (2) : Bestimmung des „minimalen“ Knoten u /∈ M

Implementierung mit FHeaps ⇒ O(logn)

• (2), . . . , (6) wird genau n = ‖V ‖ mal durchlaufen

n mal Minimumbestimmung ⇒ O(nlogn)

• (4), (5) : Aktualisierung von E (v , t ) und Prior (v )Trick und Lemma ⇒ O(logn)→ nächste Folie !

• (4), (5) wird insgesamt 2m = 2‖E‖ mal durchlaufen

m mal Aktualisierung ⇒ O(mlogn)

• Da i.A. m > n ⇒ Laufzeit: O(mlogn)

12 / 23

srCTP-Algorithmus — Laufzeit(2)

• Aktualisierungsschritt in O(logn):• Aktualisierung von Prior (v ) entspricht Einfügen in sortierte

Liste mit maximaler Länge n − 1 ∈ O(n), da ein Knotenmaximal zu allen übrigen der n Knoten adjazent sein kann.

⇒ O(logn) durch binäre Suche nach Einfügestelle• Aktualisierung von E(v , t ) entspricht Suche eines

Minimums in n − 1 ∈ O(n) Werten. Bar-Noy und Schieberzeigen:

• Falls E (v , t ) = Eh(v , t ), also Kantenindex h die minimale

erwartete Reisezeit bestimmt, so gilt für h als ersten Index:

αh + w (x , x)

1 − Ph

< w (x , xh+1)

• Dies gilt (mit entprechenden Indizes) ebenfalls für alle

größeren Kantenindizes in der sortierten Prioritätsliste.• ⇒ O(logn) für die Bestimmung des minimalen Index, der

obige Ungleichung erfüllt (mit binärer Suche) !

• Der gesamte Aktualisierungsschritt benötigt Zeit O(logn) !

13 / 23

srCTP-Algorithmus — Korrektheit,

Güte

• Der srCTP-Algorithmus berechnet für jeden Knoten die

minimal erwartete Reisezeit (Beweis unter

Berücksichtigung der Lemmata von Bar-Noy und Schieber)

wie Dijkstras Algorithmus für Distanz-Berechnung.

• Der srCTP-Algorithmus ist bezüglich der erwarteten

Reisezeit optimal.

• Der srCTP-Algorithmus ist bezüglich der Distanz nicht

kompetitiv.

14 / 23

Deterministisches Recoverable

k-CTP (drCTP)

• Zusätzliche Information : Anzahl der Blockaden(z.B. Anzahl bekannter Baustellen)

• A1 : Baustelle• A3 : Keine Baustelle• A4 : Baustelle

• Damit : Maximale Anzahl k (Beispiel k=2) von Blockaden

gegeben

• Wieder alternative Routen berechnen, diesmal abhängig

von bereits blockiert aufgefundenen Kanten

(Blockaden-Rest-Risiko :-)

• Achtung Baustellen-Beispiel dient nur der Anschauung, wo

die k möglichen Blockaden auftauchen ist völlig unbekannt

!!!15 / 23

Deterministisches Recoverable

k-CTP (drCTP)• Deterministisches Recoverable k-Canadian Traveller

Problem

Gegeben: Graph G = (V , E ), Startknoten s, Zielknoten t ,

Kostenfunktion c, Recoverfunktion tr , Anzahl der

Blockaden k Maximal k Kanten e ∈ E können für tr (e)blockiert sein.

Gesucht: Reisestrategie, die an Knoten v aufgrund der

aktuell bekannten und früheren Blockaden möglichst

günstigen nächsten Knoten ausgibt !• Lösungsidee:

• k (+1) Reisestrategien Si für 0 ≤ 1 ≤ k bereits blockierte

Kanten berechnen.• Kantenblockaden b zählen• Die noch möglichen Blockaden i = k − b geben Strategie

Si an

• Dabei ist Sk (k Kanten bereits blockiert → 0 weitere

Blockaden möglich) durch Dijkstra’s Algorithmus gegeben. 16 / 23

k Reisestrategien

• Eine Reisestrategie besteht aus n = ‖V ‖ Listen von

alternativen Kanten AE (v ) für jeden Knoten v ∈ V .

• Für eine Reisestrategie Si , die i weitere mögliche

Blockaden berücksichtigt gilt für alle v ∈ V

‖AEi (v )‖ = i + 1.

• Besitzt Knoten v nur j < i + 1 adjazente Kanten, so wird

AEi (v ) mit der Kante (v , v ) „aufgefüllt “.

• Da (v , v ) nicht blockiert sein kann, steht dem Reisenden

immer die Option „Abwarten an v “zur Verfügung.

• AEi (v ) sind vergleichbar PL(v ) sind aber anders zu

berechnen.

17 / 23

k Reisestrategien — Sicht des

Reisenden

Reisender erreicht Knoten v .

• Fall 1: Es wurden bereits b Kanten blockiert, bevor v

erreicht wurde

→ Strategie Si , i = k − b wird benutzt.

• Fall 2: Es wurden noch keine Kanten blockiert

→ Strategie Sk wird benutzt.

• Benutzung einer Strategie Sj an Knoten v :

• Falls keine adjazenten Kanten blockiert sind,

benutze besondere Kante aus AEj (v ) (Primärkante)• Sonst, falls b adjazente Kanten blockiert sind,

benutze b−te alternative Kante aus AEj (v )

18 / 23

k Reisestrategien — Berechnung,

Konzept

• Berechnung von Sj , 0 < j ≤ k beruht auf Si , 0 < i < j !

• iterativ

• Berechne Strategie S0 mit Dijkstra• Berechne Strategie S1 mittels S0 . . .

• rekursiv

• Berechne Sk aufgrund von S(k−1)

• Berechne S(k−1) mittels S(k−2) . . .

• Da wir zunächst von k möglichen Blockaden ausgehen

müssen und daher ohnehin jede Strategie S0, . . . , Sk

berechnen, können wir iterativ vorgehen

19 / 23

k Reisestrategien — Berechnung

• Berechnung von Sj , 0 < j ≤ k beruht auf S(j−1) !

• Lemma nach Bar-Noy und Schieber:

Die a−te alternative Kante aus AEj (v ) der Strategie Sj

entspricht der a−ten Kante aus AE(j−1)(v ) für S(j−1) !

• D.h. alle AEj (v ), 0 < j ≤ k stimmen überein, AEj(v ) hat

jeweils lediglich eine Kante mehr als AE(j−1)(v )

• Dennoch müssen alle Strategien nacheinander iterativ

berechnet werden !

• Warum ?

• Die Ordnung der „restlichen“ adjazenten Kanten von v als

alternativen Kanten AEj(v ) für Sj muss durch die

komplette Liste AE(j−1)(v ) für S(j − 1) bestimmt werden!

20 / 23

Alternative Kanten — Berechnung

• Die Kanten (v , vi ) aus AEj (v ) sind sortiert nach:

c(v , vi ) + dist (j , vi )

• Dabei ist dist (j , vi ) die worst case Distanz zwischen vi und

t in Strategie Sj

• dist (j , v ) wird in jeder Strategie Sj bestimmt als:

min(v ,vi )∈Emaxj−1

i=1c(v , xi )+dist (j−i , xi )∪c(v , vi )+dist (j , vi )

• D.h. die nächste alternative Kante der j−ten Strategie wird

so ausgewählt, dass die Distanz dist (j , v ), also die Distanz

zwischen v und t im Falle dass an Knoten v j Blockaden

auftreten möglichst klein ist, obwohl die Blockaden

maximal ungünstig sind (worst case).

• Die Kante, die zur minimalen worst case Distanz dist (j , v )führt, wird zur Primärkante für v in Strategie Sj

21 / 23

Dijkstra-Analogie

• Die k Reisestategien für das drCTP bestehen aus:

• k Listen AEj (v ) der alternativen Kanten an v• k Primärkanten Pj = (v , vi )j an v

• Beide können in einem Dijkstra ähnlichen Algorithmus fürjede Strategie Sj bestimmt werden:

• Initial: ∀v 6= t ∈ V : dist (j , v ) = ∞, dist (j , t ) = 0• In jedem Schritt Knoten u mit minimaler dist (j , u) wählen

und alle adjazenten Knoten auf Verbesserung der

vorläufigen Distanz und Bestimmung einer neuenPrimärkante überprüfen.

22 / 23

drCTP-Algorithmus nach Bar-Noy

und SchieberAlgorithmus zur Ermittlung der j−ten Strategie

(1) setze

dist (j , v ) := ∞

dist (j , t ) := 0

M = t

(2) bestimme u /∈ M mit dist (j , u) = mindist (j , u) : u /∈ M

(3) setze M = M ∪ u

(4) für alle v ∈ V mit (u, v ) ∈ E

(5) falls dist ′(j , v ) = maxmaxj−1

i=1c(v , xi ) + dist (j − i , xi ) ∪

c(v , u) + dist (j , u) < dist (j , v ) setze

dist (j , v ) = dist ′(j , v )

Pj (v ) := (u, v )

(6) falls M 6= V , gehe zu (2)

23 / 23