Verzweigen und beschränken - Loesungen

Aufgabe 1:

Aufgabe 2:

1. (10)
2. (10, 6.6)
3. (10, 9, 6.6)
4. (10, 9, 6.6, 5)
5. (10, 9, 6.6, 5, 1)
6. (9, 6.6, 5, 1) -> 10 wird gestrichen, da der Knoten nicht weiter expandiert werden kann, 9 wird expandiert
7. (12, 9, 6.6, 5, 1)
8. (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
9. (13, 12, 12, 9, 6.6, 5, 1)
10. (13, 12, 9, 6.6, 5, 1) -> 12 aus dem zweiten Niveau kann nicht mehr expandiert werden

Aufgabe 3:

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:

Google-Maps Ergebnis