Aus ProgrammingWiki

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.

2. Anwendung des Rucksackproblems

Gegeben ist folgende Wertetabelle:

i	1	2	3	4
	35	18	9	4
	7	6	3	2
	5	3	3	2

Das zulässige Gesammtgewicht des Rucksackes beträgt 12.

Lösen sie das Rucksackproblem mit einem Breitensuchbaum.

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)))

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.