Dynamische Programmierung III - ETH Z...Wege in Graphen zählen gegeben: ger. Graph , Knoten ,...

Vorlesungstermin 11:

DynamischeProgrammierung III

Markus PüschelDavid Steurer

talks2.dsteurer.org/dp3.pdf

Algorithmen und Datenstrukturen, Herbstsemester 2018, ETH Zürich

Plan für heutezurück zu den Graphen:

(kürzeste) Wege mit dynamischer Programmierung

Wege in Graphen zählen

gegeben: ger. Graph , Knoten , Länge

gesucht: Anzahl der Wege in von nach der Länge

G u, v ∈ V (G) L ∈ NG u v L

es kann exponentiell viele solcher Wege geben!

Struktur der Lösungen: jeder Weg von nach der Länge besteht aus einem Weg der Länge zu einem Knoten und einer Kante von nach

L − 1 w

Struktur der Lösungen: jeder Weg von nach der Länge besteht aus einem Weg der Länge zu einem Knoten und einer Kante von nach

Zerlegung in Teilprobleme: Anzahl der Wege von nach der Länge

Rekurrenz zwischen Teilproblemen:

L − 1 w

T (i, k) =(ℓ) i k ℓ

T (i, k) =(ℓ) T (i, j)∑j : (j,k)∈E(G)(ℓ−1)

T (i, k) =(ℓ) i k ℓ

T (i, k) =(ℓ) T (i, j)∑j : (j,k)∈E(G)(ℓ−1)

Beobachtung: ist -te Potenz der Adjazenzmatrix

T (i, k) =(ℓ) i k ℓ

T (i, k) =(ℓ) T (i, j)∑j : (j,k)∈E(G)(ℓ−1)

T (ℓ) ℓ

Beobachtung: ist -te Potenz der Adjazenzmatrix

Fazit: Matrix Multiplikation ist einfache Form derdynamischen Programmierung …

T (i, k) =(ℓ) i k ℓ

T (i, k) =(ℓ) T (i, j)∑j : (j,k)∈E(G)(ℓ−1)

T (ℓ) ℓ

kürzeste Wege in Graphen

gegeben: ger. Graph , Knoten , Gewichte

gesucht: Weg von nach in mit kleinstem Gewicht

G = (V , E) s, t ∈ V

w : E → Rs t G

G = (V , E) s, t ∈ V

w : E → Rs t G

G = (V , E) s, t ∈ V

w : E → Rs t G

Zur Erinnerung: Breitensuche funktioniert, wenn alleGewichte positiv und gleich sind (d.h. wir suchen Weg mitwenigsten Kanten)

G = (V , E) s, t ∈ V

w : E → Rs t G

G = (V , E) s, t ∈ V

w : E → Rs t G

Struktur: optimaler Weg von nach besteht aus optimalemWeg von zu einem Knoten und der Kante von nach

G = (V , E) s, t ∈ V

w : E → Rs t G

s i i t

Teilprobleme: min. Gewicht eines Wegs von zu

G = (V , E) s, t ∈ V

w : E → Rs t G

s i i t

T (j) = s j

Rekurrenz:

G = (V , E) s, t ∈ V

w : E → Rs t G

s i i t

T (j) = s j

T (j) = min T (i) +i : (i,j)∈E w(i, j)

Rekurrenz:

welche Einträge können wir direkt berechnen?welche Reihenfolge für die anderen Einträge?

G = (V , E) s, t ∈ V

w : E → Rs t G

s i i t

T (j) = s j

T (j) = min T (i) +i : (i,j)∈E w(i, j)

Rekurrenz:

Fehlschlag: Rekurrenz bezieht sich nicht auf “kleinere”Teilprobleme ⇝ keine natürliche Reihenfolge (“Rekursionterminiert nicht”)

G = (V , E) s, t ∈ V

w : E → Rs t G

s i i t

T (j) = s j

T (j) = min T (i) +i : (i,j)∈E w(i, j)

Rekurrenz:

Fehlschlag: Rekurrenz bezieht sich nicht auf “kleinere”Teilprobleme ⇝ keine natürliche Reihenfolge (“Rekursionterminiert nicht”)

können wir den Ansatz retten?

G = (V , E) s, t ∈ V

w : E → Rs t G

s i i t

T (j) = s j

