Algorithmen fur¨ Routenplanung - KIT - ITI Algorithmik I · Probleme z. B. Vertex-Cover, 3-Color, Independent Set Mehr dazu spater¨ Ben Strasser – Algorithmen f¨ur Routenplanung

INSTITUT FUR THEORETISCHE INFORMATIK · ALGORITHMIK

Algorithmen fur Routenplanung8. Vorlesung, Sommersemester 2017

Ben Strasser | 29. Mai 2014

KIT – Universitat des Landes Baden-Wurttemberg undnationales Großforschungszentrum in der Helmholtz-Gemeinschaft

www.kit.edu

http://www.kit.edu

Exkurs

Heute:keine RoutenplanungWomit sind die gesehenen Algorithmen verwandt?

Nachste Woche:Wieder Routenplanung

Ben Strasser – Algorithmen fur RoutenplanungFolie 2 – 29. Mai 2014

Institut fur Theoretische InformatikLehrstuhl Algorithmik

Dunnbesetzte Gleichungssysteme

Große quadratische Gleichungssysteme Losen hat vieleAnwendungenSchnelles Losen ist wichtigAlgorithmus von Gauß in O(n3) wobei n die Anzahl der Variablenist

Oft zu langsam

Oft sind Gleichungssysteme dunnbesetztd. h. viele Koeffizienten sind 0

Idee: Speichere 0-Koeffizienten nicht abAber: Wie 0-Koeffizienten wahrend des Losens erhalten?




Ziel: Obere Dreiecksmatrix per Gauselimination1 −1 1 1 11 1 0 0 −21 0 −1 −1 0−1 0 −1 −2 0

1 −1 0 0 1

4 Nullen im oberen Dreieck




Ziel: Obere Dreiecksmatrix per Gauselimination1 −1 1 1 10 2 −1 −1 −30 1 −2 −2 −10 −1 0 −1 10 0 −1 −1 0




Ziel: Obere Dreiecksmatrix per Gauselimination1 −1 1 1 10 2 −1 −1 −30 0 − 3

2 − 32

12

0 0 − 12 − 3

2 − 12

0 0 −1 −1 0




Ziel: Obere Dreiecksmatrix per Gauselimination1 −1 1 1 10 2 −1 −1 −30 0 − 3

2 − 32

12

0 0 0 −1 − 23

0 0 0 0 − 13

Keine Nullen ubrig→ :(




Idee: Spalten und Zeilen umsortieren1 −1 1 1 11 1 0 0 −21 0 −1 −1 0−1 0 −1 −2 0

1 −1 0 0 1

Alle 4 Nullen erhalten→ :)




Idee: Spalten und Zeilen umsortieren1 −1 0 0 1−2 1 0 0 1

0 0 −1 −1 10 0 −1 −2 −11 −1 1 1 1





Idee: Spalten und Zeilen umsortieren1 −1 0 0 10 −1 0 0 30 0 −1 −1 10 0 −1 −2 −10 0 1 1 0





Idee: Spalten und Zeilen umsortieren1 −1 0 0 10 −1 0 0 30 0 −1 −1 10 0 0 −1 −20 0 0 0 1





Idee: Spalten und Zeilen umsortieren1 −1 0 0 10 −1 0 0 30 0 −1 −1 10 0 0 −1 −20 0 0 0 1





Warum funktioniert das?




Jeder Eintrag der nicht Null ist entspricht einer Kante.

1 −1 1 1 11 1 0 0 −21 0 −1 −1 0−1 0 −1 −2 0

1 −1 0 0 1

0

1

2

3

4

Variablenelimination↔ KnotenkontraktionJeder Shortcut zerstort eine Null





1 −1 1 1 10 2 −1 −1 −30 1 −2 −2 −10 −1 0 −1 10 0 −1 −1 0

1

2

3

4Variablenelimination↔ Knotenkontraktion

Jeder Shortcut zerstort eine Null





1 −1 1 1 10 2 −1 −1 −30 0 − 3

2 − 32

12

0 0 − 12 − 3

2 − 12

0 0 −1 −1 0

2

3







1 −1 1 1 10 2 −1 −1 −30 0 − 3

2 − 32

12

0 0 0 −1 − 23

0 0 0 0 − 13

3







1 −1 1 1 10 2 −1 −1 −30 0 − 3

2 − 32

12

0 0 0 −1 − 23

0 0 0 0 − 13

4






1 −1 0 0 1−2 1 0 0 1

0 0 −1 −1 10 0 −1 −2 −11 −1 1 1 1

4

1

2

3







