Dynamické programování

Pamatujete si na náš článek o funkcionálním programování? Na první pohled se může zdát, že popsané funkcionální principy, zejména neměnná data, mohou být omezující. V mnoha případech je to ale jen o zvyku, protože už jsme naučení na věci nahlížet tak, že to měnný stav vyžaduje. Existuje ale i další pohled, který může být i elegantnější a nevyžaduje měnitelný stav.

Zajímavým příkladem může být dynamické programování. To je postavené na dekompozici problému na opakující se podproblémy, u kterých si můžeme předpočítat výsledky. Zde by se mohlo zdát, že už z definice potřebujeme mít měnitelný stav. Musíme si alokovat paměť na uchování výsledků podproblému a ty si postupně ukládáme. Síla dynamického programování je v tom, že jsme schopni výsledek většího podproblému vyjádřit pomocí již vypočtených menších podproblémů. Tedy už při inicializaci známe výraz, kterým spočítáme problém pomocí podproblémů.

Lazy hodnoty

Zde přichází na řadu lazy hodnoty. Ty jsou zakořeněny ve funkcionálním programování z čistého lambda calculu, který je hojně využívá. Lazy hodnoty fungují tak, že do proměnné (resp. konstanty, protože máme neměnný stav) přiřadím výraz, který se spustí, až když danou hodnotu potřebujeme. Takhle můžeme nainicializovat klidně obrovský prostor a není to výpočetně náročné, nedochází k žádnému výpočtu. Dotaz na některou konkrétní lazy hodnotu poté spustí kaskádu mezivýpočtů, které jsou pro výpočet nutné. Skvělé na tom je, že výpočet se spustí pouze jednou. Jakmile se vypočte výsledná hodnota, tak další dotaz na tuto hodnotu rovnou vrací již spočtený výsledek. To je zase možné jenom díky tomu, že výraz pro danou sadu parametrů vrátí pokaždé stejný výsledek, tudíž není závislý na žádném měnitelném stavu.

Fibonacciho posloupnost

Jednoduchým příkladem může být výpočet n-tého čísla Fibonacciho posloupnosti. To lze řešit:

  1. rekurzí – Θ(2^n)
  2. iterativně bez cache výsledků – Θ(n)
  3. pomocí dynamického programování – O(n)

Iterativní řešení pomocí dynamického programování si asi dokáže představit každý, musíme si alokovat indexovanou paměť, kde se pod každým indexem skrývá i-tý prvek posloupnosti. Pro vstup poté iterujeme a před samotným výpočtem se podíváme, jestli již v cache nemáme vypočítané hledané Fibonacciho číslo. Pokud ne, tak se číslo vypočítá a přidá do cache. Implementace v Java bude vypadat například takhle (v ukázkách nebude ošetřen záporný index, pro demonstraci principů to není důležité):

public class FibonacciSolver {
    private List<BigInteger> fibonacciNumbers = new ArrayList<>(
            Arrays.asList(BigInteger.valueOf(0), BigInteger.valueOf(1)));

    public BigInteger fibonacci(int index) {
        if (fibonacciNumbers.size() > index) {
            return fibonacciNumbers.get(index);
        }

        BigInteger last = fibonacciNumbers.get(
                fibonacciNumbers.size() - 1);
        BigInteger previous = fibonacciNumbers.get(
                fibonacciNumbers.size() - 2);
        BigInteger next;
        int currentIndex = fibonacciNumbers.size() - 1;

        while (currentIndex != index) {
            next = last.add(previous);
            fibonacciNumbers.add(next);
            previous = last;
            last = next;
            currentIndex++;
        }
        return last;
    }
}

 

