Warum Mergesort keine dynamische Programmierung ist

1. Die Stichworte hier sind "überlappende Teilprobleme" und "optimale Unterstruktur". Wenn Sie Quicksort oder Mergesort ausführen, zerlegen Sie Ihr Array rekursiv in kleinere Teile, die sich nicht überlappen. Sie arbeiten nie während einer bestimmten Rekursionsebene zweimal über dieselben Elemente des ursprünglichen Arrays. Dies bedeutet, dass keine Möglichkeit besteht, vorherige Berechnungen erneut zu verwenden. Auf der anderen Seite, DO beinhalten viele Probleme die gleichen Berechnungen über überlappende Untergruppen durchgeführt wird, und die nützliche Eigenschaft haben, dass eine optimale Lösung für ein Teilproblem wiederverwendet werden kann, wenn die optimale Lösung zu einem größeren Problem zu berechnen.

2. Dijkstra-Algorithmus ein klassisches Beispiel für die dynamische Programmierung, da es wieder verwendet, bevor Berechnungen der kürzeste Weg zwischen zwei Knoten A und Z zu entdecken sagen, dass eine unmittelbare Nachbarn sind B und C. Wir finden die kürzeste Weg von A nach Z durch Summieren der Entfernung zwischen A und B mit unserem berechneten kürzesten Weg von B nach Z; und tun, ähnlich den kürzesten Weg von C bis Z. zum Auffinden Dann wird der kürzeste Weg von A nach Z wird die kürzere dieser beiden Pfade sein. Die wichtige Erkenntnis dabei ist, dass wir die kürzesten Weg Berechnungen für Wege der Länge 2 wiederverwenden können, wenn die kürzesten Wege der Länge 3 die Berechnung, und so weiter. Dies führt zu einem viel effizienteren Algorithmus.

3. Die dynamische Programmierung verwendet werden kann, viele Arten von Problemen zu lösen - siehe Ссылка einige Beispiele.

1. Damit die dynamische Programmierung auf ein Problem angewendet werden kann, sollte

   vorhanden sein

   ich. Eine optimale Struktur in den Teilproblemen:

Dies bedeutet, dass, wenn Sie Ihr Problem in kleinere Einheiten aufteilen, diese kleineren Einheiten auch in noch kleinere Einheiten aufgeteilt werden müssen, um eine optimale Lösung zu finden. Bei der Zusammenführungssortierung kann beispielsweise ein Zahlenfeld sortiert werden, wenn wir es in zwei Unterfelder aufteilen, sortieren und kombinieren. Während Sie diese beiden Unterfelder sortieren, wiederholen Sie den gleichen Vorgang wie im vorherigen Satz. Eine optimale Lösung (ein sortiertes Array) ist also dann gegeben, wenn wir eine optimale Lösung für seine Teilprobleme finden (wir sortieren die Teilfelder und kombinieren sie). Diese Anforderung ist für die Zusammenführungssortierung erfüllt. Auch müssen die Teilprobleme unabhängig sein, damit sie einer optimalen Struktur folgen. Dies wird auch durch die Zusammenführungs-Sortierung erreicht, da die Lösungen der Teilprobleme nicht von den Lösungen der jeweils anderen betroffen sind. Zum Beispiel werden die Lösungen für die beiden Teile eines Arrays nicht von der anderen Sortierung beeinflusst.

ii. Überlappende Teilprobleme:

Dies bedeutet, dass beim Lösen der Lösung die von Ihnen formulierten Teilprobleme wiederholt werden und daher nur einmal gelöst werden müssen. Im Fall von merge sort wird diese Anforderung im Normalfall nur selten erfüllt. Ein Array von Zahlen wie 2 1 3 4 9 4 2 1 3 1 9 4 kann ein guter Kandidat für überlappende Teilprobleme für Merge-Sort sein. In diesem Fall kann die Lösung für das Teilproblem sort (2 1 3) in einer Tabelle gespeichert werden, um wiederverwendet zu werden, da sie während der Berechnung zweimal aufgerufen wird. Aber wie Sie sehen können, gibt es eine sehr geringe Chance, dass eine zufällige Reihe von Zahlen diese Art von einer wiederholten Erfindung haben wird. Es wäre also nur ineffizient, wenn wir eine dynamische Programmiertechnik wie Memoization für einen Algorithmus wie merge sort verwenden würden.

2. Nein. Dijkstras Algorithmus verwendet eine gierige Strategie.

3. Ja. Wenn ich Wikipedia hier zitieren darf, "Dynamische Programmierung ist in der Bioinformatik für die Aufgaben wie Sequenzausrichtung, Proteinfaltung, RNA-Strukturvorhersage und Protein-DNA-Bindung weit verbreitet." ^[1]

[1] Ссылка