1 −1 0 0 10 −1 0 0 30 0 −1 −1 10 0 −1 −2 −10 0 1 1 0

4

1

2

3






1 −1 0 0 10 −1 0 0 30 0 −1 −1 10 0 −1 −2 −10 0 1 1 0

4

2

3






1 −1 0 0 10 −1 0 0 30 0 −1 −1 10 0 0 −1 −20 0 0 0 1

4

3






1 −1 0 0 10 −1 0 0 30 0 −1 −1 10 0 0 −1 −20 0 0 0 1

4





Wenig Kanten im CCH-Graph↔ viele 0-Koeffizienten in MatrixWie hangt dies genau zusammen?

Baumzerlegung



Baumzerlegung

BaumzerlegungenSehr breites ThemenfeldSchwer zu uberblickenSehr viel Literatur

AnwendungenRoutenplanungGleichungssysteme losenFixed Parameter Tractablilty (FPT) Algorithmen fur NP-schwereProbleme

z. B. Vertex-Cover, 3-Color, Independent SetMehr dazu spater



Definition

Eine Baumzerlegung (B,T ) eines ungerichteten ungewichtetenGraphen (V ,E) besteht aus

Menge von BagsJeder Bag ist eine Knotenmenge

Backbone TGraph mit Bags als KnotenBei Baumzerlegung ist T ein Baum(Analog: Bei Pfadzerlegung ist T ein Pfad)

Tx ist Teilgraph von TTx wird induziert durch Bags die Knoten x enthalten



Definition

Eine Baumzerlegung (B,T ) eines ungerichteten ungewichtetenGraphen (V ,E) besteht aus

Menge von BagsJeder Bag ist eine Knotenmenge

Backbone TGraph mit Bags als KnotenBei Baumzerlegung ist T ein Baum(Analog: Bei Pfadzerlegung ist T ein Pfad)

Tx ist Teilgraph von TTx wird induziert durch Bags die Knoten x enthalten



Definition

Jede Baumzerlegung muss drei Bedingungen erfullenJeder Knoten ist in einem oder mehreren Bags⋃

b∈B

b = V

Jede Kante ist in einem Bag

∀{x , y} ∈ E : ∃b ∈ B : x ∈ b ∧ y ∈ b

Fur jeden Knoten x ist Tx ein Baum



Beispiel

ba c d

h

q

f g

m

n

po

e

i

r

j

k

l

q rp ij r ik l j e i

p ch ep c

d e c

n om omp f mp f gp c b f c a b f



Baumbreite

Breite einer Baumzerlegung ist maximale Baggroße minus 1Baumbreite tw eines Graphs ist minimale Breite einerBaumzerlegung



Fixed Parameter Tractablity (FPT)

Problem ist FPT in der Baumbreite wenn es Algorithmus gibt mitLaufzeit:

f (tw) · p(n)

tw ist Baumbreite, n ist Knotenanzahlf beliebige Funktion die nicht von n abhangtp beliebiges Polynom

BeispielVertex-Cover in Zeit 2tw ·m losbar



Zusammenhang zu CCH

Maximale Cliquen in CCH-Graph sind Bags einerBaumzerlegung



Schritt 1: CCH-Graph bauen

ba c d

h

q

f g

m

n

po

e

i

r

j

k

l

ba c d

h

q

f g

m

n

po

e

i

r

j

k

l

Knotenordnung: k, l, a, b, d, n, j, o, m, f, g, h, e, q, r, i, p, c



Schritt 2: Maximale Cliquen

ba c d

h

q

f g

m

n

po

e

i

r

j

k

l


p ch ep c

d e c




Zusammenhang zu CCH

TerminologieIm Baumzerlegungskontext verwendet man folgende Begriffe:

Kontrationsordnung ↔ (perfect) elimination orderCCH-Graph ↔ chordaler Supergraph



Definition Multilevel Partition

Multilevel Partition P ist Menge von ZellenJede Zelle z ist Menge von Knoten

Wir fordern:Es gibt immer eine top-level Zelle die alle Knoten enthaltZellen die sich “beruhren” sind verschachtelt



Wann beruhren sich Zellen?

Keine Beruhrung Beruhrung Beruhrung

Zwei Zellen beruhren sich wenn sieeinen gemeinsamen Knoten haben oderes eine Kante zwischen den Zellen gibt.



Wann beruhren sich Zellen?

WarnungZellen werden hier per Knotenseparator getrenntBei MLD ublicherweise aber per KantenschnitteKnotenseparatoren passen besser mit Baumzerlegungzusammen



Beispiel

ba c d

h

q

f g

m

n

po

e

i

r

j

k

l

