Programowanie dynamiczne

WPROWADZENIE

https://en.wikipedia.org/wiki/Dynamic_programming

https://medium.com/@codingfreak/top-50-dynamic-programming-practice-problems-4208fed71aa3

https://stackoverflow.com/questions/1065433/what-is-dynamic-programming

Programowanie dynamiczne jest techniką lub strategią projektowania algorytmów, stosowaną przeważnie do rozwiązywania zagadnień optymalizacyjnych. Jest alternatywą dla niektórych zagadnień rozwiązywanych za pomocą algorytmów zachłannych. Wynalazcą techniki jest amerykański matematyk Richard Bellman.

Programowanie dynamiczne ma na celu wykorzystanie zalet podejścia rekurencyjnego (prostota, przejrzystość) i eliminację jego wad (zasobożerność). Konstrukcja programu wykorzystującego zasadę programowania dynamicznego może być sformułowana w trzech punktach.

• Koncepcja: Dla danego problemu stwórz rekurencyjny model jego rozwiązania (wraz z jednoznacznym określeniem przypadków elementarnych).
• Inicjalizacja: Wpisz do tablicy wartości numeryczne, odpowiadające przypadkom elementarnym.
• Progresja: Na podstawie wartości numerycznych wpisanych do tablicy, używając formuły rekurencyjnej, oblicz rozwiązanie problemu wyższego rzędu i wpisz je do tablicy; postępuj w ten sposób do osiągnięcia podanej wartości.

Programowanie dynamiczne przypomina metodę dziel i zwyciężaj, ponieważ w obu metodach wykorzystujemy rekurencję. Jednak w metodzie dziel i zwyciężaj podproblemy są rozłączne (np. przy sortowaniu są to różne fragmenty tablicy). W programowaniu dynamicznym wykorzystujemy powtarzanie się podproblemów na kolejnych etapach rekurencji. Liczba istotnie różnych podproblemów jest wielomianowa, co wykorzystuje metoda programowania dynamicznego. W metodzie siłowej wiele razy rozwiązuje się te same problemy, co zwykle prowadzi do ponadwielomianowej złożoności.

Problem można rozwiązać metodą programowania dynamicznego, jeżeli ma dwie kluczowe właściwości.

1. Powtarzające się podproblemy (ang. overlapping subproblems). Podproblemy te rozwiązujemy tylko raz i zapamiętujemy ich rozwiązanie (ang. memoization).
2. Optymalna podstruktura (ang. optimal substructure). Problem ma własność optymalnej podstruktury, jeżeli może być rozwiązany z użyciem rozwiązań podproblemów. Inaczej mówiąc: optymalne rozwiązanie problemu zawiera w sobie optymalne rozwiązanie podproblemu.

CIĄG FIBONACCIEGO

Technika programowania dynamicznego może być zastosowana do problemu obliczania wyrazów ciągu Fibonacciego.

# Programowanie dynamiczne wstępujące, wersja z listą.
def fibonacci(n):
    F = [0] + n * [1]   # trzymamy wszystkie wartości
    for i in range(2, n+1):
        F[i] = F[i-1] + F[i-2]
    return F[n]

# Programowanie dynamiczne wstępujące, wersja ze słownikiem.
def fibonacci(n):
    F = {0:0, 1:1}   # trzymamy wszystkie wartości
    for i in range(2, n+1):
        F[i] = F[i-1] + F[i-2]
    return F[n]

W technice programowania dynamicznego zstępującego wartości obliczne są tylko wtedy, gdy są potrzebne.

# Programowanie dynamiczne zstępujące.
FIBONACCI = {0:0, 1:1}   # globalny słownik

def fibonacci(n):
    global FIBONACCI
    if n not in FIBONACCI:
        FIBONACCI[n] = fibonacci(n-1) + fibonacci(n-2)
    return FIBONACCI[n]

# Programowanie dynamiczne zstępujące.
# Słownik z wynikami ukryty w instancji klasy.
# Można wykorzystać wyniki z poprzednich wywołań funkcji.
class FibonacciClass:

    def __init__(self):
        self.cache = {0:0, 1:1}

    def __call__(self, n):
        if n not in self.cache:
            self.cache[n] = self(n-1) + self(n-2)
        return self.cache[n]

fibonacci = FibonacciClass()
print ( fibonacci(10) )
print ( fibonacci(20) )
print ( fibonacci.cache )   # podgląd zapamiętanych wyników

PROBLEM PLECAKOWY

Problem plecakowy (ang. knapsack problem) należy do problemów optymalizacyjnych. Wersja decyzyjna problemu plecakowego jest problemem NP-zupełnym i jest jednym z 21 NP-zupełnych problemów Karpa. Problem polega na znalezieniu takiego podzbioru elementów, aby suma wartości była jak największa, a suma wag nie była większa od danej pojemności plecaka. Nie można wybierać ułamkowch części elementów. Metody rozwiązywania problemu plecakowego.

• Przegląd zupełny (metoda siłowa) znajduje najlepsze rozwiązanie, ale ma złożoność wykładniczą O(2^n).
• Problem plecakowy może być rozwiązany przy użyciu programowania dynamicznego, ale rozwiązanie wielomianowe nie jest znane.
• Zachłanny algorytm aproksymacyjny sortuje elementy w kolejności malejącej porównując stosunek wartości do wagi elementu. Złożoność obliczeniowa algorytmu zależy od sortowania [zwykle O(n log n)].

Wikipedia, Knapsack problem, https://en.wikipedia.org/wiki/Knapsack_problem

PROBLEM CIĘCIA PRĘTA

Cormen s. 363.

Dynamic Programming — Rod Cutting Problem

http://algorithms.tutorialhorizon.com/dynamic-programming-rod-cutting-problem/

PROBLEM ŚCIEŻKI O MINIMALNYM KOSZCIE

Dynamic Programming — Minimum Cost Path Problem

http://algorithms.tutorialhorizon.com/dynamic-programming-minimum-cost-path-problem/

ALGORYTM KADANE'A

Problem znajdowania podmacierzy o maksymalnej sumie elementów. Oryginalna wersja algorytmu dotyczy macierzy jednowymiarowej, ale istnieją uogólnienia na większą liczbę wymiarów.

https://en.wikipedia.org/wiki/Maximum_subarray_problem

BIOINFORMATYKA

W bioinformatyce programowanie dynamiczne pojawia się w algorytmie Needlemana-Wunscha i innych algorytmach.

https://en.wikipedia.org/wiki/Needleman%E2%80%93Wunsch_algorithm

TEORIA GRAFÓW

Algorytm Dijkstry (najkrótsze ścieżki z jednego źródła, nieujemne wagi krawędzi). Jeżeli R znajduje się na najkrótszej ścieżce od P do Q, to znamy już najkrótsza ścieżkę od R do Q (optymalna podstruktura).

Algorytm Bellmana-Forda (najkrótsze ścieżki z jednego źródła, możliwe ujemne wagi krawędzi, brak ujemnych cykli).

Algorytm Floyda-Warshalla (najkrótsze ścieżki pomiędzy wszystkimi parami wierzchołków, możliwe ujemne wagi krawędzi, brak ujemnych cykli). Złożoność obliczeniowa to O(V^3). Wykorzystuje się relację rekurencyjną na najkrótsze ścieżki.

Algorytmy wykorzystujące drzewo dekompozycji grafu.