S alokací paměti můžeme mít problém, protože při implementaci nevíme, jak velkou cache zvolit. Můžeme vytvořit nafukovací pole, ale to přináší další složitost danou způsobem implementace (accidental complexity). Musíme ošetřit přístup mimo alokovanou paměť a dynamické roztahování. Zrovna v Javě je to poměrně jednoduché, ale například v C by to tak triviální nebylo.
Funkcionálně se to dá vyřešit hrozně elegantně pomocí lazy nekonečných streamů. Jako implementační jazyk pro zbytek příkladů je použita Scala, ale nosná myšlenka není závislá na jazyku, řešení bude podobné ve všech funkcionálních jazycích.

lazy val fibonacci: Stream[BigInt] = BigInt(0) #:: BigInt(1) #:: 
   fibonacci.zip(fibonacci.tail).map { n => n._1 + n._2 }

 

Díky tomu, že je stream lazy, tak vůbec nevadí, že je nekonečný – počítají se pouze prvky, ke kterým se reálně přistupuje. Zde nemáme problém s přístupem mimo alokovanou paměť. Nepotřebujeme složitě hledat, jaká Fibonacciho čísla jsou již spočítaná a uchovávat ty dosud neznámá. Pokud byste si s tím hráli a zkoušeli počítat hodně velká Fibonacciho čísla, tak to bude stále velmi rychlé a jako první vás nejspíš zastaví velikost paměti JVM, která tak veliká čísla nezvládne.
Zápis využívá pokročilejší konstrukce jazyka Scala. Funkce #:: dělá pouze zřetězení streamů. Takže ve streamu je na prvních dvou místech fixně 0 a 1, což jsou nutné vstupní podmínky rekurentního problému Fibonacciho posloupnosti. Další prvky jsou už počítány dynamicky pomocí rekurentního vyjádření.
Rekurentní člen využívá funkce:

  1. tail – vrátí všechny prvky streamu s výjimkou prvního. V případě nekonečného streamu, tedy stream posunutý o jeden prvek.
  2. zip – vezme 2 streamy a vrátí stream párů, kde i-tý pár obsahuje i-tý prvek z prvního streamu a i-tý prvek z druhého streamu. Stream se zastaví, pokud se dostane alespoň v jednom původním streamu na konec. Zde spojuje původní stream se streamem, který je posunutý o jeden prvek. Každý prvek tedy bude pár, kde jeden prvek je i-tý Fibonacciho číslo a druhý (i+1). Fibonacciho číslo.
  3. map – provádí transformaci nad každým prvkem streamu (zde vezme pár BigInt a sečte hodnoty). V tomto případě tedy sečte i-tý a (i+1)-tý Fibonacciho číslo, což je přesně definice rekurentního vztahu pro Fibonacciho posloupnost.

Zápis je dle mého elegantní (pokud vypadá nepřátelsky, tak dle mého jenom kvůli neznalosti syntaxe), celá komplexita je dána pouze povahou problému (essential complexity). O vše ostatní se postarají lazy values a nekonečné streamy.

Problém batohu

Fibonaccioho posloupnost vám možná přijde jako moc jednoduchý příklad pro demonstraci čistě funkcionálního dynamického programování. Zkusíme ještě jeden o trochu složitější příklad – a to řešení problému batohu.

Optimalizační problém batohu patří do NP problémů (konkrétně FPTAS), ale za určitých okolností se dá řešit pomocí dynamického programování v polynomiálním čase. Využívají se dvě možné dekompozice – podle ceny a podle váhy. Zaměřím se na dekompozici podle váhy.

Při dekompozici podle váhy je potřeba předpočítat tabulku o rozměru (počet věcí + 1)x(kapacita batohu + 1). Prvek tabulky na pozici i, j má hodnotu maximální možné ceny za použití věcí 0 až i a při maximální hmotnosti j. Z tohoto předpisu je hned zřejmé, že optimum se nachází na souřadnicích, kde jsou využity všechny předměty a maximální možná hmotnost batohu (tedy v “pravém horním rohu tabulky”).

