Wie unterscheidet sich dynamische Programmierung von Brute Force?

19

Ich habe mich gerade mit dynamischer Programmierung befasst, als ich auf folgendes Zitat gestoßen bin

Ein dynamischer Programmieralgorithmus untersucht alle Möglichkeiten zur Lösung des Problems und wählt die beste Lösung aus. Daher können wir uns die dynamische Programmierung grob als intelligente Brute-Force-Methode vorstellen, die es uns ermöglicht, alle möglichen Lösungen durchzugehen, um die beste auszuwählen . Wenn der Umfang des Problems so ist, dass alle möglichen Lösungen möglich und schnell genug durchlaufen werden, garantiert die dynamische Programmierung, dass die optimale Lösung gefunden wird

Das folgende Beispiel wurde gegeben

Angenommen, Sie müssen in einer bestimmten Stadt während der Hauptverkehrszeit so schnell wie möglich von Punkt A nach Punkt B gelangen. Ein dynamischer Programmieralgorithmus untersucht den gesamten Verkehrsbericht und alle möglichen Kombinationen von Straßen, die Sie nehmen könnten, und zeigt Ihnen dann an, welcher Weg der schnellste ist. Natürlich müssen Sie möglicherweise eine Weile warten, bis der Algorithmus abgeschlossen ist, und erst dann können Sie losfahren. Der Weg, den Sie einschlagen werden, ist der schnellste (vorausgesetzt, dass sich in der äußeren Umgebung nichts geändert hat).

Brute Force versucht jede mögliche Lösung, bevor es sich für die beste Lösung entscheidet.

Was unterscheidet Dynamic Programming von Brute Force, wenn es auch alle möglichen Lösungen durchläuft, bevor es die beste auswählt . Der einzige Unterschied, den ich sehe, ist, dass Dynamic Programming die zusätzlichen Faktoren (in diesem Fall die Verkehrsbedingungen) berücksichtigt.

Bin ich richtig zu sagen, dass Dynamic Programming eine Teilmenge der Brute-Force-Methode ist?

Computerfreak
quelle
1
Die Verkehrsverhältnisse sind ein roter Hering. Sie können sie in jedem Algorithmus berücksichtigen.
Yuval Filmus
Verwandte Antwort .
Raphael
Ihr erstes Zitat definiert keine dynamische Programmierung.
Reinierpost
@reinierpost Nun, es versucht , dorthin zu gelangen intelligent, brute force, vergisst dann aber, den "intelligenten" Teil zu beschreiben
Izkata
@Izkata Nach dieser Überlegung ist jeder Algorithmus "intelligente rohe Gewalt" (die ohnehin ein Oxymoron ist).
Raphael

Antworten:

17

Ein dynamischer Programmieralgorithmus untersucht alle Möglichkeiten zur Lösung des Problems und wählt die beste Lösung aus.

Diese Aussage ist einfach falsch.

Dynamische Programmierung Rezidive hat (oft) berücksichtigt alle möglichen Wege , um die gegebene Probleminstanz in kleinere Instanzen nach einem gewissen Schema aufgeteilt. Es werden jedoch nicht alle Lösungen für alle Teilprobleme miteinander kombiniert und die besten ausgewählt - es werden nur optimale Teillösungen kombiniert (und die besten ausgewählt).

Die Tatsache, dass dies eine optimale Lösung für das ursprüngliche Problem ergibt, ist nicht trivial und gilt in der Tat nur für einige Probleme. Und zwar diejenigen, die das Bellman-Prinzip der Optimalität erfüllen (eine der fischartigsten, missverstandenen "Definitionen", die regelmäßig zitiert werden). Sehen Sie hier für einige weitere Gedanken daran.

Als ein konkretes Beispiel sei die Bellman-Ford - Algorithmus auf einem vollständigen Graphen mit Wichten: es hält immer nur Wege der Länge eins und zwei (dh Θ ( n 2 ) viele) , weil jene eine Kante alle optimal verwenden . Aber es gibt unendlich viele Lösungen, wenn Sie nicht die maximal zulässige Anzahl von Kanten gebunden haben und trotzdem ( n - 1 ) ! viele, wenn Sie zulassen, dass jeder Knoten nur einmal verwendet wird. So klar, Bellman-Ford - ein dynamischer Programmieralgorithmus - nicht nicht führen eine Brute-Force-Methode.KnΘ(n2)(n-1)!

