Beweis dass Greedy Algorithmus optimal ist

Kirby.exe

Top Contributor
Also ich habe drei Aufgaben, welche jeweils ein Problem geben und ich einen Greedy Algorithmus entwickeln soll, dann die Laufzeit und den Speicherverbrauch berechnen und anschließend beweisen, dass dieser Algorithmus optimal ist. Die ersten beiden Teilaufgaben habe ich bereits gelöst. Jedoch bei dem Beweis hänge ich im Moment etwas...xD

Uns wurden zwei Beweis Strategien vorgestellt: Einmal "Greedy stays ahead" und "Greedy Exchangeargument".

Ich wollte diese Beweise gerne mit "Greedy stays ahead" führen.

Der erste Schritt dieses Beweises ist es ja erstmal eine Lösung zu konstruieren (was ich bereits getan habe). Im zweiten Schritt soll man ein "Measure" finden.

Hier stellt sich meine Frage:

Soll ich mir hier einen beliebigen "Non" Greedy Algorithmus ausdenken? Also beispielsweise man soll Aufgaben schedulen und die Aufgaben habe eine verschiedene Arbeitsdauer. Somit wäre mein Greedy Algorithmus ja die Aufgaben erstmal aufsteigend nach Arbeitszeit zu sortieren um so viele wie möglich in einer gewissen Zeit abzuhandeln.

Der Comparison Algorithmus könnte dann also z.B. sein: Aufgaben absteigend nach Arbeitszeit sortieren und in dieser Reihenfolge abarbeiten? Und dann muss ich ich für alle Indizes zeigen, dass der Greedy Algorithmus immer besser ist ?
 

LimDul

Top Contributor
Ohne die konkrete Aufgabenstellung schwer. Aber dein Ansatz klappt nicht. Damit kannst du zeigen das der Greedy Algorithmus besser ist, als der andere - aber über Optimalität des Greedy sagt das nicht aus. Denn das müsstest du für jeden möglichen anderen Algorithmus zeigen.

Meist geht man den umgekehrten Weg. Man nimmt an, dass der Greedy Algorithmus nicht optimal ist. Und dann macht man darüber Schritt für Schritt Schlussfolgerungen. Was heißt nicht optimal? Es gibt eine Eingabemenge, wo der Algorithmus nicht die optimale Lösung berechnet hat. Was muss die Eingabemenge für Eigenschaften haben? usw. Und irgendwann kommt auf einen Widerspruch - man kommt zum Schluss, dass bei den Eigenschaften der Eingabemenge der Algorithmus doch das Optimum berechnet hätte - bzw. das so eine Eingabemenge nicht existieren kann.

Mal als simples Beispiel:
* Aufgabenstellung: Eingabe eine Menge N von natürlichen Zahlen. Ermittle die zwei Zahlen, die das größte Produkt bilden.
* Algorithmus: Sortiere die Menge und gibt die zwei größten Zahlen zurück. (z1 und z2)

Annahme: Das ist nicht das größte Produkt.

Schlussfolgerungen:
* Dann muss es zwei Zahlen geben n1 und n2, für die gilt: n1*n2 > z1*z2. Oder n1*n2 - z1*z2 > 0
* Mindestens eine dieser Zahlen muss unterschiedlich zu z1 & z2 sein. Sie dies n1
* Dann gilt n1 < z1 und n1 < z2. (Da z1 und z2 die größten Zahlen sind)
* Und damit ist laut Mathematik das Produkt n1*n2 kleiner als z1*z2
 

Kirby.exe

Top Contributor
Oh man xD Also hier ist die Aufgabenstellung:

Bildschirmfoto 2020-12-17 um 10.42.51.png

Mein Greedy Algorithmus ist dieser:
Sei M ein Array aller Jobs, C ein Array von nicht verwendeten Computern und sc der Supercomputer.

Code:
Sortiere M nach s_j aufsteigend;
while(!M.isEmpty()){
    füge alle unbenutzten PC's wieder in C ein;
    sc.runOp(M[0]);
    Warte bis sc berechnung beendet hat;
    C[0].runOp(M[0]);
    C.delete(0);
    M.delete(0);
}
 

Kirby.exe

Top Contributor
Somit könnte ich hier annehmen, dass mein Algorithmus nicht optimal ist und es eine Reihenfolge an Jobs gibt. Womit die Jobs schneller abgearbeitet werden können. Da aber die Menge M aufsteigend nach Arbeitszeit im Supercomputer sortiert ist, würde dies bedeuten dass die Sortierung falsch ist xD Weiter wüsste ich jetzt aber auch ned :(
 

LimDul

Top Contributor
Annahme: Dein Algorithmus ist nicht optimal.
* Das heißt der Abarbeitungsplang ist nicht optimal
* Das heißt, es gibt einen Abarbeitungsplan, der früher fertig ist. (Kleinere Fertigstellungszeit)
* Wie ermittelt sich die Fertigstellungszeit:
** Die Jobs müssen alle auf dem Supercomptuer berechnet wurden sein
** Jeder Job wurde auf einem PC fertigestellt
* Randbedingungen
** Die Reihenfolge der Jobs auf dem Supercomputer hat keinen Einfluss daran, wie lang es dauert, bis alle Jobs auf dem Supercomputer durch sind. Da die dort squentiell abgearbeitet werden.

Wenn dein Plan nicht optimal ist, bedeutet es, dass es einen anderen Plan gibt, der schneller fertig ist. Das heißt, in dem Plan gibt es mindestens einen Job, der früher auf den Supercomputer gegeben wird, als in deinem Plan. Dafür muss es aber auch einen anderen Job geben, der im optimalen Plan später auf den Supercomputer gegeben wurde als in deinem Plan.

Und jetzt musst du - mit den Eigenschaften deines Greedy Algorithmus versuchen zu beweisen - dass durch die Fertigstellungszeit nur steigen kann.
 

Neue Themen


Oben