Detaily, jak spočítat hodnotu každé souřadnice popisovat nebudu, není to pro účely příkladu tak důležité. Co ale důležité je, tak že jsem schopný spočítat libovolný prvek za pomoci jiných prvků tabulky a omezujících podmínek (např. nemůžu mít zápornou hmotnost, …). Pro každý prvek tedy znám předpis, jak ho spočítat.

Imperativní způsob postupně spočte celou tabulka a pak se přistoupí k optimu. Máme měnitelné 2D pole a 2 vnořené for cykly, které toto pole projdou a vypočítají. Ještě jsem zapomněl zmínit, že mnoho prvků tabulky bude nejspíš nedosažitelných anebo určitě nepovedou k optimu. Kdybychom se jim chtěli vyhnout, tak do cyklů můžeme přidat podmínky, ale opět přidáváme nadbytečnou komplexitu.

Pro funkcionální implementaci je klíčové, že pro každý prvek známe předpis, jak ho spočítat. To nás zase vede na lazy hodnoty. Je možné inicializovat tabulku, která bude obsahovat pouze lazy hodnoty s předpisem, jak se mají spočítat. Přístup k optimu poté spustí kaskádu výpočtů, které dojdou k výsledku. Výhodou je, že se opravdu spustí pouze ty výpočty, které jsou potřeba pro dosažení optima, aniž bychom kvůli tomu implementovali nějakou logiku.

def solveWeightDecomp(problemInstance: ProblemInstance): Int = {
   val items = problemInstance.items

   def computeMatrixElem(i: Int, j: Int): Lazy[Int] = Lazy {
      if (i == 0 || j == 0) 0
      else if (items(i - 1).weight > j) matrix(i - 1)(j)()
      else matrix(i - 1)(j)() max matrix(i - 1)(j - items(i - 1).weight)() 
              + items(i - 1).price
   }

   lazy val matrix = Array.tabulate[Lazy[Int]](problemInstance.size + 1,
      problemInstance.capacity + 1)(computeMatrixElem)

   matrix(problemInstance.size)(problemInstance.capacity)()
}

 

Implementace pro jednoduchost vrací pouze optimální cenu batohu. Získání věcí, které se v optimálním batohu nachází, by ale také bylo jednoduché.

Nejsložitější v implementaci je vnitřní funkce computeMatrixElem, která pouze počítá konkrétní prvek v tabulce na souřadnicích, které jsou dány vstupními parametry. Předpis je dán přímo použitým algoritmem, takže tomu se nevyhneme. Důležité je, že funkce vrací lazy hodnotu.

Následuje inicializace tabulky o rozměrech (počet věcí + 1)x(kapacita + 1). K inicializaci je použita funkce Arrays.tabulate, která kromě rozměrů bere jako parametr funkci. Ta bere tolik vstupních parametrů kolik je dimenze pole. Ty vyjadřují indexy tabulky. Funkce vrací hodnotu prvku tabulky, takže lazy hodnotu.

Doposud se nic reálně nespočítalo! Proběhla pouze registrace výrazů, které vedou k výsledku. Výpočet spouští až poslední řádek, který přistupuje k optimu v tabulce. Jednoduché, čitelné (až na výraz pro výpočet prvku, toho se ale nezbavíme ani v imperativním řešení), rychlé!

Striktní pravidla nejsou až tak na škodu

Striktní pravidla funkcionálního programování nejsou až tak limitující. Jde pouze o praxi a částečnou změnu myšlení. Lazy hodnoty už jsou jedním z pokročilejších funkcionálních konstruktů a v OOP jazycích se bohužel vyskytují zřídka. Často ale můžou výrazně snížit komplexitu a zvýšit expresivnost kódu.

Pro OOP programátora může být těžko představitelné, jak žít bez měnitelného stavu. Proto jsem v článku demonstroval práci s neměnným stavu na dynamickým programování, které se může tvářit, že měnitelný stav vyžaduje přímo z definice.

Autor: Jan Hanuš