Dynamische Programmierung (DP)

Dies ist eines der Probleme, die bei Programmierwettbewerben wie LeetCode und AtCoder häufig auftreten. Wenn Sie mit Round-Robin (blaue Kraft) codieren, wird dies zu einem exponentiellen Rechenaufwand (z. B. $ O (2 ^ n) $ ). Sie können den Umfang der Codeberechnung erheblich reduzieren (z. B. $ O (n ^ 2) $ usw.). Daher denke ich, dass es ein Konzept ist, das nicht nur für Programmierwettbewerbe, sondern auch für die alltägliche Codierung nützlich sein kann.

Hinweis)

Dieser Artikel beschreibt das Verfahren für Anfänger, um mithilfe dynamischer Planung algorithmische Probleme in einer begrenzten Zeit zu lösen. Daher betonen wir die Leichtigkeit des Verstehens in kurzer Zeit und geben keine strenge mathematische Erklärung.
Pseudocode ist in Python geschrieben. Darüber hinaus verwenden verwandte Begriffe die Beschreibung von Wikipedia.
Für diejenigen, die systematisch wissen möchten, hier und wikipedia Es wird in% E7% 9A% 84% E8% A8% 88% E7% 94% BB% E6% B3% 95) erklärt.
Dieser Artikel bezieht sich auch auf MIT Lecture. Sehr leicht zu verstehen und zu empfehlen.

Warum dynamische Planung auf den ersten Blick schwer zu verstehen ist

Dynamische Planung wird allgemein beschrieben als:

Zum Beispiel im Fall von wikipedia : ** Definition **

Der Algorithmus ist nicht im Detail definiert, sondern ein allgemeiner Begriff für Algorithmen, die die folgenden beiden Bedingungen erfüllen. ** Definition 1. ** Verwendung induktiver Beziehungen: Verwenden Sie die Lösungen kleinerer Problembeispiele (Teilprobleme) und Berechnungsergebnisse, um größere Problembeispiele mithilfe induktiver Beziehungen zu lösen. ** Definition 2. ** Berechnungsergebnisse aufzeichnen: Zeichnen Sie kleine Problembeispiele und Berechnungsergebnisse auf und vermeiden Sie es, dieselbe Berechnung zu wiederholen. Um in einer rekursiven Beziehung effizient zu referenzieren, werden die Berechnungsergebnisse mit Überschriften wie Ganzzahlen, Zeichen und deren Kombinationen verwaltet.

** Definition 2. ** In Bezug auf die Aufzeichnung von Berechnungsergebnissen können Sie intuitiv verstehen, dass die Berechnungsergebnisse zwischengespeichert werden. Ich denke, es ist intuitiv, sich Notizen zu machen, also nenne ich es "Memo".
Das Problem ist ** Definition 1. **, aber Anfänger können es schwierig finden, es zu verstehen.
Was ist ein kleineres Problembeispiel (Teilproblem)?
Warum können wir Teilprobleme verwenden, um größere Probleme (Probleme selbst) mithilfe induktiver Beziehungen zu lösen?
Wissen Sie, warum dynamische Planung verwendet werden kann?
Ich verstehe die Bedeutung des Wortes Dynamische Programmierung überhaupt nicht!
Herr Bellman, der den Begriff Dynamische Programmierung erfand, nannte ihn so, um seine mathematischen Forschungen vor dem Verteidigungsminister zu verbergen, der mittel- bis langfristige Forschungen hasste [^ 1]… Es ist eine Sache, daher ist es natürlich schwer zu verstehen: Schweiß:

Während wir diese Dinge erklären, werden wir uns das Verfahren zur Lösung des Problems der dynamischen Planung ansehen.

Dynamische Planungsmethode Verfahren zur Beantwortung von Fragen

Beispiel: Rucksackproblem

