Verzweigen und beschränken - Loesungen

Wiki-Quelltext dieser Seite.

'''Aufgabe 1:'''


'''Aufgabe 2:'''
<ol>
<li>(10)</li>
<li>(10, 6.6)</li>
<li>(10, 9, 6.6)</li>
<li>(10, 9, 6.6, 5)</li>
<li>(10, 9, 6.6, 5, 1)</li>
<li>(9, 6.6, 5, 1) -> 10 wird gestrichen, da der Knoten nicht weiter expandiert werden kann, 9 wird expandiert</li>
<li>(12, 9, 6.6, 5, 1)</li>
<li>(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</li>
<li>(13, 12, 12, 9, 6.6, 5, 1)</li>
<li>(13, 12, 9, 6.6, 5, 1) -> 12 aus dem zweiten Niveau kann nicht mehr expandiert werden</li>
</ol>

'''Aufgabe 3:'''
<center>[[Bild:Aufgabe3.png]]</center>

'''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:
<center>[[Bild:Aufgabe5.png]]</center>
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: Dresden - Zittau
{|border="1"
|width="50pt"| '''von\nach''' 
|width="50pt"| '''Dresden'''
|width="50pt"| '''Zittau'''
|width="50pt"| '''Görlitz''' 
|width="50pt"| '''Bautzen'''
|width="50pt"|  
|-
|'''Dresden''' ||<math>\infty</math> ||<math>108_0</math> ||<math>\infty</math> ||<math>\infty</math> ||108
|-
|'''Zittau''' ||<math>\infty</math> ||<math>\infty</math> ||<math>37_0</math> ||<math>46_9</math> ||37
|-
|'''Görlitz''' ||110 ||35 ||<math>\infty</math> ||49 ||49
|-
|'''Bautzen''' ||65 ||46 ||51 ||<math>\infty</math> ||51
|-
|14 ||0 ||0 ||0 ||259
|}

[http://maps.google.de/maps?f=d&source=s_d&saddr=dresden&daddr=g%C3%B6rlitz+to:zittau+to:bautzen+to:dresden&hl=de&geocode=&mra=ls&sll=51.137085,14.35127&sspn=0.67297,1.388397&ie=UTF8&ll=51.060386,14.356384&spn=0.674088,1.388397&z=10 Google-Maps Ergebnis]