Vyčíslitelnost a složitost výpočtů

Aplikace: Dynamické programování

Shrnutí kapitoly

Existuje početná skupina problémů (často založených na rekurzi), které vyžadují rozdělit problém na části, a jejich řešení využít pro výpočet celkového řešení. Přitom se často zdá, že množství nutných výpočtů (rekurzívních volání) roste exponenciálně s velikostí zadání, a že tedy problém je NP-těžký. Ve skutečnosti tomu ale tak není: stačí si všimnout, že mnoho částečných řešení se počítá opakovaně, a jejich celkový počet je jen polynomiální. Dynamické programování je obecná strategie, kdy místo rekurzívního algoritmu postupně vypočítáváme řešení podproblémů od nejmenších k větším, a mezivýsledky ukládáme, až se dostaneme k výpočtu původního zadání.

Typickým příkladem je výpočet , kde je tento princip názorně předveden.

Studijní materiály

Doporučuji kurz dynamického programování na wiki stránkách ČVUT. Pro nastudování základů si projděte prezentace č. 09 a 10a, nejdůležitější vybrané partie např.

- slidy 4-10 v sadě 09, 

- slidy 7-23 v sadě 10a, klíčová myšlenka je na slidu 16. 

Příklady a problémy

Problém reprezentace obrázku binárním stromem (klikněte pro zobrazení zadání). Kromě kódu programu odevzdejte i výpis vstupů a výstupů pro všech 10 příkladů ve veřejném datasetu, na který je na konci zadání odkaz.

Nápověda řešení pro variantu minimálního počtu uzlů ve stromě:

Označím MU(x1, x2, y1, y2) minimální počet uzlů ve stromě reprezentujícím obraz mezi sloupci x1-x2 (včetně) a řádky y1-y2 (včetně). Například pro obdélník 2x3 v pravém horním rohu obrázku je to MU(W-2, W, 1, 2).

Teď lze napsat naivní algoritmus, který by řešil úlohu hrubou silou:

INPUT: char image[][];       // obrázek rozměrů HxW s hodnotami '0', '1'

// v tomto kódu ho používám jako globální proměnnou, i když se to nemá

int MU(int x1, int x2, int y1, int y2)  {

// metoda vrací počet uzlů v podstromu reprezentujícím výřez obrázku (obdélník)

// ve sloupcích x1 až x2 a řádcích y1 až y2 včetně

bool black = false;

bool white = false;

for (int i = x1; i <= x2; i++) {

     for (int j = y1; i <= y2; j++) {

         black |= image[i,j] == '1';

         white |= image[i,j] == '0';

     }

}

// pokud mají všechny pixly v obdélníku stejnou barvu, je výsledek 1

// obrázek je pak reprezentován grafem s jedním uzlem

if ! (black & white) {   return 1 }


// nastupuje dělení: v nejhorším případě budeme potřebovat pro každý pixel zvláštní list stromu

// celkový  počet uzlů ve stromě pak bude:

int vysledek = 2 * (x2 - x1+1) * (y2 - y1+1) - 1;


// vyzkoušíme všechna možná horizontální dělení a vybereme z nich nejlepší

for (int i = y1; i < y2; i++) {

     vysledek = Math.Min(vysledek, MU(x1, x2, y1, i) + MU(x1, x2, i+1, y2) + 1    }


// totéž pro vertikální dělení

for (int i = x1; i < x2; i++) {

     vysledek = Math.Min(vysledek, MU(x1, i, y1, y2) + MU(i+1, x2, y1, y2) + 1    }

return vysledek

}

Řešení úlohy dostanu zavoláním MU(0, W-1, 0, H-1).

Jaká je vada tohohle řešení? Že má exponenciální časovou složitost, to se dá snadno zjistit. Je to tak proto, že se různé mezivýsledky MU(x1, x2, y1, y2) pro stejnou kombinaci x1, x2, y1, y2 počítají opakovaně. Přitom, kolik je všech možných mezivýsledků, tj. všech možných obdélníků v obraze? Přesně W*(W+1)*H*(H+1)/4 (proč? zkuste odvodit).

Takže to chce algoritmus upravit - uchovávat někde potřebné mezivýsledky a postupně je počítat jako v úloze tabelace na slidech alg09, nebo při násobení matic na slidech alg10a na wiki stránkách ČVUT.

Předchozí
Následující