🔀 🔏 👩🏾‍🎓 Das Buch „Perfekter Algorithmus. Gierige Algorithmen und dynamische Programmierung

Hallo habrozhiteli! In dem neuen Buch spricht Tim Rafgarden über gierige Algorithmen (das Planungsproblem, minimale Spannbäume, Clustering, Huffman-Codes) und dynamische Programmierung (das Rucksackproblem, Sequenzausrichtung, kürzeste Wege, optimale Suchbäume). In diesem Beitrag wird ein Auszug „Entwickeln eines gierigen Algorithmus“ vorgestellt.

Gierige Algorithmen scheinen für die Aufgabe der Arbeitsplanung gut geeignet zu sein, um die gewichtete Summe der Fertigstellungszeiten zu minimieren. Die Ausgabe hat eine iterative Struktur, in der die Arbeit einzeln verarbeitet wird. Warum nicht einen gierigen Algorithmus verwenden, der iterativ entscheidet, welcher Job als nächstes kommt?

Der erste Schritt unseres Plans besteht darin, zwei Sonderfälle des allgemeinen Problems zu lösen. Unsere Lösungen für diese Fälle werden zeigen, wie ein gieriger Algorithmus im allgemeinen Fall aussehen könnte. Dann beschränken wir die Domäne auf einen Kandidatenalgorithmus und beweisen, dass es dieser Kandidat ist, der das Problem richtig löst. Der Prozess, durch den wir zu diesem Algorithmus kommen, ist für das Erinnern wichtiger als der Algorithmus selbst; Dieser Vorgang ist wiederholbar und kann in Ihren eigenen Anwendungen verwendet werden.

13.3.1. Zwei Sonderfälle

Nehmen wir an, dass es für die Minimierung der gewichteten Summe der Fertigstellungstermine tatsächlich einen korrekten Greedy-Algorithmus gibt. Wie würde es aussehen, wenn wir annehmen, dass alle Werke die gleiche Länge (aber möglicherweise unterschiedliche Gewichte) oder umgekehrt das gleiche Gewicht (aber möglicherweise unterschiedliche Längen) haben?

13.2

(1) , ?
(2) , ?
) ;
) ;
) ;
) ;
( . 13.3.3.)

13.3.2.

Im Allgemeinen kann die Arbeit unterschiedliche Gewichte und Längen haben. Wann immer unsere beiden Faustregeln - kürzere Arbeit bevorzugen und mit höheren Gewichten arbeiten - das Glück haben, dass ein paar Jobs zusammenfallen, wissen wir, welche wir zuerst planen müssen (kürzer mit höheren Gewichten). Was aber, wenn diese beiden Regeln widersprüchliche Ratschläge geben? Was sollen wir mit einer kurzen Arbeit mit geringem Gewicht und einer langen Arbeit mit hohem Gewicht tun?

Was wird der einfachste gierige Algorithmus sein, der so funktioniert, wie er sollte? Jede Arbeit hat zwei Parameter, und der Algorithmus sollte beide betrachten. Die beste Option wäre, eine Formel zu entwickeln, die die Länge und das Gewicht jeder Arbeit zu einer einzigen Note (Beitrag) zusammenfasst, sodass Planungsarbeiten von der höchsten zur niedrigsten Note garantiert werden, um die Anzahl der gewichteten Fertigstellungstermine zu minimieren. Wenn eine solche Formel existiert, folgt aus unseren beiden besonderen Fällen, dass sie zwei Eigenschaften haben muss: (i) Wenn die Länge fest bleibt, sollte sie sich um das Gewicht der Arbeit erhöhen; (ii) Wenn das Gewicht fest bleibt, sollte es von der Länge der Arbeit abnehmen (denken Sie daran, dass je höher die Marke, desto besser). Verbringen Sie eine Minute mit dem Brainstorming mehrerer Formeln, die beide Eigenschaften haben.

Die vielleicht einfachste Funktion, die an Gewicht zunimmt und an Länge abnimmt, ist der Unterschied zwischen ihnen:
Vorschlag Nr. 1 für die Note des Werkes. Bild