Nehmen Sie als Beispiel das berühmte Rucksackproblem. Problem: Du bist ein Dieb Ich schlich mich in einen Uhrenladen, um meine Uhr zu stehlen. Wenn das Array von Uhren durch $ S $ dargestellt wird, gibt es eine große Anzahl teurer Uhren mit verschiedenen Preisen bis zu $ S [0], ... S [i], ..., S [n-1] $. Ja, aber es gibt ein festes Gewicht von $ W $, das Sie mit nach Hause nehmen können. Wie kann ich den höchsten Gesamtpreis innerhalb der Beschränkungsgewichtsgrenze von $ W $ finden?

組み合わせ.png Abbildung 1 Rucksackproblem

Wenn Sie beispielsweise 1000 Uhren haben ($ n = 1000 $) und alle Uhrenkombinationen ausprobieren, werden Sie zwei Möglichkeiten für alle Uhren in Betracht ziehen, einschließlich oder nicht einschließlich jeder Uhr, also $ 2 ^ {n} = 2 ^ {1000} ≒ 10 ^ {301} $, was eine exponentiell enorme Menge an Berechnungen darstellt.

1. Stellen Sie fest, ob die dynamische Planung verwendet werden kann

Wenn Sie ein Problem innerhalb einer begrenzten Antwortzeit angehen, müssen Sie zunächst herausfinden, ob die dynamische Planungsmethode angewendet werden kann, um unnötige Überlegungen zu vermeiden. Daher geht es hier nicht darum zu beweisen, dass dynamische Planung angewendet werden kann, sondern darum, eine Vorstellung davon zu bekommen, ob dynamische Planung in kurzer Zeit auf dieses Problem angewendet werden kann.

Ob nun die dynamische Planungsmethode angewendet werden kann, ist, ob das, was in der Definition geschrieben ist, angewendet werden kann oder nicht. Wie kann ich das überprüfen? Es ist ein Kandidat für eine dynamische Planung, wenn die folgenden ** Bedingungen I. ** und ** Bedingungen II. ** wahrscheinlich in den ersten Minuten gefunden werden.

Bedingung I. Teilproblem kann gelöst werden

Nach ** Definition 1. ** ist es wichtig, Teilprobleme durch Zerlegung großer Problembeispiele lösen zu können. Was für einen Fall bedeutet dieses "Teilproblem kann gelöst werden"? Das heißt, wenn $ S $ ein Array von Eingabedaten ist, kann eine Lösung für einen Teil von $ S $ unter den gleichen Bedingungen wie die gesamte Lösung gefunden werden.

Insbesondere im Rucksackproblem, wenn beispielsweise nur die Uhren nach $ i $ (= $ S [i:] $) aus den vielen Uhren (= $ S $) im Uhrengeschäft betrachtet werden, z. Dies bedeutet, dass Sie den maximalen Gesamtpreis finden können, der unter der Bedingung einer Gewichtsbeschränkung von $ w $ in einen Rucksack passt. Wir schreiben $ V [i :, w] $ als den Wert, der auf diese Weise maximiert oder minimiert werden soll. Im Fall des Rucksackproblems ist $ V [i :, w] $ der Gesamtpreis nach der Uhrennummer $ i $ ($ i bis n $), wenn die verbleibende Gewichtsgrenze für die Eingabe des Rucksacks $ w $ beträgt. Obwohl der Rechenaufwand enorm ist, ist $ V [i :, w] $ ein Round-Robin-Ansatz (blaue Kraft), wie in der Erläuterung des Beispiels beschrieben, und alle Kombinationen von Uhren mit einer Gewichtsgrenze von $ w $ oder weniger können berücksichtigt werden. Wenn ja, kann es als der Wert mit dem größten Gesamtpreis berechnet werden. Daher scheint diese Bedingung erfüllt zu sein.

Ein Teil der Sequenz sind die folgenden drei Arten von Teilsequenzen.

$ S [: i] $ -Array-Präfix
$ S [i:] $ -Array-Suffix (Suffix)
$ S [i: j] $ -Subarray

Diesmal wird als Beispiel der Fall des Suffixes $ S [i:] $ -array (Suffix) verwendet.

Bedingung II. Das Problem kann rekursiv gelöst werden

