Eine Fallunterscheidung zur dynamischen Programmierung: Benötigtes Beispiel!

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$\Gamma(\mathbf{i})$$\mathbf{i}$$\Gamma$

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 hat$d$

$\qquad d(\mathbf{i}) = f(\mathbf{i}, \widetilde{\Gamma}_d(\mathbf{i}))$

mit , und eine (berechenbare) Funktion, die über .~ Γ d ( i ) = { ( j , d ( j ) ) | j ∈ Γ d ( i ) } f d ~ Γ$\mathbf{i} \in [0\dots m] \times [0\dots n]$$\widetilde{\Gamma}_d(\mathbf{i}) = \{(\mathbf{j},d(\mathbf{j})) \mid \mathbf{j} \in \Gamma_d(\mathbf{i}) \}$$f$$d$$\widetilde{\Gamma}_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:$\Gamma_d$

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.$\Gamma$$\Gamma$

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?

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+\epsilon)$

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,n-1)$$A(m-1,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.

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:

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.

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 × n$$M$$x$$M$

Antworten

Dies kann auf folgende rekursive Weise gelöst werden:

$k = \lceil{\frac{1+n}{2}}\rceil$$x$$m_{k,k}$$x<m_{k,k}$$m_{i,j}$$k\leq i\leq n$$k\leq j\leq n$$1/4$$x>m_{k,k}$$1/4$$\frac{3}{4} n^2$$x$$\left(\frac{3}{4}\right)^3 n^2$