T (j) = min T (i) +i : (i,j)∈E w(i, j)

Struktur: optimaler Weg von nach besteht aus optimalemWeg von zu einem Knoten und der Kante von nach dabei hat der optimale Weg von zu eine Kante weniger

G = (V , E) s, t ∈ V

w : E → Rs t G

s i i t

Teilprobleme: min. Gewicht eines Wegs von zu mit Kanten

Rekurrenz:

G = (V , E) s, t ∈ V

w : E → Rs t G

s i i t

T (j, ℓ) = s j ⩽ ℓ

T (j, ℓ) = min T (j, ℓ − 1), min T (i, ℓ − 1) + w(i, j){ (i,j)∈E }

Rekurrenz:

Berechnung: initialisiere Einträge der Form ; berechneEinträge der Form via Rekurrenz; danach …[Bellman–Ford Algorithmus]

G = (V , E) s, t ∈ V

w : E → Rs t G

s i i t

T (j, ℓ) = s j ⩽ ℓ

T (j, 0)T (j, 1) T (j, 2)

Rekurrenz:

T (j, ℓ) = s j ⩽ ℓ

Rekurrenz:

Satz: genau dann wenn es Wegevon nach mit beliebig kleinem (negativen) Gewicht gibt

T (j, ℓ) = s j ⩽ ℓ

n = ∣V ∣

T (j, 2n) < T (j, n − 1)s j

Rekurrenz:

Satz: genau dann wenn es Wegevon nach mit beliebig kleinem (negativen) Gewicht gibt

äquivalent: ein Pfad von nach berührt einen Zyklus mitnegativem Gewicht

T (j, ℓ) = s j ⩽ ℓ

n = ∣V ∣

T (j, 2n) < T (j, n − 1)s j

Rekurrenz:

sei und

Laufzeit: Anzahl der Einträge ist ;

T (j, ℓ) = s j ⩽ ℓ

n = ∣V ∣ m = ∣E∣

Rekurrenz:

sei und

Laufzeit: Anzahl der Einträge ist ;

T (j, ℓ) = s j ⩽ ℓ

n = ∣V ∣ m = ∣E∣

O(n )2

Rekurrenz:

sei und

Laufzeit: Anzahl der Einträge ist ; Berechnung einesEintrags braucht Schritte

T (j, ℓ) = s j ⩽ ℓ

n = ∣V ∣ m = ∣E∣

O(n )2

T (j, ℓ)

Rekurrenz:

sei und

T (j, ℓ) = s j ⩽ ℓ

n = ∣V ∣ m = ∣E∣

O(n )2

T (j, ℓ) O(deg (j))−

Rekurrenz:

sei und

naive Abschätzung: Gesamtlaufzeit (da )

T (j, ℓ) = s j ⩽ ℓ

n = ∣V ∣ m = ∣E∣

O(n )2

O(n )3 deg (j) ⩽− n

Rekurrenz:

sei und

bessere Abschätzung: Gesamtlaufzeit

wobei ;

T (j, ℓ) = s j ⩽ ℓ

n = ∣V ∣ m = ∣E∣

O(n )2

O(n )3 deg (j) ⩽− n

O( N )∑ℓ=1n ∑j∈V j,ℓ

N =j,ℓ deg (j)−

Rekurrenz:

sei und

bessere Abschätzung: Gesamtlaufzeit

wobei ; da , hat

Bellman–Ford Laufzeit

T (j, ℓ) = s j ⩽ ℓ

n = ∣V ∣ m = ∣E∣

O(n )2

O(n )3 deg (j) ⩽− n

O( N )∑ℓ=1n ∑j∈V j,ℓ

N =j,ℓ deg (j)− N =∑ℓ=1n ∑j∈V j,ℓ n ⋅ m

O(n ⋅ m)

alle kürzesten Wege

gegeben: ger. Graph , Gewichte

gesucht: Tabelle min. Gewicht eines - -Wegs

G = (V , E) w : E → RD(i, j) = i j

wir nehmen an

baseline:

G = (V , E) w : E → RD(i, j) = i j

V = {1, … , n}

wir nehmen an

baseline: Bellman–Ford berechnet für ein alle Einträge in Zeit ;

mit Aufrufen erhalten wir gesamte Tabelle in Zeit

G = (V , E) w : E → RD(i, j) = i j

V = {1, … , n}

