Aufgaben
Aufgaben zu dem Themenbereich "Verzweigen und Beschränken"
1. Wege und Entfernungen
Gegeben ist folgende Entfernungsmatrix:
| von \ nach | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 1 | 0 | 5 | 88 | 49 |
| 2 | 4 | 0 | 64 | 70 |
| 3 | 97 | 17 | 0 | 78 |
| 4 | 2 | 79 | 35 | 0 |
Ermitteln sie alle möglichen Routen und deren Strecken.
Lösung
Es existieren 3! Lösungen:
1->2->3->4->1 : 149
1->2->4->3->1 : 207
1->3->2->4->1 : 177
1->3->4->2->1 : 249
1->4->3->2->1 : 105
1->4->2->3->1 : 289
2. Anwendung des Rucksackproblems
Gegeben ist folgende Wertetabelle:
| i | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| w_i | 35 | 18 | 9 | 4 |
| g_i | 7 | 6 | 3 | 2 |
| wq_i | 5 | 3 | 3 | 2 |
Das zulässige Gesammtgewicht des Rucksackes beträgt 12.
Lösen sie das Rucksackproblem mit einem Breitensuchbaum.
Lösung
Die Lösung wird später nachgetragen.
3. TSP - Traveling Salesman Problem
Gegeben ist folgende Entfernungsmatrix:
| von \ nach | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 1 | 0 | 65 | 14 | 93 |
| 2 | 87 | 0 | 55 | 13 |
| 3 | 6 | 59 | 0 | 74 |
| 4 | 33 | 27 | 71 | 0 |
Finden Sie die kürzeste Rundreise mithilfe der Baumstruktur. Überprüfen sie Ihr Ergebniss mit dem Racket Programm.
(Hinweis: Sollte es zu Problemen in der Ausführung des Programmes kommen, versuchen Sie es bitte mit einem anderen Browser)
Verwenden sie dazu folgende Definition:
(define matrix2 '((0 65 14 93) (87 0 55 13) (6 59 0 74) (33 27 71 0)))
Lösung
Die Lösung wird später nachgetragen.
Zusatzaufgaben:
Testen Sie die eine weitere Heuristik Ihrer Wahl mit dem Lösungsbaum und der Entfernungsmatrix aus Aufgabe 3. Entwickeln sie dafür zuerst eine geignete Schranke und vergleichen Sie anschließend Ihre Ergebnisse.
Entwickeln Sie einen Algorithmus für das Rucksackproblem.