Greedy Algorithmus

Erste Frage Aufrufe: 1081     Aktiv: 27.05.2020 um 16:35
0

Hey, wie kann ich die Korrektheit dieses sehr einfachen Greedy Algorithmus beweisen? Ich habe eine Liste von Laufzeiten und muss diese so anordnen, dass die Summe der Beendigungszeitpunkte minimal ist.

Mein Algorithmus dazu ist:

Feld F mit Laufzeiten aufsteigenden sortieren
for i = 0 to f.length do:   
   summe = summe + F[i] + summe 
return summe
Diese Frage melden
gefragt

Punkte: 10

 
Kommentar schreiben
1 Antwort
0

Hallo,

1.) Zeigen, dass der Algorithmus berechnet was er soll

2.) Zeigen, dass er terminiert

Hast du dich hier vielleicht verschrieben "summe = summe + F[i] + summe"?

zu 1.) Das tut er (wenn man von einer sequentiellen Ausführung ausgeht), da es egal ist in welcher Reihenfolge man die Laufzeiten summiert. Somit sind die Laufzeiten addiert = minimale Laufzeit,

zu 2.) Er terminert, da ein Feld nicht unendlich viele Indizes besitzen kann (zwecks Speicher) und der Algorithmus die Schleife somit in endlich vielen Schritten verlassen wird und danach terminiert.

Diese Antwort melden
geantwortet

Punkte: 10

 

Kommentar schreiben