Beim Entwurf von Algorithmen werden häufig die folgenden Techniken angewendet:
- Dynamische Programmierung
- Die Gier-Strategie
- Teilen und Erobern
Während es für die ersten beiden Methoden bekannte theoretische Grundlagen gibt, nämlich das Bellman-Optimalitätsprinzip und die Matroid- (bzw. Greedoid-) Theorie, konnte ich für Algorithmen, die auf D & C basieren, keinen solchen allgemeinen Rahmen finden.
Erstens ist mir etwas bekannt, das wir (oder besser gesagt der Professor) in einer funktionalen Programmierklasse eingeführt haben, die als "algorithmisches Skelett" bezeichnet wird und das im Kontext von Kombinatoren entstanden ist. Als Beispiel hierfür haben wir ein solches Grundgerüst für D & C-Algorithmen wie folgt angegeben:
Definition : Sei nicht leere Mengen. Wir nennen die Elemente von Lösungen und die Elemente von (dh die Teilmengen von ) werden als Probleme bezeichnet . Dann ist ein D & C-Gerüst ein 4-Tupel , wobei:S P : = P ( A ) , A ( P β , β , D , C )
- p P β ( p ) ist ein Prädikat über die Reihe von Problemen , und wir sagen , dass ein Problem ist Grund iff hält.
- P β → S ist ein Mapping , das jedem Grundproblem eine Lösung zuweist.
- P → P ( P ) ist eine Zuordnung , die jedes Problem in eine Reihe von Unterproblemen unterteilt.
- P × P ( S ) → S ist eine Abbildung , die die Lösungen (abhängig von der Art eines "Pivot-Problems") der Unterprobleme verbindet, um eine Lösung zu erhalten.
Dann berechnet für ein gegebenes Skelett und ein Problem die folgende generische Funktion eine Lösung (im Formalen) Sinn) für :p f s : P → S p
wobei wir in der zweiten Zeile die Notation für Teilmengen der Codomäne einer Abbildung .X f
Wir haben jedoch die zugrunde liegenden "strukturellen" Eigenschaften von Problemen, die auf diese Weise formuliert werden können, nicht weiter untersucht (wie gesagt, es war eine funktionale Programmierklasse und dies war nur ein kleines Beispiel). Leider konnte ich zu diesem Ansatz keine weiteren Hinweise finden. Daher denke ich nicht, dass die obigen Definitionen ganz normal sind. Wenn jemand erkennt, was ich oben angegeben habe, würde ich mich über verwandte Artikel freuen.
Zweitens haben wir für die Greedy-Strategie das berühmte Ergebnis, dass ein Problem durch den allgemeinen Greedy-Algorithmus genau dann korrekt gelöst wird, wenn seine Lösungen eine gewichtete Matroide darstellen. Gibt es ähnliche Ergebnisse für D & C-Algorithmen (die nicht unbedingt auf der oben beschriebenen Methode basieren)?
quelle