Aufgaben
Aus ProgrammingWiki
Archivierte Version vom 2011-05-22T21:55:02+00:00. Aktuelle Version
Aufgaben zu dem Themenbereich "Verzweigen und Beschrenken"
Anwendung auf das Rucksackproblem
Gegeben ist folgende Wertetabelle:
| i | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| w_i | 30 | 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. 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.