Kreise sind ZellenToplevel Zelle nicht eingezeichnet



Zellenrand

Zellenrand R einer Zelle Z sind Knoten dienicht in Z sindaber es eine Kante gibt zwischen Knoten in Z und in R



Zusammenhang zu MultilevelPartition

ZusammenhangMultilevel Partition entspricht gewurzelter BaumzerlegungZellen entsprechen BagsKind-Eltern-Relation entspricht Treebackbone

Bag ist Vereinigung vonZellenrand und Zellohne das Innere der Kinderzellen



Beispiel

ba c d

h

q

f g

m

n

po

e

i

r

j

k

l

p c i

e ip c

h ep c

p c

f p c

f gp c

n om omp f mp b f c a b f

j r ik l j

q rp i

p r i

d e c



Beispiel

c d

h

q

g

p

e

i

r

j

k

l

ba

f

m

n

o


p ch ep c

d e c




Straßengraph

orange Knoten sind in einem BagBeispiel ist ein Pfad im Treebackbone von 6 Bags



Straßengraph




Straßengraph




Straßengraph




Straßengraph




Straßengraph




Baumbreite Schranken

Graph Upper Treewidth Bound

DIMACS Colorado 87DIMACS Kalifornien & Nevada 127DIMACS Europa 449DIMACS USA 311OSM London 84OSM Baden-Wurttemberg 107OSM Deutschland 220



Vertex-Cover

Eingabe:einfacher Graph mit Knoten und Kantenungerichtet und ungewichtet

Ausgabe:Knotenmenge CFur jede Kante {x , y} muss x ∈ C oder y ∈ C oder beide sein

Zielfunktion:C soll moglichst klein sein



Vertex-Cover

Eingenschaften:klassisches NP-schweres Problemist FPT in der BaumbreiteLaufzeit 2tw ·m

Achtung: Die Baumbreite von Straßengraphen ist zu groß furFPT Algorithmen



Idee

Schritt 1: Find BaumzerlegungSchritt 2: Wahle irgendeinen Knoten als Wurzel aus

Idee:Speichere fur jeden Bag b eine Tabelle mit 2|b| ZeilenTabelle enthalt Zeile fur jede Auswahl an Knoten aus bJede Zeile enthalt fur jeden Knoten x aus b ein Bit ob x ∈ CJede Zeile enthalt Große eines kleinsten Vertex-Covers

Nicht der ganze Graph wird uberdecktNur durch von Knoten im Teilbaum von b induzierter SubgraphuberdecktZellensichtweise: Graph induziert durch innere und Randknotenuberdeckt

Falls nicht moglich, dann Große∞



Beispiel

ba c d

h

q

f g

m

n

po

e

i

r

j

k

l

Tabelle fur Bag {f ,p, c}f ∈ C p ∈ C c ∈ C Große C (nicht gespeichert)

◦ ◦ ◦ 4 a, b, g, o◦ ◦ • 3 c, a, o◦ • ◦ 3 p, m, b◦ • • 4 p, c, a, m

· · ·



Beispiel

ba c d

h

q

f g

m

n

po

e

i

r

j

k

l

Tabelle fur Bag {f ,p, c}f ∈ C p ∈ C c ∈ C Große C (nicht gespeichert)

· · ·• ◦ ◦ 4 f , b, o, g• ◦ • 3 f , c, o• • ◦ 4 f , p, n, b• • • 4 f , p, c, n



Algorithmus

Bottom-UpBerechne erst die Tabellen der BlatterDann die ZwischenknotenSchlussendlich die Tabelle der Wurzel

Tabellen der Blatter werden mit durchprobieren berechnetAndere Bags verwenden Tabellen ihrer KinderKleinste Große in Tabelle der Wurzel ist Endergebniss



Literatur I

Hans L. Bodlaender.A tourist guide through treewidth.Acta Cybernetica, 11:1–21, 1993.

Hans L. Bodlaender.Treewidth: Structure and algorithms.In Proceedings of the 14th International Colloquium on Structural Information andCommunication Complexity, volume 4474 of Lecture Notes in Computer Science,pages 11–25. Springer, 2007.

Jean Blair and Barry Peyton.An introduction to chordal graphs and clique trees.In Graph Theory and Sparse Matrix Computation, volume 56 of The IMA Volumesin Mathematics and its Applications, pages 1–29. Springer, 1993.



Documents

Algorithmen fur¨ Routenplanung - KIT - ITI Algorithmik I · Probleme z. B. Vertex-Cover, 3-Color, Independent Set Mehr dazu spater¨ Ben Strasser – Algorithmen f¨ur Routenplanung