Eine Fallunterscheidung zur dynamischen Programmierung: Benötigtes Beispiel!

19

Ich arbeite seit einiger Zeit an dynamischer Programmierung. Die kanonische Methode zum Auswerten einer dynamischen Programmierrekursion besteht darin, eine Tabelle mit allen erforderlichen Werten zu erstellen und zeilenweise zu füllen. Siehe zum Beispiel Cormen, Leiserson et al .: "Introduction to Algorithms" für eine Einführung.

Ich konzentriere mich auf das tabellenbasierte Berechnungsschema in zwei Dimensionen (zeilenweise Füllung) und untersuche die Struktur von Zellabhängigkeiten, dh welche Zellen durchgeführt werden müssen, bevor eine andere berechnet werden kann. Wir bezeichnen mit die Menge der Indizes von Zellen, von denen die Zelle abhängt. Beachten Sie, dass zyklenfrei sein muss.i ΓΓ(i)ichΓ

Ich abstrahiere von der tatsächlich berechneten Funktion und konzentriere mich auf ihre rekursive Struktur. Formal halte ich eine Wiederholung für eine dynamische Programmierung, wenn sie die Form hatd

d(ich)=f(ich,Γ~d(ich))

mit , und eine (berechenbare) Funktion, die über .~ Γ d ( i ) = { ( j , d ( j ) ) | jΓ d ( i ) } f d ~ Γ dich[0m]×[0n]Γ~d(i)={(j,d(j))jΓd(i)}fdΓ~d

Wenn man die Granularität von auf raue Bereiche (links, links oben, rechts oben, ... der aktuellen Zelle) einschränkt, stellt man fest, dass im Wesentlichen drei Fälle (bis zu Symmetrien und Rotation) gültig sind Dynamische Programmierrekursionen, die angeben, wie die Tabelle gefüllt werden kann:Γd

Drei Fälle von Abhängigkeiten dynamischer Programmierzellen

Die roten Bereiche bezeichnen (Überapproximationen von) . In den Fällen eins und zwei werden Teilmengen zugelassen, in Fall drei ist der schlechteste Fall (bis zur Indextransformation). Beachten Sie, dass nicht unbedingt alle roten Bereiche von abgedeckt werden müssen . Einige Zellen in jedem roten Teil der Tabelle reichen aus, um sie rot zu zeichnen. Weiße Flächen sind explictly zu benötigt nicht enthalten alle erforderlichen Zellen.ΓΓ

Beispiele für den ersten Fall sind die Bearbeitungsentfernung und die längste gemeinsame Teilsequenz , für Bellman & Ford und CYK gilt der zweite Fall . Weniger offensichtliche Beispiele sind solche, die sich eher auf die Diagonalen als auf Zeilen (oder Spalten) beziehen, da sie gedreht werden können, um den vorgeschlagenen Fällen zu entsprechen. Siehe Joes Antwort für ein Beispiel.

Ich habe jedoch kein (natürliches) Beispiel für Fall drei! Meine Frage lautet also: Was sind Beispiele für drei dynamische Programmierrekursionen / -probleme?

Raphael
quelle
2
Fall 3 fasst die Fälle 1 und 2 zusammen.
JeffE
Nicht, tut es trotz des Aussehens nicht. Zum Beispiel kann ein Fall 1 Fall nicht eine gewünschte Zelle in dem linken oberen Bereich hat, während ein Fall 3 Beispiel hat eine gewünschte Zelle in dem linken oberen Bereich haben. Ich habe die Erklärung bearbeitet, um sie zu verdeutlichen.
Raphael

Antworten:

15

Es gibt viele andere Beispiele für dynamische Programmieralgorithmen, die überhaupt nicht zu Ihrem Muster passen.

  • Das am längsten zunehmende Folgeproblem erfordert nur eine eindimensionale Tabelle.

  • Es gibt mehrere natürliche dynamische Programmieralgorithmen, deren Tabellen drei oder mehr Dimensionen erfordern. Beispiel: Suchen Sie das weiße Rechteck mit der maximalen Fläche in einer Bitmap. Der natürliche dynamische Programmieralgorithmus verwendet eine dreidimensionale Tabelle.

  • Vor allem aber geht es bei der dynamischen Programmierung nicht um Tabellen . Es geht darum, die Rekursion zu lösen. Es gibt viele natürliche dynamische Programmieralgorithmen, bei denen die zum Speichern von Zwischenergebnissen verwendete Datenstruktur kein Array ist, da die Wiederholung, die abgewickelt wird, nicht über einen Bereich von ganzen Zahlen liegt. Zwei einfache Beispiele sind das Finden der größten unabhängigen Menge von Eckpunkten in einem Baum und das Finden des größten gemeinsamen Unterbaums von zwei Bäumen. Ein komplexeres Beispiel ist der -Näherungsalgorithmus für das euklidische Handelsreisendenproblem von Arora und Mitchell.(1+ϵ)

