Algorithmen und Berechnungshomplexität
Übungsblatt 3
31
Aufgabe ,
legeben sei ein Hotel mit genau einer Rezeption ,
die nicht
durchgehend besetzt sein muss .
Es jedoch verlangt dans die Rezeption
wird ,
zu
jedem Zeitpunkt besetzt ist dem ein , an
angekündigter Gast im Hotel ankommt .
Die Mitarbeiter müssen jeweils für genau
vier Stunden (am Stück) beschäftigt
und bezahlt werden. Die Startzeiten der
Schichten können dabei
beliebig gewählt
werden .
Seit Etritz ,
=
... En3 dann die Menge
der Ankunftszeiten der Gäste ,
wobei angenommen wird das es sich bei allen
,
ti mit it [1 , ... in 3 um positive
reele Zahlen handelt und , eine Stunde
Intervall der
genau
einem
Lange 1 entspricht .
, Ein
Greedy Algorithmus ist
-
eine
spezielle Art von
Algorithmus , der darauf abzielt ,
ein Problem durch schrittweise Auswahl der
lokaloptimalen Lösung in jedem Schritt
zu lösen , in der
Hoffnung dass diese
,
Entscheidungen
am Ende eine global optimale Lösung ergeben ,
5
Finde das
2 3 größste Element im Graphen
20 15 10
(15220)
Übungsblatt 3
31
Aufgabe ,
legeben sei ein Hotel mit genau einer Rezeption ,
die nicht
durchgehend besetzt sein muss .
Es jedoch verlangt dans die Rezeption
wird ,
zu
jedem Zeitpunkt besetzt ist dem ein , an
angekündigter Gast im Hotel ankommt .
Die Mitarbeiter müssen jeweils für genau
vier Stunden (am Stück) beschäftigt
und bezahlt werden. Die Startzeiten der
Schichten können dabei
beliebig gewählt
werden .
Seit Etritz ,
=
... En3 dann die Menge
der Ankunftszeiten der Gäste ,
wobei angenommen wird das es sich bei allen
,
ti mit it [1 , ... in 3 um positive
reele Zahlen handelt und , eine Stunde
Intervall der
genau
einem
Lange 1 entspricht .
, Ein
Greedy Algorithmus ist
-
eine
spezielle Art von
Algorithmus , der darauf abzielt ,
ein Problem durch schrittweise Auswahl der
lokaloptimalen Lösung in jedem Schritt
zu lösen , in der
Hoffnung dass diese
,
Entscheidungen
am Ende eine global optimale Lösung ergeben ,
5
Finde das
2 3 größste Element im Graphen
20 15 10
(15220)