Raphael
quelle
"Diese Aussage ist einfach falsch" - Fix it .
Nmclean
4
@nmclean Meine Erfahrung mit der Bearbeitung algorithmischer Artikel in Wikipedia war alles andere als angenehm, also nein. Ich würde lieber meine Zeit hier investieren.
Raphael
Ich habe mein Glück versucht und den Artikel bearbeitet. Hoffe, es ist jetzt ein bisschen weniger falsch.
C4stor
9

Dynamische Programmierung ist clever, da sie Berechnungen wiederverwendet , Brute Force jedoch nicht. Nehmen wir an, Sie müssen zur Lösung von f (6) 2 Unterprobleme lösen, die beide f (3) nennen. Die Brute-Force-Methode berechnet f (3) zweimal, wodurch Aufwand verschwendet wird, während die dynamische Programmierung es einmal aufruft und das Ergebnis speichert, falls zukünftige Berechnungen es verwenden müssen. Bei vielen Problemen verbessert die Dynamik die exponentielle Komplexität von Brute Force zu Polynomkomplexität.

Tushar
quelle
9
Das ist Memoization , das ist nur einer von vielen Tricks, die DP anwendet.
Ben Voigt
4
Brute Force mit Auswendiglernen ist immer noch ineffizient. Nur zusätzliche Struktur / Beschneidung, die durch DP-Wiederholungen bereitgestellt wird, zahlt sich aus.
Raphael
3
Ich weiß nichts über dynamisches Programmieren, aber ich bin mir ziemlich sicher, dass es mehr als nur das Hinzufügen von Caches zu einem Brute-Force-Algorithmus gibt. Ich denke, dynamische Programmierung vermeidet es, jede mögliche Kombination zu testen, indem sie den Problemraum unterteilt, eine optimale Lösung für jede kleine Unterteilung findet und sie dann kombiniert, um eine insgesamt beste Lösung zu schaffen. (Möglicherweise wird dies rekursiv durchgeführt und die Unterteilungen werden untergliedert.) Dies funktioniert nur, wenn Sie das Problem so ausdrücken können, dass eine Kombination solcher Lösungen möglich ist und dennoch ein Gesamtoptimum erzielt wird.
Jonathan Hartley
1
Diese Antwort ist eigentlich ziemlich genau. Ich empfehle, ein Lehrbuch wie Cormen et al. Zu lesen: "Introduction to Algorithms" (Einführung in Algorithmen), um mehr über dynamisches Programmieren zu erfahren. Dieses Buch enthält ein recht anständiges Kapitel. Kurz gesagt, eine effiziente dynamische Programmierung nutzt zwei Eigenschaften des (Optimierungs-) Problems, das Sie lösen möchten: Optimale Lösungen können aus den optimalen Lösungen kleinerer Teilprobleme konstruiert werden, und die Gesamtzahl kleinerer Teilprobleme ist tatsächlich eher klein. Anschließend können Sie alle Teilproblemlösungen von unten nach oben erstellen und die Berechnung auf Kosten des Arbeitsspeichers beschleunigen.
MRA
Oder noch einfacher ausgedrückt: Wenn Sie wissen, wie man einen Binomialkoeffizienten mit dem Pascalschen Dreieck berechnet , wissen Sie alles, was Sie jemals über dynamische Programmierung wissen müssen.
MRA
3

Der Wikipedia-Artikel versucht möglicherweise, drei Arten von Algorithmen zu unterscheiden:

  1. Algorithmen, die alle möglichen Lösungen durchgehen und die optimale auswählen.

  2. Algorithmen, die eine Teilmenge aller möglichen Lösungen durchlaufen, so gewählt, dass die optimale Lösung zur Teilmenge gehört.

  3. Algorithmen, die eine Teilmenge aller möglichen Lösungen durchlaufen, ohne die Garantie, dass die optimale Lösung zur Teilmenge gehört.

Die ersten beiden Arten von Algorithmen erzeugen die optimale Lösung, während die dritte Art darauf abzielt, eine "gute" Lösung anstelle einer optimalen Lösung zu erzeugen. Meiner Meinung nach ist die Unterscheidung zwischen den ersten beiden Arten nicht so eindeutig.