JeffE
quelle
Vielen Dank für Ihre Antwort, aber ich habe die Frage ausdrücklich auf zweidimensionale Probleme und das kanonische, tabellenbasierte Berechnungsschema (überarbeitet, um diesen Punkt noch klarer zu machen) beschränkt. Mir ist der allgemeinere Rahmen bekannt, aber ich bin an dieser Stelle nicht daran interessiert.
Raphael
9
Okay, aber ich denke wirklich, Sie verpassen den Punkt.
JeffE
Da es viele positive Stimmen gibt, dachte ich, ich sollte dies klarstellen: Dieser Beitrag beantwortet die Frage nicht und versucht es in der Tat nicht einmal.
Raphael
2
@ Raffael ist richtig. Meine "Antwort" ist keine Antwort, sondern eine Kritik an der Frage, aber sie war zu lang für einen Kommentar.
JeffE
3

Computing Ackermann Funktion ist in diesem Sinne. Um zu berechnen , müssen Sie A ( m , n - 1 ) und A ( m - 1 , k ) für ein großes k kennen . Entweder nimmt die zweite Koordinate ab oder die erste ab und die zweite potenziell ab.A(m,n)A(m,n1)A(m1,k)k

Dies passt nicht ideal zu den Anforderungen, da die Anzahl der Spalten unendlich ist und die Berechnung normalerweise von oben nach unten mit Auswendiglernen erfolgt, aber ich denke, es ist erwähnenswert.

sdcvvc
quelle
1
A(m1,A(m,n1))
1
Ich bin nicht sicher, warum diese Antwort abgelehnt wurde, da es sich um eine gute Antwort handelt. Die Ackermann-Funktion eignet sich hervorragend für die dynamische Programmierung. Im Allgemeinen eignet sich jede rekursiv definierte Funktion, die wiederholt für dieselben Argumente berechnet wird, für die dynamische Programmierung. Um dies zu sehen, muss man es nur implementieren und die Laufzeiten vergleichen. Was mit der normalen Ackermann-Funktion Jahre dauert, kann mit der dynamischen Programmierung Sekunden dauern.
Jules
@Jules: Das Problem für das kanonische Tabellenschema besteht darin, dass Sie a priori keine (primitive rekursive) Grenze für die Tabellengröße kennen. Natürlich kann man sich etwas merken, aber nicht ganz auf die übliche Weise. Also ja, es mag für DP lebensfähig sein, aber es passt nicht zu der Klasse von Problemen, mit denen sich meine Frage befasst.
Raphael
1
Ich denke nicht, dass es eine Voraussetzung für DP ist, dass die Tischgröße von vornherein festgelegt ist? Wie JeffE erwähnt, muss der Cache überhaupt kein Tisch sein. Es kann sich um eine beliebige assoziative Datenstruktur handeln. DP ist wirklich eine sehr sehr einfache Idee: Sie möchten eine rekursiv definierte Funktion berechnen, aber diese Funktion wird wiederholt mit denselben Argumenten aufgerufen. DP ist die Optimierung, bei der Sie einen Cache einführen, um sicherzustellen, dass Sie jeden Fall nur einmal berechnen. Es gibt viele Funktionen, die in keinen Ihrer Fälle passen, auch wenn sie Funktionen von zwei begrenzten ganzen Zahlen sind.
Jules
2

Dies passt nicht genau zu Fall 3, aber ich weiß nicht, ob einer Ihrer Fälle ein sehr häufiges Problem erfasst, das zum Lehren der dynamischen Programmierung verwendet wird: Matrix Chain Multiplication . Um dieses Problem zu lösen (und viele andere, dies ist nur das kanonische), füllen wir die Matrix diagonal nach diagonal statt zeilenweise auf.

Die Regel lautet also ungefähr so:

diagMatrix

Joe
quelle
1
So geschrieben passt es in der Tat auf keinen Fall. Wenn Sie jedoch im Uhrzeigersinn um 45 Grad drehen, erhalten Sie Fall 2 (und alle implizierten Eigenschaften). Dies gilt auch für andere Beispiele, die von der Diagonale in Richtung einer Ecke arbeiten. Aber danke, dass du es erwähnt hast!
Raphael
@Raphael es ist nicht sofort offensichtlich, dass diese äquivalent sind, vielleicht möchten Sie das in Ihrer Frage erwähnen.
Joe
0

Ich weiß, es ist ein albernes Beispiel, aber ich denke, ein einfaches iteratives Problem mag

Suchen Sie die Summe der Zahlen in einer quadratischen Matrix

qualifizieren könnte. Das traditionelle "für jede Zeile für jede Spalte" sieht aus wie in Ihrem Fall 3.

hugomg
quelle
-1

Dies ist genau nicht der Suchbereich, den Sie suchen, aber ich habe eine Idee von der Spitze meines Kopfes, die hilfreich sein könnte.

Problem :

n×nMxM

Antworten

Dies kann auf folgende rekursive Weise gelöst werden:

k=1+n2xmk,kx<mk,kmi,jkichnkjn1/4x>mk,k1/434n2x(34)3n2

0x0
quelle
1
Dies ist keine Instanz der dynamischen Programmierung, nicht wahr?
Raphael