 |
Didaktik der
Informatik |
 |
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:
|
|
|
