Suche Home Einstellungen Anmelden Hilfe  

 
UNI Didaktik der 
Informatik
DdI
 Projekttage zum Erwerb eines Scheins zur
Vorlesung Algorithmen, Daten und Programme II, SS 98
 

Programmierung elementarer Algorithmen

Aufgabe 3
"Versorgung der Bevölkerung"

Mittlerweile haben sich die Siedlungen auf dem Planeten Erde2 zu größeren Städten entwickelt. Zur Versorgung der einzelnen Häuser mit Grundnahrungsmitteln werden Roboterboten verwendet , die jedes zu beliefernde Haus genau einmal aufsuchen müssen (jede Stadt kann sich nur einen Boten leisten).

Schreiben Sie Programme, welche ausgehend von den bekannten Entfernungen zwischen einzelnen zu beliefernden Häusern die Reihenfolge der Häuser bestimmen, in der der Roboterbote sie aufsuchen muss, um insgesamt einen möglichst kurzen Rundweg zurückzulegen. Verwenden Sie unterschiedliche Verfahren und vergleichen Sie diese!

Bsp. (weitere in der angegebenen Literatur)
von Hausnr  zu Hausnr:  Entfernung
1 2
20
1
3
23
1
4
1
2
4
4
2
5
15
3
4
36
3
6
28
4
5
9
4
7
16
4
6
25
5
7
3
6
7
17
kurzer Weg: 3,1,4,2,5,7,6,3 (Länge: 91)

Stichworte:
Problem des Handlungsreisenden, NP-vollständige Probleme, Backtracking, Branch&Bound, Dynamische Programmierung, Heuristiken, genetischer Algorithmus
Literatur:
Duden Informatik, Algorithmen-Sedgewick S. 703-725, 673, Bundeswettbewerb Informatik Bd. 7 S.97ff, Turing-Omnibus S. 111ff, Web
 

Ergebnisse der Projektgruppe  

Benutzer: gast • Besitzer: mthomas • Zuletzt geändert am: