Optimaler Unterbau

Question

Ich versuche, mir ein umfassenderes Bild von der Verwendung der optimalen Unterstruktureigenschaft in der dynamischen Programmierung zu machen, habe aber nicht verstanden, warum wir das beweisen müssen beliebig Die optimale Lösung des Problems enthält optimale Lösungen für die Teilprobleme.

Wäre es nicht genug, das zu zeigen? manche Soll die optimale Lösung des Problems diese Eigenschaft haben, und verwenden Sie diese dann, um zu argumentieren, dass die von unserem rekursiven Algorithmus erstellte Lösung mindestens so gut wie eine optimale Lösung ist und daher selbst optimal ist?Mit anderen Worten, ich kann nicht erkennen, wo wir im Korrektheitsargument unseres Algorithmus benötigen, dass alle optimalen Lösungen optimale Lösungen für Teilprobleme enthalten.

Um klarzustellen:

Die CLRS-Definition der optimalen Unterstruktur besagt, dass „ein Problem eine optimale Unterstruktur aufweist, wenn beliebig „Eine optimale Lösung des Problems enthält optimale Lösungen für Teilprobleme.“

Warum sollte es nicht ausreichen zu sagen, dass „ein Problem eine optimale Unterstruktur aufweist, wenn …“ manche „Enthält die optimale Lösung des Problems optimale Lösungen für Teilprobleme“?

Answer 1

Ich habe ein bisschen in meiner Forschung zu Annäherungsalgorithmen gestört, die dynamische Programme beinhaltet, die ungefähr optimale Lösungen finden. Der richtige Weg, um über die Richtigkeit dynamischer Programme nachzudenken, glaube ich, ist als Reduktion (in der Komplexitätstheorie-Sinne) von einem Problem zu einem Unterproblem. Diese Reduktion wird häufig rekursiv und mit Memoization aufgebracht, aber die sind jetzt Details.

lass ein Problem sein und b sein Unterproblem sein. Es gibt nur ein Unterproblem, da wir mehrere unabhängige Subprobleme über ein generalisiertes kartesisches Produkt kombinieren können. Die Reduktion besteht aus zwei Funktionen: f, von einer A-Instanz bis zu einer B-Instanz und H, von einer B-Lösung bis zu einer A-Lösung. Die Richtigkeitseigenschaft, die wir benötigen, ist für jede Funktion G von jeder B-Instanz zu einer entsprechenden optimalen B-Lösung (des Oracels), der Zusammensetzung H. g. F ist eine Funktion von jeder A-Instanz zu einer entsprechenden optimalen A-Lösung. (Wenn H Zugriff auf die A-Instanz benötigt, erweitern Sie B so, dass seine Instanzen eine A-Instanz enthalten, die ein Verbatim in die entsprechende B-Lösung kopiert werden muss.)

Um Ihren Punkt zu machen, für eine bestimmte A-Instanz und eine optimale A-Lösung muss kein Oracle G so vorhanden sein, dass die Pipeline H. g. f erzeugt diese Lösung aus der angegebenen Instanz. (Mit anderen Worten, H muss nicht surjektiv sein.) Andererseits muss H jeder mögliche optimale B-Lösung von G für die B-IN-Instanz von F c auftreten können.

Eine gemeinsame Strategie, um sicherzustellen, dass H korrekt ist, besteht darin, eine "Unterkonstruktion" -Funktion K von A-Lösungen zu B-Lösungen und einem Weg zum "Spleiß" -Substruktur zu finden, dh ein Beweis dafür, dass er eine A-Lösung gegeben hat X und eine B-Lösung y Nein schlechter als k (x), gibt es eine A-Lösung x 'Nein schlechter als X, so dass k (x')= y. Dann kann h alles im inversen Bild unter k seines Eingangs optimieren. Es ist nicht notwendig, dass das Spleißen für alle Lösungen x, nur ein optimales Anwenden.

Answer 2

Bei der dynamischen Programmierung teilen wir das Problem in kleinere Teilprobleme auf, nehmen einige Manipulationen vor und liefern Antworten für eine größere Antwort – sehr ähnlich zum Rekursionsansatz (und keineswegs zufällig).

Wenn wir nun die Korrektheit eines solchen Algorithmus formal beweisen wollen, geschieht dies durch Induktion.Wir beweisen, dass unsere „Basisklausel“ korrekt ist (normalerweise sehr einfach), und gehen dann davon aus, dass jedes Problem, das kleiner als das aktuelle ist, ebenfalls optimal ist.Anschließend verwenden wir diese Hypothese, um die Richtigkeit unseres größeren Problems zu beweisen.

Wenn wir nicht wüssten, dass alle Lösungen optimal sind, wären wir nicht in der Lage zu beweisen, dass wir mit einem zusätzlichen Schritt die optimale Lösung für ein kleineres Problem in eine optimale Lösung für ein größeres Problem ändern könnten – es gäbe einfach nicht genügend Informationen dazu beweisen Sie diese Behauptung.

Wenn wir wüssten, dass einige der Teilprobleme eine optimale Lösung darstellen, würde es nicht ausreichen, sicherzustellen, dass die Verwendung dieses Teilproblems, für das wir eine optimale Lösung haben, tatsächlich diejenige ist, die wir benötigen, um die optimale Lösung für das größere Problem zu erhalten.

---

Werfen Sie zum Beispiel einen Blick auf knapsack und werfen wir einen Blick auf seinen DP-Schritt:

f(x,i) = max(f(x-weight[i],i-1) +val[i], f(x,i-1))

Wenn wir wüssten, dass nur einer von ihnen optimal ist, könnten wir nicht beweisen, dass der Algorithmus korrekt ist, da wir möglicherweise den „anderen“ Fall benötigt hätten, für den wir keine optimale Lösung haben.

Wenn wir wollten f(x,i-1) im max() - Es könnte die falsche Wahl gewesen sein.Indem wir sicherstellen, dass wir für alle Teilprobleme eine optimale Lösung haben, stellen wir sicher, dass dies nicht passieren kann.