Zweitens muss bestätigt werden, ob das Teilproblem, das durch ** Bedingung I ** gelöst werden kann, rekursiv gelöst werden kann. Dies wird in Definition 1 als "induktive Beziehung" bezeichnet. Die Tatsache, dass es rekursiv gelöst werden kann, bedeutet, dass zum Beispiel, wenn der maximale Gesamtpreis bis zu $ S [i:] $ durch $ V [i:] $ ausgedrückt wird, eine Beziehung besteht, die durch die folgende allmähliche Gleichung ausgedrückt werden kann. Es ist eine Sache.

$ V [i:] = V [i + 1:] + v_ {i + 1} $ ($ v_ {i + 1} $ ist eine Konstante) ・・・ ①

Mit anderen Worten, wenn Sie erraten können, dass $ V [i:] $ wahrscheinlich anhand des Berechnungsbetrags $ O (1) $ unter Verwendung von $ V [i + 1:] $ berechnet wird, ist dies in diesem Stadium gut.

Im Fall des Rucksackproblems wird es in diesem Stadium angesichts der Gewichtsbeschränkung etwas kompliziert. Ignorieren Sie es also und denken Sie, dass $ v_ {i} $ der Preis der Uhr $ i $ ist. Sie können den Maximalwert von finden. Da die Gewichtsbeschränkung ignoriert wird, handelt es sich lediglich um den Gesamtpreis aller Uhren. Angesichts der späteren Gewichtsbeschränkung konnten wir jedoch eine rekursive Beziehung bestätigen, sodass sie sich zu diesem Zeitpunkt in Zustand II befindet. Angenommen, Sie haben eine Ahnung.

2. Denken Sie an eine rekursive Funktion (oder einen allmählichen Ausdruck).

Bisher bin ich durch die Prüfung der obigen ** Bedingung I. ** und ** Bedingung II. ** in kurzer Zeit zu dem Schluss gekommen, dass dieses Problem wahrscheinlich durch die dynamische Planungsmethode gelöst wird. Daher betrachten wir schließlich einen Algorithmus, der dynamische Planung verwendet. Zur Erläuterung unten werde ich zuerst den Code und dann den Code schreiben, aber wenn Sie das eigentliche Problem lösen, können Sie aus dem Code denken. In meinem Fall ist der Code leichter zu denken als der Ausdruck, und am Ende ist es der Code, der zur Lösung des Problems benötigt wird, also denke ich von Anfang an.

Für ** Bedingung II. ** formulieren wir es unter Berücksichtigung der Gewichtsgrenze. Da wir diesmal an ein partielles Array = Suffix denken, betrachten wir zum Beispiel jede Uhr $ S [i] $ in absteigender Reihenfolge von $ i = n-1 $ bis $ i = 0 $. Wie bereits erwähnt, müssen Sie überlegen, ob Sie die Uhr $ i = n-1 $ zuerst in den Rucksack stecken möchten oder nicht. In der Formel kann ① wie folgt erweitert und ausgedrückt werden. Wenn Sie eine $ i = n-1 $ Uhr in einen Rucksack stecken möchten: $ V [n-2 :, w] = V [n-1 :, w-weight_ {n-1}] + value_ {n-1} $ ・・・ ③ Wenn Sie $ S [n-1] $ nicht in den Rucksack stecken: $ V [n-2 :, w] = V [n-1 :, w] $ ‥ ‥ ④ Wobei $ weight_ {n-1} $ das Gewicht der Uhr $ n-1 $ und $ value_ {n-1} $ den Preis darstellt.

Sobald $ V [n-2 :, w] $ aus der obigen Formel erhalten wird, betrachten Sie als nächstes die Fälle, in denen i = n-2 für jeden der Fälle ③ und ④ in den Rucksack gelegt wird oder nicht.

Um diese Beziehung auf alle $ i = 0, ..., n-1 $ anzuwenden, werden die Formeln ③ und ④ verallgemeinert, indem sie durch $ n-2 = i, n-1 = i + 1 $ ersetzt werden. Dann können Sie schreiben: So legen Sie $ S [i + 1] $ in den Rucksack: $ V [i :, w] = V [i + 1 :, w-weight_ {i + 1}] + value_ {i + 1} $ ・・・ ⑤ Wenn Sie $ S [i + 1] $ nicht in den Rucksack stecken: $ V [i :, w] = V [i + 1 :, w] $ ‥ ‥ ⑥