Lassen Sie mich zunächst einfache Beispiele für alle drei Arten von Algorithmen im Kontext des kürzesten Pfades (das von Ihnen angegebene Beispiel) geben.

  1. Versuche alle möglichen Pfade. Dies wird als Brute Force bezeichnet .

  2. Probieren Sie alle möglichen Pfade aus und behalten Sie die bisherige Mindestlösung im Auge. Wenn der aktuelle Pfad, den Sie erstellen, teurer ist als die bisherige Mindestlösung, geben Sie ihn auf und wählen Sie einen anderen aus (wir gehen davon aus, dass die Entfernung segmentweise berechnet wird). Dies wird als Beschneiden bezeichnet .

  3. Schauen Sie sich die Karte an, überlegen Sie sich ein paar Wege und wählen Sie den besten aus. Dies ist ein Algorithmus für einen Menschen und nicht für einen Computer.

Diese Beispiele sind ziemlich grob und zeichnen möglicherweise kein sehr genaues Bild. Das Beschneiden ist in vielen Situationen von entscheidender Bedeutung, beispielsweise beim Computerschach. Wenn Sie neugierig sind, schlagen Sie den A * -Algorithmus nach , der tatsächlich für den kürzesten Weg verwendet wird.

Dynamische Programmierung ist eine Technik, um den Brute-Force-Algorithmus erheblich zu beschleunigen. Es ist jedoch etwas irreführend, dies so zu sehen. Es ist eine algorithmische Technik zur Lösung von Optimierungsproblemen. Sie können das Bereinigen im Kontext der dynamischen Programmierung implementieren.

ttt+1t

Yuval Filmus
quelle
Und dann wird ein Kandidat aus der Prüfung entfernt, ohne ihn vollständig zu verarbeiten. Wenn Sie beispielsweise den Satz nicht negativer Zahlen mit der minimalen Summe finden, müssen Sie nicht jeden Satz vollständig summieren, sondern nur, bis die Summe die aktuell beste überschreitet. Dies ist eine ähnliche Idee wie beim Beschneiden, jedoch orthogonal. Die Kombination der beiden Ideen ergibt "branch-and-bound", wo ein Problem mit reduzierter Komplexität gelöst und zur Rechtfertigung des Beschneidens verwendet wird.
Ben Voigt
0

Dynamische Programmierung ist viel schneller als Brute Force. Brute Force kann exponentielle Zeit in Anspruch nehmen, während die dynamische Programmierung in der Regel viel schneller ist.

Die Analogie zur rohen Gewalt ist sehr locker. Dynamisches Programmieren ist kein Wundermittel, mit dem Sie jeden gewünschten Brute-Force-Algorithmus anwenden und effizienter gestalten können.

DW
quelle
5
Das ist eine Konsequenz, keine Erklärung.
Raphael
-2

Das ist unkompliziert. Dynamische Programmierung ist eine "Suchstrategie", die zusätzliche Faktoren verwendet, um eine Suche einzugrenzen. Wenn es keine Lösung in dem Suchraum ist, die dynamische Programmierung wird ( in der Regel) eine Suche durch jedes Element des Suchraumes. Dies bedeutet jedoch nicht, dass es sich um eine Brute-Force-Suche handelt.

keine Männer
quelle
"Wenn es im Suchraum keine Lösung gibt, durchsucht die dynamische Programmierung (normalerweise) jedes Element des Suchraums." - falsch, siehe meine Antwort.
Raphael
-2

Die Aussage, dass dynamisches Programmieren intelligente Brute Force ist, ist richtig, aber mit dieser Formulierung etwas schwer zu verstehen. Bei der dynamischen Programmierung geht es im Allgemeinen darum, ein Problem auf intelligente Weise in kleinere Teile zu zerlegen. Nachdem Sie das getan haben, werden Sie Brute Force anwenden, um jedes kleine Teil zu lösen, und dann werden Sie wieder Brute Force anwenden, um die Teile zu einer endgültigen Lösung zu kombinieren. Während man also definitiv sagen kann, dass dynamisches Programmieren eine Art Brute-Force-Lösung ist, liegt der Trick darin, wie man diese Brute-Force einsetzt.

Tal
quelle
1
"Sie werden brachiale Gewalt anwenden, um jedes kleine Stück zu lösen" - falsch. Normalerweise verwenden Sie denselben Ansatz rekursiv.
FrankW