Transcript
Eidgen¨ ossische Technische Hochschule Z¨ urich
Ecole polytechnique f´ed´erale de Zurich Politecnico federale di Zurigo Federal Institute of Technology at Zurich
Institut f¨ ur Theoretische Informatik Peter Widmayer Tobias Pr¨oger Thomas Tschager
13. Mai 2015
Datenstrukturen & Algorithmen L¨ osung 11.1
L¨ osungen zu Blatt 11
FS 15
Pfadplanung in Labyrinthen.
a) Wir definieren einen gerichteten Graphen, der einen Knoten f¨ ur jeden m¨oglichen Zustand des Systems enth¨ alt. Ein Zustand wird vollst¨andig durch drei Parameter festgelegt: 1) Das Feld auf dem der Roboter steht, 2) die Blickrichtung des Roboters und 3) ob der Roboter gerade steht oder in Bewegung ist. F¨ ur jedes Feld, auf dem der Roboter stehen kann, haben wir also 8 Zust¨ande (4 Blickrichtungen multipliziert mit 2 M¨ oglichkeiten ob der Roboter steht oder sich bewegt). Wir konstruieren unseren Graphen entsprechend mit 8 Knoten pro Feld des Labyrinths. Ausserdem brauchen wir noch einen Knoten, der dem Zielzustand entspricht, in dem der Roboter entkommen ist. Wir f¨ ugen Kanten f¨ ur Bewegung, Rotation und Stehenbleiben ein und gewichten diese entsprechend der Zeit, die die entsprechende Operation ben¨otigt. Der k¨ urzeste Pfad im Graphen vom Startzustand des Roboters zum Zielzustand entspricht einer Folge von Operationen des Roboters, die ihn schnellstm¨oglich entkommen l¨asst. Das folgende Bild illustriert unsere Konstruktion an einem kleinen Ausschnitt eines Labyrinths. Die Beschriftung der Knoten zeigt die Blickrichtung des Roboters; Doppelpfeile bedeuten, dass er in Bewegung ist. Wir k¨onnten nat¨ urlich Zust¨ande entfernen, die gar nicht vorkommen k¨ onnen.
3
2
3
2
2
2
2
2
2
3
3
2
b) Da der konstruierte Graph keine negativen Kantengewichte enth¨alt, kann ein k¨ urzester Pfad mithilfe des Algorithmus von Dijkstra gefunden werden. c) F¨ ur jedes Feld des Labyrinths wird eine konstante Anzahl Knoten (n¨amlich 8) und eine konstante Anzahl Kanten (h¨ ochstens 20) verwendet. Ist n die Anzahl der Felder im Labyrinth, dann sind |V | ∈ O(n) und |E| ∈ O(n), also ist die Laufzeit des Algorithmus von Dijkstra durch O(n log n) beschr¨ankt.
Anmerkung: F¨ ur einen gerichteten, ungewichteten Graph kann ein k¨ urzester Pfad auch mit einer Breitensuche gefunden werden. Da unser Graph nur ganzzahlige Kantengewichte hat, die alle gr¨ oßer als 0 und durch eine Konstante nach oben beschr¨ankt sind, k¨onnen wir einen erweiterten, ungewichteten Graphen konstruieren, indem wir eine Kante mit Gewicht w > 1 durch w Kanten mit je Gewicht 1 ersetzen. Dazu f¨ ugen wir w − 1 Hilfsknoten ein. Hat diese Kante in unserem urspr¨ unglichen Graph einen Knoten x, der mit einem Knoten y verbunden ist, so sind diese Knoten im erweiterten Graph durch einen Pfad bestehend aus w Kanten verbunden. Somit haben im erweiterten Graph alle Kanten Gewicht 1 und wir k¨ onnen die Breitensuche verwenden, um einen k¨ urzesten Pfad zu finden. Da die Kantengewichte durch eine Konstante nach oben beschr¨ankt sind, werden insgesamt nur O(n) Knoten und Kanten hinzugef¨ ugt und die Laufzeit ist in O(n). L¨ osung 11.2
Max-Flow von Hand.
Der maximale Flusswert betr¨ agt 31. In der folgenden Abbildung ist ein maximaler Fluss dargestellt. Neben jeder Kante e sind die Kapazit¨at ce und der Flusswert xe in der Reihenfolge xe , ce angegeben. Der minimale Schnitt ist gestrichelt eingezeichnet, und die zugeh¨origen Kanten sind fett dargestellt.
Die folgende Abbildung zeigt den Restgraphen f¨ ur den oben dargestellten Fluss. An den Kanten ist die jeweilige Restkapazit¨ at (ce − xe oder xe ) notiert.
L¨ osung 11.3
Evakuierungsprobleme.
a) Sei G = (VG , EG ) das ungerichtete Gitter, das als Eingabe gegeben ist. Die Knotenmenge V des Netzes N enth¨ alt neben allen Knoten aus G zus¨atzlich noch eine Quelle s und eine Senke t. Die Kantenmenge von N enth¨alt nun die folgenden Kanten: • F¨ ur jeden Startknoten si enth¨alt N die Kante (s, si ).
2
• F¨ ur jede (ungerichtete) Kante {v, w} ∈ EG des Gitters enth¨alt N die zwei gerichteten Kanten (v, w) und (w, v). • F¨ ur jeden Randpunkt rj enth¨alt N die Kante (rj , t). Wir konstruieren also ein Netz N = (V, E, c) mit V := VG ∪· {s} ∪· {t}
(1)
E := {(s, si ) | i ∈ {1, . . . , m}} ∪· {(v, w), (w, v) | {v, w} ∈ EG } ∪·
(2)
{(rj , t) | rj ist Randpunkt von G} c((s, si )) := 1 ∀i ∈ {1, . . . , m}
(3)
c((v, w)) := 1 ∀{v, w} ∈ EG
(4)
c((rj , t)) := 2 ∀ Randpunkte rj
(5)
Man beachte, dass ein Randpunkt doppelt benutzt werden kann. Einerseits kann er der letzte Knoten eines Fluchtwegs sein, der im Inneren des Gitters startet. Andererseits kann es aber auch einen Fluchtweg geben, der nur aus genau diesem Randpunkt besteht. Aus diesem Grund muss als Kapazit¨at der Kanten (rj , t) genau 2 gew¨ahlt werden (und nicht 1). Es gibt nun in G genau dann m kanten-disjunkte Fluchtwege, falls es im obigen Netz N einen Fluss mit Wert mindestens m gibt. b) Wir analysieren zun¨ achst die Gr¨osse des Netzes in Abh¨angigkeit von n. Das Gitter G 2 hat |VG | = n viele Knoten, also ist |V | = 2 + |VG | ∈ Θ(n2 ). Ausserdem hat G genau |EG | = 2n(n−1) ≤ 2n2 viele Kanten und 2n+2(n−2) = 4n−4 viele Randpunkte. Da jede Kante von G in N doppelt vorkommt, ist |E| = m+2|EG |+4n−4 ≤ n2 +4n2 +4n ∈ Θ(n2 ). Der Wert eines Flusses ist sowohl durch m (die Anzahl der Startknoten) als auch durch 8n − 8 nach oben beschr¨ ankt, da es nur 4n − 4 Randpunkte gibt und wie oben gesehen maximal zwei Fluchtwege in einem gemeinsamen Randpunkt enden k¨onnen (theoretisch w¨aren mehr Fluchtwege m¨ oglich, aber jeder weitere besucht mindestens einen weiteren Randknoten und muss daher nicht ber¨ ucksichtigt werden). Der Algorithmus von Ford und Fulkerson berechnet einen maximalen Fluss mit O(|E| · φ∗ ) Operationen, wenn φ∗ der maximale Flusswert ist. Damit ist seine Laufzeit pseudopolynomiell, und im Allgemeinen existieren effizientere Methoden zur Flussmaximierung. Da aber hier |E| ∈ Θ(n2 ) als auch φ∗ = min{m, 8n − 8} ∈ Θ(min{m, n}) gelten, betr¨agt die Laufzeit des Algorithmus von Ford und Fulkerson nur O(n2 min{m, n}), und die Wahl dieses Verfahrens ist in diesem speziellen Fall optimal. c) Sei v ∈ VG ein Knoten des Gitters und Γ(v) = {w ∈ VG | {v, w} ∈ EG } die Menge aller Nachbarknoten von v in G. Wir erzeugen nun im Netz N f¨ ur v ∈ VG genau zwei Knoten v in out in out und v , die durch die gerichtete Kante (v , v ) verbunden werden. Abgesehen von dieser Kante enth¨ alt v in nur eingehende und v out nur ausgehende Kanten. F¨ ur jeden Nachbar w ∈ Γ(v) erzeugen wir jeweils die Kanten (v out , win ) und (wout , v in ).
3
F¨ ur alle Startknoten si erzeugen wir ausgehend von der Quelle s eine Kante (s, sin i ). Ausout serdem erzeugen wir f¨ ur jeden Randpunkt rj eine Kante (rj , t) zur Senke t. Allen Kanten wird Kapazit¨ at 1 zugewiesen. Im Vergleich zu a) wird die Anzahl der Knoten nahezu verdoppelt (nur die Quelle und die Senke werden nicht doppelt angelegt). Pro Knoten v ∈ VG wird dabei nur eine weitere Kante angelegt, n¨ amlich die innere Kante (vin , vout ). Damit sind wie vorher |V | ∈ Θ(n2 ) 2 und |E| ∈ Θ(n ), und die Laufzeit ver¨andert sich nicht.
4
