Übung10 –Musterlösung–€¦ · 2 LehrstuhlfürInformatik2 ModellierungundVeriﬁkationvonSoftware DatenstrukturenundAlgorithmenSoSe2018 Übung10(Abgabebis5.7.2018) aaProf.Dr.Ir.Joost-PieterKatoen

2 Lehrstuhl für Informatik 2Modellierung und Verifikation von Software

Datenstrukturen und Algorithmen SoSe 2018Übung 10 (Abgabe bis 5.7.2018)

aaProf. Dr. Ir. Joost-Pieter Katoen Sebastian Junges, Benjamin Kaminski, David Korzeniewski, Tim Quatmann

Übung 10– Musterlösung –

Hinweise:

• Die Lösungen müssen bis Donnerstag, den 5. Juli um 16:00 Uhr in den entsprechenden Übungskasteneingeworfen werden. Sie finden die Kästen am Eingang Halifaxstr. des Informatikzentrums (Ahornstr. 55).

• Die Übungsblätter müssen in Gruppen von je 3 Studierenden aus der gleichen Kleingruppenübung abgegebenwerden.

• Drucken Sie ggf. digital angefertigte Lösungen aus. Abgaben z.B. per Email sind nicht zulässig.

• Namen und Matrikelnummer sowie die Nummer der Übungsgruppe sind auf jedes Blatt der Abgabe zuschreiben. Abgaben, die aus mehreren Blättern bestehen müssen geheftet bzw. getackert werden! DieGruppennummer muss sich auf der ersten Seite oben links befinden.

• Bei Nichtbeachten der obigen Hinweise müssen Sie mit erheblichen Punktabzügen rechnen!

Aufgabe 1 (Ein Graphalgorithmus): (5 + 20 = 25 Punkte)

Gegeben sei der folgende Algorithmus:

Eingabe: zusammenhängender gewichteter, ungerichteter Graph (V, E, W )

Erstelle ein Array Es aller Kanten absteigend sortiert nach Kantengewicht

for i = 0 to |E| − 1:e := Es [i ]

Lösche Kante e aus E

Falls (V, E, W ) nicht zusammenhängend :

Füge Kante e zu E hinzu

Ausgabe: (V, E)

a) Was berechnet der obige Algorithmus? Begründen Sie ihre Antwort.

b) Führen Sie den obigen Algorithmus auf dem untenstehenden Graphen aus. Geben Sie den Graphen (V, E)nach jeder Iteration der Schleife an.

1



Lösung:

.

a) Der Algorithmus berechnet einen minimalen Spannbaum. Er geht dabei dual zum Kruskal-Algorithmus vor.Statt in jedem Schritt die nächstbilligste Kante, die keinen Kreis einführt, zum Ergebnis hinzuzufügen wirdin jedem Schritt die nächstteuerste Kante, die den Graphen nicht unzusammenhängend macht, gelöscht.

b) Kante 20 wird gelöscht:

Kante 19 wird gelöscht:

Kante 18 wird nicht gelöscht:

2






3






4






5






6






7





.

8



Aufgabe 2 (Minimale Spannbäume): (15 Punkte)

Beweisen oder widerlegen Sie: Der minimale Spannbaum eines Graphen, dessen Kantengewichte alle paarweiseverschieden sind, ist eindeutig.

Lösung:

.

Seien T1 = (V, E1) und T2 = (V, E2) zwei unterschiedliche minimale Spannbäume. Da beide Spannbäume vonein-ander verschieden sind, ihre Knotenmengen aber übereinstimmen, müssen notwendigerweise die Kantenmengenungleich sein, d.h. es muss es in einem der beiden Spannbäume eine Kante geben, die in dem anderen Spannbaumnicht vorkommt.

Es sei nun e1 diejenige Kante mit kleinstem Gewicht, die in einem von beiden aber nicht in beiden Spannbäumenvorkommt. Da alle Kanten nach Annahme eindeutig über ihr Gewicht identifiziert werden können, ist diese Kantee1 auch eindeutig. Wir nehmen imWeiteren ohne Beschränkung der Allgemeinheit an, dass diese Kante e1 in T1 ist.

Wir betrachten nun den Graphen T2 ∪ {e1} := (V, E2 ∪ {e1}), also den Graphen, der entsteht, wenn wir demminimalen Spannbaum T2 die Kante e1 hinzufügen. Da e1 nicht in T2 enthalten ist, T2 aber bereits ein Baum war,muss T2 ∪{e1} nun notwendigerweise einen Zykel enthalten. Da T1 keine Zykel enthält, muss es auf diesem Zykeleine Kante e2 geben, welche in T2, aber nicht in T1 enthalten ist. Da die Kante e2 in einem, aber nicht beidenSpannbäumen enthalten ist, ist e2 nicht diejenige, die diese Eigenschaft erfüllt und minimales Gewicht hat, denndiese Eigenschaft hat alleine die Kante e1. Es muss also gelten:

W (e1) < W (e2)

Da e2 Teil eines Zykels in T2∪{e1} ist, können wir die Kante e2 löschen und erhalten somit einen neuen Spannbaum

T ∗ =(V,(E2 \ {e2}

)∪ {e1}

),

welcher wegen W (e1) < W (e2) ein geringeres Gewicht als der bereites minimale Spannbaum T2 hat.

Dies ist ein Widerspruch und die Annahme, dass zwei voneinander verschiedene minimale Spannbäume existieren,kann nicht wahr sein.

.

Aufgabe 3 (Single-Source Single-Target Shortest Path): (25 Punkte)

Betrachten wir zunächst folgende Definition:Ein Graph mit Koordinaten ist ein 4-Tupel (V, E,W,K) wobei

• (V, E,W ) ein gewichteter Graph ist, und

• K : V → R× R jeden Knoten auf eine Koordinate abbildet.

Zusätzlich nehmen wir an, dass W (v1, v2) ≥ ‖K(v1)−K(v2)‖2.Hinweise:

• Informell bedeutet dies, dass das Gewicht zwischen zwei Knoten mindestens die Länge der Luftlinie ist.

Wir suchen den kürzesten Weg zwischen s und t.Dazu definieren wir unten zusätzlich eine Funktion h : V → R.Wir passen den Dijkstra-Algorithmus so an, dass

• ExtractMin nun argminv∈Q h(v) + dist[v ] auswählt, und

9



• sobald ExtractMin t auswählt, terminiert der Algorithmus.

Beweisen oder widerlegen Sie:

a) Für h(v) = ‖K(v) − K(t)‖1 berechnet der angepasste Dijkstra-Algorithmus einen kürzesten Pfad von snach t.

b) Für h(v) = ‖K(v) − K(t)‖max berechnet der angepasste Dijkstra-Algorithmus einen kürzesten Pfad von snach t.

Hinweise:

• ‖(x, v)‖1 = |x |+ |y |• ‖(x, y)‖2 =

√x2 + y2

• ‖(x, y)‖max = max{|x |, |y |}

Lösung:

.

a) Die Aussage ist falsch. Betrachten wir folgendes Gegenbeispiel:

Der Graph ist gegeben durch:

• V = {A,B, C,D},• E = {e1 = {A,B}, e2 = {B,D}, e3 = {A,C}, e4 = {C,D}},• – K(A) = (0, 0),

– K(B) = (1, 1),

– K(C) = (3, 4),

– K(D) = (4, 4)

• – W (e1) =√2

– W (e2) = 3√2

– W (e3) = 5

– W (e4) = 1

wobei wir eine kürzeste Strecke zwischen s = A und t = D suchen. Die kürzeste Strecke ist gegeben durchABD mit Länge 4

√2 < 4 · 1.5 = 6.

Es gilt

• h(B) = 6,

• h(C) = 1,

• h(D) = 0.

Wir fangen an mit A, dist[B] =√2, dist[C] = 5. ExtractMin wählt C (1+5), dist[D] = 6. ExtractMin wählt

D und terminiert.

b) Die Aussage ist richtig. Aus der Globalübung folgt, das es reicht zu Zeigen dass f entlang jedem Pfad mitStartknoten s monoton ist.

10



Sei π = s . . . vv ′ . . ..

f (v ′) = dist[v ′] + h(v ′)

= dist[v ] +W (v , v ′) + h(v ′)

≥ dist[v ] + ‖K(v)−K(v ′)‖2 + h(v ′)≥ dist[v ] + ‖K(v)−K(v ′)‖max + h(v ′)= dist[v ] + ‖K(v)−K(v ′)‖max + ‖K(v ′)−K(t)‖max≥ dist[v ] + ‖K(v)−K(t)‖max = dist[v ] + h(v) = f (v)

Also ist jeder Pfad Monoton in f , und (siehe GÜ) wählt ExtractMin einen Knoten erst, wenn der MinimalePfad von s zu diesem Knoten gefunden wurde. Wenn der Algorithmus terminiert, wurde Knoten t gefundenund demnach der kürzeste Weg von s nach t.

.

Aufgabe 4 (Schiebepuzzle): (10 Punkte)

Betrachten Sie das n−Schiebepuzzel, wobei ein Quadrat der Größe n mal n gegeben ist. An fast jeder Positionin dem Quadrat befindet sich eines der n2 − 1 Puzzelteile, eindeutig beschriftet mit einer Zahl aus dem Interval1 bis n2 − 1. Es gibt genau eine leere Position. Ein Puzzelteil, das horizontal oder vertikal adjazent zu der leerenPosition ist, kann auf die leere Position geschoben werden. Ziel des Puzzles ist es, die Teile an eine vordefiniertePosition zu schieben, und zwar in möglichst wenigen Zügen.In folgendem Beispiel (n = 3) ist die leere Position in der zweiten Zeile und der ersten Spalte. Die möglichenAktionen ergeben sich durch das Verschieben des Puzzelteils 2, 7 oder 4.

