DAA - Programowanie dynamiczne

Programowanie dynamiczne jest również wykorzystywane w problemach optymalizacji. Podobnie jak metoda dziel i rządź, programowanie dynamiczne rozwiązuje problemy poprzez łączenie rozwiązań podproblemów. Co więcej, algorytm programowania dynamicznego rozwiązuje każdy podproblem tylko raz, a następnie zapisuje odpowiedź w tabeli, unikając w ten sposób ponownego obliczania odpowiedzi za każdym razem.

Dwie główne właściwości problemu sugerują, że dany problem można rozwiązać za pomocą programowania dynamicznego. Te właściwości sąoverlapping sub-problems and optimal substructure.

Nakładające się podproblemy

Podobnie jak w przypadku podejścia „dziel i rządź”, programowanie dynamiczne również łączy rozwiązania podproblemów. Jest używany głównie tam, gdzie rozwiązanie jednego podproblemu jest potrzebne wielokrotnie. Obliczone rozwiązania są przechowywane w tabeli, więc nie trzeba ich ponownie obliczać. Stąd ta technika jest potrzebna tam, gdzie istnieje nakładający się podproblem.

Na przykład wyszukiwanie binarne nie ma nakładającego się problemu podrzędnego. Podczas gdy rekurencyjny program liczb Fibonacciego ma wiele nakładających się podproblemów.

Optymalna podstruktura

Dany problem ma optymalną właściwość podstruktury, jeśli optymalne rozwiązanie danego problemu można uzyskać za pomocą optymalnych rozwiązań jego podproblemów.

Na przykład problem Najkrótsza ścieżka ma następującą optymalną właściwość podstruktury -

Jeśli node x leży w najkrótszej ścieżce od węzła źródłowego u do węzła docelowego v, to najkrótsza ścieżka od u do v to połączenie najkrótszej ścieżki z u do xi najkrótsza ścieżka od x do v.

Standardowe algorytmy All Pair Shortest Path, takie jak Floyd-Warshall i Bellman-Ford, są typowymi przykładami programowania dynamicznego.