Suche Home Einstellungen Anmelden Hilfe  

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 :

  1. Priorität
  2. 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:

  1. binäre Suchbäume
  2. for to do - Schleifen
  3. 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.
 
 
 
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:

 

Literaturhinweise:

 
 

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

info  project5.zip

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