2 3 6

7 8

4 1 5

Formalisieren Sie dieses Problem mit Hilfe von Graphen, und beschreiben Sie, welcher Algorithmus aus der Vor-lesung zur Lösung hilfreich ist. Beschreiben Sie zusätzlich, wie groß der Graph in Abhängigkeit von n ist.

Lösung:

.Wir betrachten den (ungerichteten)

Graphen G = (V, E,W ):• V = {A ∈ {0 . . . n2}n×n|ai j = akl ⇐⇒ i = k ∧ j = l},

• E ⊆ V × V , sodass {A,B} ∈ E gdw:

– ai ,j = 0 ∧ ai+1,j = bi ,j ∧ bi+1,j = 0, oder– ai ,j = 0 ∧ ai ,j+1 = bi ,j ∧ bi ,j+1 = 0.

• W (e) = 1 für alle e ∈ E.

Es gibt circa (n2)! Knoten in G.Als Algorithmus zum finden einer minimalen Anzahl Zügen bietet sich entweder eine Breitensuche oder auchDijkstra an.

.

11



Aufgabe 5 (Dijkstra-Algorithmus): (10 Punkte)

Betrachten Sie den folgenden Graphen:

A

B

CD

E

F

G

H

6

3

3

311

35

3

9

8

35

4

Führen Sie den Dijkstra Algorithmus auf diesem Graphen mit dem Startknoten A aus. Falls mehrere Knoten fürdie nächste Iteration zur Wahl stehen, werden die Knoten dabei in alphabetischer Reihenfolge betrachtet. FüllenSie dazu die nachfolgende Tabelle aus:

Knoten A

B

C

D

E

F

G

H

Lösung:

.

12



Knoten A D E B F G H

B 6 6 6 – – – –

C ∞ ∞ ∞ 17 17 17 17

D 3 – – – – – –

E 3 3 – – – – –

F ∞ 6 6 6 – – –

G ∞ 12 7 7 7 – –

H ∞ 11 11 11 11 11 –

Die grau unterlegten Zellen markieren, an welcher Stelle für welchen Knoten die minimale Distanz sicher berechnetworden ist.

.

13



Aufgabe 6 (Prim-Algorithmus): (15 Punkte)

Führen Sie Prims Algorithmus auf dem folgenden Graphen aus.

A

B

C

D

E

F

G

H

I

J

K

L

M

4

3

9

1

3

3

4

3

3

5

44

4

3

Der Startknoten hat hierbei den Schlüssel A. Geben Sie dazu vor jedem Durchlauf der äußeren Schleife an,

1. welche Kosten die Randknoten haben (d. h. für jeden Knoten v in pq die Priorität von v, wobei ∞ angibt,dass der entsprechende Knoten noch nicht zum Randbereich gehört)

2. und welchen Knoten pq.getMin() wählt, indem Sie den Kosten-Wert des gewählten Randknoten in derTabelle unterstreichen (wie es in der ersten Zeile bereits vorgegeben ist).

Geben Sie zudem den vom Algorithmus bestimmten minimalen Spannbaum an.#Iteration A B C D E F G H I

1 0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞

2

3

4

5

6

7

8

9

10

11

12

13

14



J K L M

∞ ∞ ∞ ∞

Minimaler Spannbau

Lösung:

.

#Iteration A B C D E F G H I1 0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞2 4 3 ∞ ∞ 9 ∞ ∞ ∞3 4 3 ∞ ∞ 9 ∞ ∞ ∞4 4 4 3 9 ∞ ∞ ∞5 4 4 5 ∞ ∞ ∞6 4 5 ∞ 3 37 4 5 ∞ 38 4 5 ∞9 5 310 5111213

J K L M∞ ∞ ∞ ∞1 ∞ ∞ ∞

∞ ∞ ∞∞ ∞ ∞∞ ∞ ∞∞ ∞ ∞∞ ∞ ∞∞ ∞ ∞∞ ∞ ∞∞ ∞ ∞4 ∞ 4

4 34

Hierbei gibt eine unterstrichene Zahl an, in welcher Iteration (zugehöriger Zeilenkopf) welcher Knoten (zugehörigerSpaltenkopf) durch pq.getMin() gewählt wurde. Wir erhalten den folgenden minimalen Spannbaum:

15



A

B

C

D

E

F

G

H

I

J

K

L

M

4

3

5

14

3

3

3

3

4

3

4

.

16

Documents

Übung10 –Musterlösung–€¦ · 2 LehrstuhlfürInformatik2 ModellierungundVeriﬁkationvonSoftware DatenstrukturenundAlgorithmenSoSe2018 Übung10(Abgabebis5.7.2018) aaProf.Dr.Ir.Joost-PieterKatoen