Bitte beachten Sie, dass das Gewichtslimit von $ w $ durch das Gewicht der Uhr im Rucksack reduziert wird.

Wenn Sie dies als Python-Code schreiben, sieht es folgendermaßen aus: (* Hier wird der Übersichtlichkeit halber der direkte Ausdruck in einen Code umgewandelt, und in Wirklichkeit müssen die Randbedingungen usw. berücksichtigt werden.)

# weight:Gewicht jeder Uhr:
#Beispiel)weight = [10, 20, 30, 35]
# value:Preis jeder Uhr=
#Beispiel)value = [5,12,17,20]

def V(i, w):
  #Beim Einbeziehen der Uhr i:
  if w >= weight[i]:
    V1 = V(i+1, w-weight[i]) + value[i]    
  #Wenn Uhr ich nicht enthalten ist:
  V2 = V(i+1, w)

Wir haben zwei graduelle Formeln, aber unter Berücksichtigung von ** Bedingung I. ** können wir die beiden graduellen Formeln zu einer kombinieren.

3. Erstellen Sie eine rekursive Funktion (vorläufiger Ausdruck), die ein Teilproblem löst

In ** Bedingung I. ** dachte ich, dass es möglich ist, den maximalen Gesamtpreis unter der Gewichtsgrenze von $ w $ durch Round-Robin (blaue Kraft) bis zur Uhrennummer $ i $ zu finden. Und es sollte möglich sein, es auch unter Verwendung der allmählichen Gleichung zu finden. Wenn es zwei Werte des Gesamtpreises $ V [i :, w] $ wie in den Gleichungen ⑤ und ⑥ gibt, kann der mit dem kleineren Gesamtpreis der Maximalwert sein, wenn die Gewichtsgrenze $ w $ gleich ist. Da es so etwas nicht gibt, kann sofort festgestellt werden, dass es unnötig ist. Daher können die beiden allmählichen Gleichungen (5) und (6) in den folgenden Gleichungen zusammengefasst werden. $ V [i :, w] = max (V [i + 1 :, w-Gewicht_ {i + 1}] + Wert_ {i + 1} $, $ V [i + 1 :, w] $) ・・・ ⑦

Jetzt haben Sie die Formel, um den Maximalwert des Teilproblems zu ermitteln. In Python geschrieben sieht es so aus:

# weight:Gewicht jeder Uhr:
#Beispiel)weight = [10, 20, 30, 35]
# value:Preis jeder Uhr=
#Beispiel)value = [5,12,17,20]

def V(i, w):
  #Beim Einbeziehen der Uhr i:
  V1 = 0
  if w >= weight[i]:
    V1 = V(i+1, w-weight[i]) + value[i]    
  #Wenn Uhr ich nicht enthalten ist:
  V2 = V(i+1, w)
  return max(V1, V2)

Jedes Mal, wenn $ V (i, w) $ aufgerufen wird, betrachten wir sowohl mit als auch ohne die Uhr $ i $, aber die mit der gleichen Gewichtsgrenze von $ w $ oder weniger und dem kleineren Gesamtpreis ist der maximale Gesamtpreis. Da dies niemals der Fall sein wird, wird nur derjenige mit dem höheren Gesamtpreis als Rückgabewert von $ max () $ festgelegt. Daraus können Sie ersehen, dass die Kombination, die nicht der Maximalwert sein kann, zum Zeitpunkt von $ i $ bestimmt werden kann.

Nehmen wir als konkretes Beispiel an, Sie haben einen Rucksack mit einer Gewichtsbeschränkung von $ W = 5 $ und der folgenden Uhr.

Uhr	0	1	2	3
Gewicht	2	4	2	3
Preis	12	20	10	17

Ein konkretes Beispiel für diesen rekursiven Funktionsaufruf ist in der folgenden Abbildung dargestellt.

再帰関数呼び出し.png Abbildung 2 Rekursiver Aufrufbaum