Die angegebene Note könnte negativ sein, dies stellt jedoch keine Hindernisse für die konsequente Konstruktion von Werken von der höchsten bis zur niedrigsten Note dar . Es gibt jedoch viele andere Optionen. Zum Beispiel ist das Verhältnis zweier Parameter ein weiterer Kandidat:

Vorschlag Nr. 2 zur Bewertung der Arbeit. Bild

Diese beiden Funktionen zur Berechnung der Bewertung führen zu zwei verschiedenen gierigen Algorithmen.

GREEDYDIFF GREED DIFFERENCE

Planen Sie die Arbeit in absteigender Reihenfolge
(willkürlich das Zusammentreffen von Werten brechen).

GREEDYRATIO

( ).

So veranschaulicht bereits unsere erste Fallstudie das erste Thema des gierigen Paradigmas (Abschnitt 13.1.2): Es ist normalerweise nicht schwierig, mehrere konkurrierende gierige Algorithmen für eine Aufgabe vorzuschlagen. Aber welcher der beiden Algorithmen, falls vorhanden, ist richtig? Eine schnelle Möglichkeit, einen von ihnen auszuschließen, besteht darin, eine Instanz zu finden, in der zwei Algorithmen unterschiedliche Zeitpläne mit unterschiedlichen Werten der Zielfunktion anzeigen. Für jeden Algorithmus, dessen Ergebnisse in diesem Beispiel schlechter sind, können wir schließen, dass er nicht immer optimal ist. In zwei Sonderfällen mit gleichem Gewicht oder gleicher Länge funktionieren beide Algorithmen korrekt. Das einfachste mögliche Beispiel für den Ausschluss eines von ihnen kann ein Beispiel für eine Aufgabe sein, bei der zwei Werke unterschiedliche Gewichte und Längen haben.Infolgedessen planen beide Algorithmen, in entgegengesetzter Reihenfolge zu arbeiten. Das heißt, wir suchen nach zwei Werken, deren Reihenfolge im Unterschied das Gegenteil ihrer Reihenfolge in Bezug ist. Beispiel:

Die erste Arbeit hat ein größeres großes Verhältnis, Bild

aber einen größeren Unterschied (–2 vs. –1). Somit GreedyDiffplant der Algorithmus zuerst die zweite Arbeit, während der Algorithmus GreedyRatiodas Gegenteil plant.

ÜBUNG 13.3

Was ist die Summe der gewichteten Fertigstellungstermine in den Listen von den abgeleiteten GreedyDiffund Algorithmen, die jeweils GreedyRatio?

a) 22 und 23
b) 23 und 22
c) 17 und 17
d) 17 und 11
(Eine Lösung und Erklärung finden Sie in Abschnitt 13.3.3.)

Wir haben uns weiterentwickelt, indem wir den Algorithmus GreedyDiffvon weiteren Überlegungen ausgeschlossen haben. Das Ergebnis von Übung 13.3 führt jedoch nicht direkt dazu, dass der Algorithmus GreedyRatioimmer optimal ist. Soweit wir wissen, gibt es andere Fälle, in denen dieser Algorithmus einen nicht optimalen Zeitplan erzeugt. Sie sollten immer skeptisch gegenüber einem Algorithmus sein, der nicht von einem Beweis seiner Richtigkeit begleitet wird, auch wenn dieser Algorithmus in mehreren Testfällen das Richtige tut und gierigen Algorithmen äußerst skeptisch gegenübersteht.

In unserem Fall wird der Algorithmus GreedyRatiotatsächlich garantiert, um die Anzahl der gewichteten Fertigstellungstermine zu minimieren.

Satz 13.1 (die Richtigkeit des Algorithmus GreedyRatio) . Für jeden Satz positiver ArbeitsgewichteBei positiven Auftragslängen zeigt der Algorithmus GreedyRatioeinen Zeitplan mit der kleinstmöglichen Summe der gewichteten Fertigstellungstermine an.

