Verzweigen und beschränken - Loesungen

Aus ProgrammingWiki

Archivierte Version vom 2009-05-04T08:47:08+00:00. Aktuelle Version

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 x 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

Inhaltsverzeichnis

Aufgabe 1

Aufgabe 2

Aufgabe 3

Aufgabe 4

Aufgabe 5

Suche