Aus ProgrammingWiki

Inhaltsverzeichnis

1 Aufgabe 1
2 Aufgabe 2
3 Aufgabe 3
4 Aufgabe 4
5 Aufgabe 5

Aufgabe 1

Signatur:

Datentyp:	priority_queue
Sorten:	element, priority_queue
Konstruktoren:	create: $\rightarrow$ priority queue
	push: priority_queue $\times$ element $\rightarrow$ priority_queue
Prädikat:	empty: priority_queue $\rightarrow$ {true, false}
Selektoren:	top: priority_queue - $\{\epsilon\} \rightarrow$ element
	pop: priority_queue - $\{\epsilon\} \rightarrow$ priority_queue

Axiome:

create = $\epsilon$	erzeugt eine leere priority queue
empty( $\epsilon$ ) = true	leere priority queue ist leer
empty(push(priority_queue, element)) = false	nach push ist die priority queue nicht leer
top(push(priority_queue, element)) = element	top gibt das Element mit der höchsten Priorität zurück
pop(push(priority_queue, element)) = priority_queue	pop entfernt das Element mit der höchsten Priorität

Aufgabe 2

(10)
(10, 6.6)
(10, 9, 6.6)
(10, 9, 6.6, 5)
(10, 9, 6.6, 5, 1)
(9, 6.6, 5, 1) -> 10 wird gestrichen, da der Knoten nicht weiter expandiert werden kann, 9 wird expandiert
(12, 9, 6.6, 5, 1)
(12, 12, 9, 6.6, 5, 1) -> Die 12 aus dem zweiten Niveau steht immer noch vorn, da die 12 aus dem dritten Niveau nicht besser ist
(13, 12, 12, 9, 6.6, 5, 1)
(13, 12, 9, 6.6, 5, 1) -> 12 aus dem zweiten Niveau kann nicht mehr expandiert werden

Aufgabe 3

Der Ergebnissvektor lautet: $\vec{x}=(1,1,1,0)$ .

Aufgabe 4

Um die Lösung des TSP zu überprüfen, stellen sie zuerst alle möglichen Rundreisen auf. Zu jeder Rundreise berechnen sie die Länge. Die kürzeste Rundreise muss dann genau mit der übereinstimmen, die wir mit branch and bound ermittelt haben.

Aufgabe 5

Kurzfassung der Lösung:

Die beste Route ist also Dresden, Görlitz, Zittau, Bautzen und zurück mit einer Länge von 255km.

Ausführliche Lösung:

Schritt 1: Ausgangsmatrix reduzieren

von\nach	Dresden	Zittau	Görlitz	Bautzen
Dresden	$\infty$	$108_{45}$	$109_{46}$	$63_0$	63
Zittau	$114_{77}$	$\infty$	$37_0$	$46_9$	37
Görlitz	$110_{75}$	$35_0$	$\infty$	$49_{14}$	35
Bautzen	$65_{19}$	$46_0$	$51_5$	$\infty$	46
	19	0	0	0	200

Schritt 2: Dresden - Zittau

von\nach	Dresden	Zittau	Görlitz	Bautzen
Dresden	$\infty$	$108_0$	$\infty$	$\infty$	108
Zittau	$\infty$	$\infty$	$37_0$	$46_9$	37
Görlitz	110	35	$\infty$	49	49
Bautzen	65	46	51	$\infty$	51
	14	0	0	0	259

Schritt 3: Dresden - Görlitz

von\nach	Dresden	Zittau	Görlitz	Bautzen
Dresden	$\infty$	$\infty$	$109_0$	$\infty$	109
Zittau	$114_{68}$	$\infty$	$\infty$	$46_0$	46
Görlitz	$\infty$	$35_0$	$\infty$	$49_{14}$	35
Bautzen	$65_{19}$	$46_0$	$\infty$	$\infty$	46
	19	0	0	0	255

Schritt 4: Dresden - Bautzen

von\nach	Dresden	Zittau	Görlitz	Bautzen
Dresden	$\infty$	$\infty$	$\infty$	$63_0$	63
Zittau	$114_{77}$	$\infty$	$37_0$	$\infty$	37
Görlitz	$110_{75}$	$35_0$	$\infty$	$\infty$	35
Bautzen	$\infty$	$46_0$	$51_5$	$\infty$	46
	75	0	0	0	256

Schritt 5: Dresden - Görlitz - Zittau

von\nach	Dresden	Zittau	Görlitz	Bautzen
Dresden	$\infty$	$\infty$	$109_0$	$\infty$	109
Zittau	$\infty$	$\infty$	$\infty$	$46_0$	46
Görlitz	$\infty$	$35_0$	$\infty$	$\infty$	35
Bautzen	$65_{0}$	$\infty$	$\infty$	$\infty$	65
	0	0	0	0	255

Schritt 6: Dresden - Görlitz - Bautzen

von\nach	Dresden	Zittau	Görlitz	Bautzen
Dresden	$\infty$	$\infty$	$109_0$	$\infty$	109
Zittau	$114_{0}$	$\infty$	$\infty$	$\infty$	114
Görlitz	$\infty$	$\infty$	$\infty$	$49_{0}$	49
Bautzen	$\infty$	$46_0$	$\infty$	$\infty$	46
	0	0	0	0	318

Schritt 7: Dresden - Görlitz - Zittau - Bautzen

von\nach	Dresden	Zittau	Görlitz	Bautzen
Dresden	$\infty$	$\infty$	$109_0$	$\infty$	109
Zittau	$\infty$	$\infty$	$\infty$	$46_0$	46
Görlitz	$\infty$	$35_0$	$\infty$	$\infty$	35
Bautzen	$65_{0}$	$\infty$	$\infty$	$\infty$	65
	0	0	0	0	255

Google-Maps Ergebnis

Verzweigen und beschränken - Loesungen

Aus ProgrammingWiki

Inhaltsverzeichnis

Aufgabe 1

Aufgabe 2

Aufgabe 3

Aufgabe 4

Aufgabe 5

Ansichten

Persönliche Werkzeuge

Navigation

Suche

Werkzeuge