Diese logische Aussage ist nicht offensichtlich, und Sie sollten ihm nicht vertrauen, ohne Beweise zu erhalten. In Übereinstimmung mit dem dritten Thema des gierigen Paradigmas (Abschnitt 13.1.2) nimmt dieser Beweis den gesamten nächsten Abschnitt ein.

, . .

. — , ( ). — , , , . «» ( ) , .

Das verbleibende Thema des gierigen Paradigmas ist die Einfachheit der Laufzeitanalyse (Abschnitt 13.1.2). Hier ist es natürlich. Der GreedyRatio-Algorithmus sortiert die Jobs nur nach Beziehung, was O (n log n) Zeit benötigt, wobei n die Anzahl der Jobs in der Eingabe ist (siehe Fußnote 1 auf S. 24).

13.3.3. Übungslösungen 13.2–13.3

Die Lösung für Übung 13.2 Die

richtige Antwort lautet: (a) . Nehmen wir zunächst an, dass alle n Jobs dieselbe Länge haben, z. B. 1. Dann hat jeder Zeitplan genau die gleichen Fristen - {1, 2, 3, ..., n} - und die einzige Frage ist, welche Art von Job erhalten wird Fertigstellungstermin und Frist. Unsere Semantik für Arbeitsgewichte impliziert sicherlich, dass Arbeiten mit größerem Gewicht kürzere Abschlusszeiten erhalten sollten, und dies ist wahr. Zum Beispiel möchten Sie keine Arbeit mit einem Gewicht von 10 Dritteln (mit einer Frist von 3) und mit einem Gewicht von 20 Fünftel (mit einer Frist von 5) planen. Sie sollten die Positionen dieser beiden Werke ändern, wodurch sich die Summe der gewichteten Fristen um 20 verringert (wie Sie selbst sehen können).

Der zweite Fall, in dem alle Werke das gleiche Gewicht haben, ist etwas dünner. Hier möchten Sie kürzere Arbeiten bevorzugen. Betrachten Sie beispielsweise zwei Jobs mit Einheitsgewicht und Längen von 1 und 2. Wenn Sie zuerst eine kürzere Arbeit planen, betragen die Fertigstellungstermine 1 und 3 mit insgesamt 4. In umgekehrter Reihenfolge sind die Fristen 2 und 3 mit dem schlechtesten Ergebnis 5. Im Allgemeinen sind die geplanten Die erste Arbeit trägt zur Fertigstellungszeit aller Arbeiten bei, da alle Arbeiten auf die Fertigstellung der ersten warten müssen. Wenn alle Dinge gleich sind, minimiert die Planung der kürzesten Arbeit zuerst diese negativen Auswirkungen. Der zweite Job trägt zu allen Fertigstellungsterminen mit Ausnahme des ersten Jobs bei, daher sollte der zweitkürzeste Job als nächstes geplant werden und so weiter.

Lösung von Übung 13.3

Die richtige Antwort lautet: (b). Der Algorithmus GreedyDiffplant zuerst einen zweiten Job. Die Frist für die Fertigstellung dieser Arbeit ist, Bild

während die Frist für die Fertigstellung einer anderen Arbeit die Bild

Summe der gewichteten Fristen für die Fertigstellung ist

Der Algorithmus GreedyRatioplant die erste Arbeit zuerst, was zu Fristen Bild

und einer Summe der gewichteten Fristen von führt

Da der Algorithmus GreedyDiffden optimalen Zeitplan für dieses Beispiel nicht berechnet, ist er nicht immer korrekt.

»Weitere Informationen zum Buch finden Sie auf der Website des Herausgebers.
» Inhalt
» Auszug

für Khabrozhiteley 25% Rabatt auf den Gutschein - Algorithmen

Nach Zahlung der Papierversion des Buches wird ein elektronisches Buch per E-Mail verschickt.

Das Buch „Perfekter Algorithmus. Gierige Algorithmen und dynamische Programmierung »

13.3.1. Zwei Sonderfälle

13.3.2.

13.3.3. Übungslösungen 13.2–13.3

More articles: