Aufgaben
Aufgaben zu dem Themenbereich "Verzweigen und Beschrenken"
Anwendung auf das Rucksackproblem
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.
Zusatzaufgabe: Entwickeln Sie einen Algorithmus für das Rucksackproblem.
Lösung
Die Lösung wird später nachgetragen.
TSP - Trade 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 Baumstrucktur. Überprüfen sie Ihr Ergebniss mit dem Racket Programm.
(Nutzen Sie dazu bitte keinen Internet Explorer, da dort der Code nicht ordnungsgemäß ausgeführt wird. Getesteter Browser: Firefox)
Verwenden sie dazu folgende Definition:
(define matrix2 '((0 65 14 93) (87 0 55 13) (6 59 0 74) (33 27 71 0)))
Zusatzaufgabe: Testen Sie die eine weitere Heuristik mit dem Lösungsbaum.
Lösung
Die Lösung wird später nachgetragen.
Gegeben ist folgende Entfernungsmatrix:
| von \ nach | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 1 | x | 9 | 5 | 3 |
| 2 | 11 | x | 17 | 5 |
| 3 | 17 | 13 | x | 19 |
| 4 | 19 | 21 | 1 | x |
Stellen Sie die reduzierte Entfernungsmatrix auf!