i ∈ V

D(i, 1), … , D(i, n) O(n ⋅ m)n O(n ⋅2

Verbesserungsidee:

G = (V , E) w : E → RD(i, j) = i j

Verbesserungsidee: berechne alle Einträge gleichzeitig undstelle “bessere” Rekurrenz auf

G = (V , E) w : E → RD(i, j) = i j

Struktur: optimaler Weg von zu besteht aus optimalenWegen von zu und von zu mit halb so vielen Kanten

G = (V , E) w : E → RD(i, j) = i j

i k k j

Struktur: optimaler Weg von zu besteht aus optimalenWegen von zu und von zu mit halb so vielen Kanten

Teilprobleme: min. Gewicht eines - Wegs mit Kanten

Rekurrenz:

G = (V , E) w : E → RD(i, j) = i j

i k k j

T (i, j, r) = i j ⩽ 2r

T (i, j, r) = min T (i, k, r −k∈V 1) + T (k, j, r − 1)

Rekurrenz:

Berechnung:

G = (V , E) w : E → RD(i, j) = i j

T (i, j, r) = i j ⩽ 2r

Rekurrenz:

Berechnung: initialisiere Einträge mit (wie?);verwende Rekurrenz für Einträge mit ; dann , …

G = (V , E) w : E → RD(i, j) = i j

T (i, j, r) = i j ⩽ 2r

r = 0r = 1 r = 2

Rekurrenz:

Laufzeit:

G = (V , E) w : E → RD(i, j) = i j

T (i, j, r) = i j ⩽ 2r

r = 0r = 1 r = 2

Rekurrenz:

Laufzeit: es reicht aus zu betrachtenAnzahl der Einträge ist

Schritte pro Eintrag;

G = (V , E) w : E → RD(i, j) = i j

T (i, j, r) = i j ⩽ 2r

r = 0r = 1 r = 2

r ⩽ ⌈log n⌉O(n ⋅2 log n)

Rekurrenz:

Schritte pro Eintrag;Gesamtlaufzeit

G = (V , E) w : E → RD(i, j) = i j

T (i, j, r) = i j ⩽ 2r

r = 0r = 1 r = 2

O(n)O(n ⋅3 log n)

Rekurrenz:

Schritte pro Eintrag;Gesamtlaufzeit (besser als baseline falls )

G = (V , E) w : E → RD(i, j) = i j

T (i, j, r) = i j ⩽ 2r

r = 0r = 1 r = 2

O(n)O(n ⋅3 log n)

m > n ⋅ log n

Rekurrenz:

Schritte pro Eintrag;Gesamtlaufzeit (besser als baseline falls )

es geht noch besser! [Floyd–Warshall Algorithmus]

G = (V , E) w : E → RD(i, j) = i j

T (i, j, r) = i j ⩽ 2r

r = 0r = 1 r = 2

O(n)O(n ⋅3 log n)

m > n ⋅ log n

Idee: mehr Teilprobleme; weniger Zeit pro Teilproblem

G = (V , E) w : E → RD(i, j) = i j

Teilprobleme: min. Gewicht eines - -Pfads mitallen Zwischenknoten in

G = (V , E) w : E → RD(i, j) = i j

T (i, j) =(k) i j

{1, … , k}

Rekurrenz:

G = (V , E) w : E → RD(i, j) = i j

T (i, j) =(k) i j

{1, … , k}

T (i, j) =(k) min{T (i, j), T (i, k) +(k−1) (k−1) T (k, j)}(k−1)

Rekurrenz:

Laufzeit:

G = (V , E) w : E → RD(i, j) = i j

T (i, j) =(k) i j

{1, … , k}

Rekurrenz:

Laufzeit: Einträge; Zeit pro Eintrag⇝ Gesamtlaufzeit des Floyd–Warshall Algorithmus

G = (V , E) w : E → RD(i, j) = i j

T (i, j) =(k) i j

{1, … , k}

O(n )3 O(1)O(n )3

Dynamische Programmierung III - ETH Z...Wege in Graphen zählen gegeben: ger. Graph , Knoten ,...

Documents

Städtischer Liefer- und Ladeverkehr ......Auch sind die Spediteure häufig nicht bereit, länge-re Wege in Kauf zu nehmen und die ausgewiese-nen Ladebereiche zu nutzen. Für die Beschilderung

WELLENVERBINDER UND AUFHÄNGER - simu · PDF filemotoren und zubehÖr wellenverbinder und aufhÄnger ] 101 wellengrÖsse lÄnge mindest- lÄnge hÖchst- lÄnge anzahl glieder (achkant)