Der Funktionsaufruf der rekursiven Funktion erfolgt von oben nach unten, der Rückgabewert wird jedoch vom tiefsten Angerufenen zurückgegeben. Infolgedessen wird die Gewichtsgrenze von oben nach unten berechnet, wie durch den blauen Pfeil dargestellt, aber der Höchstpreis wird von unten nach oben berechnet, wie durch den roten Pfeil angezeigt. Jeder Knoten hat einen roten Pfeil von jedem der beiden unteren untergeordneten Knoten, aber der untergeordnete Knoten auf der rechten Seite hat eine $ i $ -Uhr im Rucksack und der untergeordnete Knoten auf der linken Seite hat $ V [ i :, w] Repräsentiert den Rückgabewert von $. Nur derjenige mit dem größeren Höchstpreis, der vom untergeordneten Knoten zurückgegeben wird, wird übernommen und an den oberen Knoten zurückgegeben, und schließlich wird der Höchstpreis 29 erhalten.

Übrigens verstehe ich, wie man den Maximalpreis erhält, ohne aufzurunden, indem man den allmählichen Ausdruck (rekursive Funktion) verwendet, aber das Memo von ** Definition 2. **, den Speicher Anstatt die Nutzung zu opfern, können Sie den Rechenaufwand reduzieren.

4. Machen Sie sich eine Notiz

Abbildung 2 In der Zeile $ i = 2 $ im rekursiven Aufrufbaum befindet sich ein von Purpur umgebener Knoten. Diese Knoten rufen zweimal $ V [i :, w] $ auf, was die gleiche Gewichtsgrenze von $ w $ wie die aktuelle Uhr $ i $ hat. Das heißt, da alle Berechnungen der untergeordneten Knoten von diesem Knoten gleich sind, können Sie die nachfolgenden Berechnungen weglassen, wenn Sie dies beim ersten Aufruf notieren. Wie viele Memogrößen benötigen Sie? Wenn das Gewicht aller Uhren eine Ganzzahl ist, beträgt der Bereich möglicher Werte für $ w $ $ 0 \ leq w \ leq W $, sodass W + 1-Memos erforderlich sind. Da der Bereich möglicher Werte für $ i $ $ 0 \ leq i \ leq n-1 $ ist, ist ein Wert von $ n $ erforderlich. Daher beträgt die Größe des Memos $ W × (n-1) $.

Bisher haben wir nicht die Randbedingung des Arrays berücksichtigt, sondern hier auch die Randbedingung des Arrays. In Python geschrieben sieht es so aus:


# weight:Gewicht jeder Uhr:
weight = [2, 4, 2, 3]
# value:Preis jeder Uhr:
value = [12,20,10,17]
n = len(value)
#Rucksackbegrenzungskapazität:
W = 5

#Sichere Notizen
memo = [[0] * (W+1) for _ in range(n)] 

def V(i, w):
  if i >= n:
    #Nach dem Ende des Arrays
    return 0

  if memo[i][w]:
    #Wenn im Memo
    return memo[i][w]

  #Beim Einbeziehen der Uhr i:
  V1 = 0
  if w >= weight[i]:
    V1 = V(i+1, w-weight[i]) + value[i]    
  #Wenn Uhr ich nicht enthalten ist:
  V2 = V(i+1, w)
  memo[i][w] = max(V1, V2)
  return memo[i][w]

V(0, W)

5. Bestätigung des Berechnungsbetrags

Wenn es bereits im Memo enthalten ist, müssen Sie es nicht berechnen, sodass Sie nur die rekursive Funktion für die Anzahl der Memos berechnen müssen. Daher beträgt der Berechnungsbetrag $ O (nW) $.

Es wird oft durch den Index der horizontalen Achsenanordnung, den Graphen oder die Tabelle des vertikalen Achsengewichts erklärt, aber für mich war es intuitiver, mit der rekursiven Funktion als Achse zu erklären, also gebe ich einen solchen Artikel zu Ich versuchte es.

[^ 1]: Von https://www.youtube.com/watch?v=OQ5jsbhAv_M

[PYTHON] So lösen Sie das Problem des dynamischen Planungsalgorithmus (von Anfängern gesehen)