Didaktik
der
Informatik
Projekttag zum Erwerb eines
Scheins zur
Vorlesung Algorithmen, Daten
und Programme II
Projektgruppe V
Jan Becker
Stephan Uhlmann
Thomas Franz
Dokumentation
zu
"Shuttle-Dienst"
Inhalt der Aufgabe 5:
Zwischen 2 Planeten - Erde und Erde2 - gib es nur ein
mal an Tag eine Shuttleverbindung (hin und zurück) mit logischerweise
begrenzter Ladekapazität.
Hier setzt unsere Aufgabe an, welche die optimale Auslastung
des Shuttles beinhaltet.
Die Parameter nach denen die Passagiere ausgesucht werden
sind :
-
Priorität
-
Gewicht .
Diese Werte geben die Passagiere am Vortag an, weiterhin
wird eine laufende Nummer und der Abflugort gespeichert.
Im Ergebnis unseres Programmes muß eine möglichst
"wertvolle" Ladung stehen.
Weiterhin bekommen Personen die nicht befördert werden
konnten einen zusätzlichen Prioritätszuwachs gegenüber denen
die am nächsten Tag zu befördernden sind. So wird gewährleistet
das niemand ewig "steht"- also die Wartezeit wird angerechnet.
Lösungsansatz:
Lösungsmöglichenkeiten für dieses Problem sind:
-
binäre Suchbäume
-
for to do - Schleifen
-
Branch-and-Bound Verfahren
Wegen des Personalmangels und der begrenzten Zeit die uns während
des Projektes zur Verfügung stand, entschieden wir uns für die
Lösung des Problems durch die Erzeugung eines binären Suchbaumes.
-
Baumstruktur dieses Rucksackproblems - aus
Duden der Informatik - :
Da das Shuttle nur eine bestimmte Kapazität besitzt, muß
man alle Möglichkeiten (bezüglich Priorität und Gewicht)
- siehe Baum - nach der Optimalen durchsuchen, (d.h. man sucht eine
Indexmenge { 1...n } mit : die Summe aller Prioritäten i
ist maximal und die Summe aller Gewichte i
ist kleiner oder gleich der maximalen Ladekapazität).
Im schlimmsten Fall hat der Algorithmus eine Laufzeit der Ordnung
O(2^n), da es 2^n Indexmengen gibt.
Algorithmen der Laufzeit O(n) gibt es für dieses Problem nicht.
TEST:
In Standard ML -
Eingabe von : use"shuttle.sml";
Arbeitsgang der Lösungsfindung der Gruppe:
-
Lesen der Aufgabenstellung und Nachschlagen der in der Aufgabenstellung
angegebenen Stichworte
-
Identifizierung der Aufgabe als "Rucksackproblem" - Verwendung der dynamischen
Programmierung
-
Baumstruktur als Grundlage für die Implementierung
-
Erzeugung eines binären Baumes (tree.sml)
-
Herausfiltern der Passagiere die sich nicht am Abflugort befinden (loads.sml)
-
Erzeugung einer Passagierliste anhand der Indizies die der Suchbaum
liefert (loads.sml)
Literaturhinweise:
-
Titel: Algorithmen Autor: Robert Sedgewick
-
Duden der Informatik
-
Vergleiche auch Ergebnisse der anderen Projektgruppen zur dynamischen Programmierung
!
project5.zip
|
|
Benutzer: Gast •
Besitzer: mthomas • Zuletzt geändert am:
|
|
|