Das richtige Werkzeug · 2019-07-03 · Octave Mannoni Wohin geht die Reise? Die Reise geht ins Digitale natürlich. Und zwar immer schneller. Exponentiell schneller, weil Wissenschaftler

WEGE-Erfolgsgeschichte 2010 bis 2018 Wo stehen wir? Wo ... WEGE-Prozess...WEGE-Büro der VGV Daun Verena Welter, Daniel Weber WEGE-Erfolgsgeschichte 2010 bis 2018 ... verbessern! >>

BIM Fremuth Bekämpfung des Coronavirus und ......Coronavirus und Menschenrechte« Die Bekämpfung des Coronavirus – Menschenrechtliche Grundlagen und Grenzen Die exponentiell wachsende

Magnetische Mißweisung (Kartenmitte): 0° 41' O, 1 ... · Haus Bürgel Punkte: 33 Länge: 1853m Dweg6 Punkte: 1486 Länge: 65208m Hochzeitswiese Punkte: 108 Länge: 1165m Haus Morp

Halogen - Flutlicht R 7 s - illi.eu · Halogen - Flutlicht R 7 s Halogenstab R7s Länge 78,3mm Länge 117,6mm Länge 189,1mm 230 - 240V (klar) Kontaktabstand 74,9mm Kontaktabstand

Wege wiesenthema

SÄTZE MIT VARIABLER LÄNGE - bigdata.uni-frankfurt.de · Sätze variabler Länge 2 Grundlagen der Datenbanksysteme II Definition von Sätzen mit variabler Länge 1. Ein Satz mit

Wenn Rechtsextreme von Naturschutz reden - nf-farn.de · Theorie auf, dass sich die Bevölkerung exponentiell vermehre, wohingegen die Nahrungsmittelproduktion nur linear wachse

DIGITALISIERUNG IN DER INDUSTRIE – CHANCEN NUTZEN · Eigentlich sind Computer, Netzwerke und Softwares nichts Neues. Auch ist mit der fast schon exponentiell wachsenden ... Semantische

vom 4. März 2002 der über - Online Broker · Der Moving Average Convergence Divergence Indikator ... Ein MACD-Indikator basiert auf der Differenz von zwei exponentiell gewichteten

fluter Nr. 34 —Thema: Zukunft Was kommt denn jetzt? · schon 30.000 Jahre altes Gehirn im-stande ist, sich auf die exponentiell be-schleunigte Wissensproduktion einzu-stellen. Unsere

Business Intelligence OLAP & Data Warehousing...(exponentiell) großen Lösungsraum mit Hilfe einer durch ‚Heuristiken’ gesteuerten Suche zu finden. Dabei sind Heuristiken „problem-spezifische

Viele Wege…

Kürzeste Wege in Graphen - Computational-Intelligencefuzzy.cs.ovgu.de/studium/graph/txt/duvigneau.pdf · Definitionen – Länge eines Weges In Graphen ohne gewichtete Kanten bezeichnet

Qualitätsprodukte – Made in Germany...TS2032 360 Stativ mit Laufwagen, Länge = 570 mm TS1501 Twin Stativ mit Laufwagen, Länge = 800 mm TS1502 Twin Stativ mit Laufwagen, Länge

Profile & Bleche - DE | Hirsch€¦ · 2630 0500301000 5 x 3 mm, Länge: 1000 mm 2630 0500400500 5 x 4 mm, Länge: 500 mm 2630 0500401000 5 x 4 mm, Länge: 1000 mm 2630 0600200500

STROJÍRNA TYC s.r.o. · 2017. 2. 27. · STROJÍRNA TYC, s.r.o. FVC FPPC FSGC Der Arbeitsraum: bis 1,6m Breite bis 6m Breite bis 6m Breite bis 4m Länge bis 50m Länge bis 50m Länge

Aleksandar Razpopov - Goethe-Universitätvalenti/TALKS_BACHELOR/slides/Aleksandar... · Probleme für Computer Faktorisieren von Zahlen, Aufwand wächst exponentiell Suchprobleme: