Rozróżnienie przypadków w programowaniu dynamicznym: potrzebny przykład!

Od jakiegoś czasu pracuję nad programowaniem dynamicznym. Kanonicznym sposobem oceny dynamicznej rekurencji programowania jest utworzenie tabeli wszystkich niezbędnych wartości i wypełnienie jej wiersz po wierszu. Zobacz na przykład Cormen, Leiserson i in .: „Wprowadzenie do algorytmów” .

Skupiam się na opartym na tabeli schemacie obliczeń w dwóch wymiarach (wypełnianie wiersz po rzędzie) i badam strukturę zależności między komórkami, tj. Które komórki należy wykonać, zanim można obliczyć inny. Oznaczamy za pomocą zestaw wskaźników komórek, od których zależy komórka . Pamiętaj, że musi być wolna od cyklu.$\Gamma(\mathbf{i})$$\mathbf{i}$$\Gamma$

Abstrahuję od obliczonej faktycznej funkcji i koncentruję się na jej strukturze rekurencyjnej. Formalnie uważam, że nawrót jest programowaniem dynamicznym, jeśli ma taką formę$d$

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

z , i niektóre (obliczalne) funkcje, które nie używają inne niż przez .$\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$

Ograniczając ziarnistość do szorstkich obszarów (po lewej, u góry po lewej, u góry, u góry po prawej, ... w bieżącej komórce) należy zauważyć, że istnieją zasadniczo trzy przypadki (do symetrii i obrotu) dynamiczne rekurencje programowania, które informują o sposobie wypełnienia tabeli:$\Gamma_d$

Czerwone obszary oznaczają (nadmierne przybliżenia) . Przypadki pierwszy i drugi dopuszczają podzbiory, przypadek trzeci to najgorszy przypadek (do transformacji indeksu). Pamiętaj, że nie jest bezwzględnie wymagane, aby całe czerwone obszary były objęte ; niektóre komórki w każdej czerwonej części tabeli są wystarczające, aby pomalować ją na czerwono. Białe obszary są wyraźnie wymagane, aby nie zawierały wymaganych komórek.$\Gamma$$\Gamma$

Przykładami przypadku pierwszego są odległość edycji i najdłuższy wspólny podciąg , przypadek drugi dotyczy Bellman i Forda oraz CYK . Mniej oczywiste przykłady obejmują takie, które działają na przekątnych, a nie na rzędach (lub kolumnach), ponieważ można je obracać w celu dopasowania do proponowanych przypadków; zobacz odpowiedź Joe na przykład.

Jednak nie mam (naturalnego) przykładu dla przypadku trzeciego! Więc moje pytanie brzmi: jakie są przykłady przypadków / problemów z dynamicznym programowaniem w przypadku trzecim?

Istnieje wiele innych przykładów algorytmów programowania dynamicznego, które w ogóle nie pasują do Twojego wzorca.

• Najdłużej rosnący problem z podsekwencją wymaga tylko jednowymiarowej tabeli.

• Istnieje kilka naturalnych algorytmów programowania dynamicznego, których tabele wymagają trzech lub nawet więcej wymiarów. Na przykład: Znajdź biały prostokąt o maksymalnej powierzchni na mapie bitowej. Naturalny algorytm programowania dynamicznego wykorzystuje tabelę trójwymiarową.

• Ale co najważniejsze, programowanie dynamiczne nie dotyczy tabel ; chodzi o odwijanie rekurencji. Istnieje wiele naturalnych algorytmów programowania dynamicznego, w których struktura danych używana do przechowywania wyników pośrednich nie jest tablicą, ponieważ rozwijana rekurencja nie przekracza zakresu liczb całkowitych. Dwa proste przykłady to znalezienie największego niezależnego zestawu wierzchołków w drzewie i znalezienie największego wspólnego poddrzewa dwóch drzew. Bardziej złożonym przykładem jest algorytm aproksymacji dla problemu podróżnego sprzedawcy euklidesowego autorstwa Arory i Mitchella.$(1+\epsilon)$

Obliczanie funkcji Ackermanna jest w tym duchu. Aby obliczyć , musisz znać A ( m , n - 1 ) i A ( m - 1 , k ) dla niektórych dużych k . Druga współrzędna maleje lub pierwsza maleje, a druga potencjalnie wzrasta.$A(m,n)$$A(m,n-1)$$A(m-1,k)$$k$

Nie idealnie pasuje to do wymagań, ponieważ liczba kolumn jest nieskończona, a obliczenia zwykle wykonuje się z góry na dół z zapamiętywaniem, ale myślę, że warto o tym wspomnieć.

To nie pasuje dokładnie do przypadku 3, ale nie wiem, czy któryś z twoich przypadków wychwytuje bardzo częsty problem używany do nauczania programowania dynamicznego: mnożenie łańcucha macierzy . Aby rozwiązać ten problem (i wiele innych, to tylko kanoniczny), wypełniamy macierz diagonalnie po przekątnej zamiast rzęd po rzędzie.

Więc zasada jest taka:

Wiem, że to głupi przykład, ale myślę, że to prosty iteracyjny problem

Znajdź sumę liczb w macierzy kwadratowej

może się zakwalifikować. Tradycyjne „dla każdego wiersza dla każdej kolumny” wygląda jak twój przypadek 3.

To nie jest dokładnie to, czego szukasz, ale mam pomysł na czubek głowy, który może być pomocny.

Problem:

$n × n$$M$$x$$M$

Odpowiedź

Można to rozwiązać w następujący sposób rekurencyjny:

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