9 - Třídy P/NP a Dynamické programování III

Třídy složitosti jsou množiny úloh, které splňují určitou vlastnost. Tato vlastnost typicky souvisí s časovou či prostorovou náročností jejich řešení. Dvě nejznámější třídy složitosti jsou třída P a třída NP.

Než si uvedeme jejich zjednodušené definice, tak je nutné říci, že třídy složitosti jsou zavedeny pro rozhodovací verze úloh. To znamená, že třeba v případě hledání kostry grafu bychom se neptali, jaká je nejlevnější kostra grafu, ale zda existuje kostra s cenou menší rovno \(k\).

Pro definování tříd složitosti je nutné zavést pojem velikost vstupu úlohy. Velikost vstupu úlohy je počet bitů, který potřebujeme k zakódování vstupu dané úlohy.

Úloha patří do třídy P (Polynomial), pokud existuje algoritmus, který ji řeší v polynomiálním čase vůči velikosti vstupu.

Úloha patří do třídy NP (Non-deterministic Polynomial), pokud existuje algoritmus (verifikátor), který dokáže v polynomiálním čase vůči velikosti vstupu ověřit, zda libovolný polynomiálně dlouhý řetězec je řešením úlohy.

Prakticky vzato verifikátor musí být napojen na generátor možných řešení. Možný generátor je třeba brute force průchod všemi možnými řešeními. Odsud také plyne onen název Nedeterministicky Polynomiální, kdybychom dokázali všechny výstupy našeho generátoru vyzkoušet najednou, tak úlohu řešíme v polynomiálním čase.

Povšimněme si, že pokud máme přímo polynomiální postup, který generuje přímo řešení úlohy, tak tento postup můžeme použít jako generátor. Platí tedy, že \(P \subseteq NP\). Otázka, zda \(NP \subseteq P\) a tedy \(P = NP\) je otevřená.

Dále máme také třídu NP-těžké (NP-hard), což jsou všechny úlohy alespoň tak těžké, jako všechny úlohy v NP. Formálně se jedná o třídu úloh, na které dokážeme v polynomiálním čase převést libovolnou úlohu z NP.

Velmi důležitá je také třída NP-úplné (NP-Complete), do té patří úlohy, které jsou ve třídě NP i třídě NP-hard.

Pro žádnou NP-úplnou úlohu zatím neznáme polynomiální algoritmus. Protože NP-úplné úlohy lze mezi sebou převádět v polynomiálním čase, tak kdybychom našli polynomiální postup řešení jedné z nich, tak jej máme pro celou třídu NP. Mnozí proto předpokládají, že \(P \neq NP\), ale nemáme k tomu důkaz.

Třídami složitosti se detailně zabývá magisterský předmět Teorie Algoritmů (TAL); zde uvedený text je jen hrubé shrnutí pro přehled. Cílem je poskytnout základní přehledovou znalost i těm, kteří nebudou pokračovat na magisterské studium, či těm, kteří se o algoritmy zajímají i ve volném čase a mohou tedy na tyto koncepty narazit.

Problém batohu (knapsack problem) je klasický NP-těžký problém. Máme batoh s kapacitou \(C\) a \(n\) předmětů, kde každý předmět \(i\) má váhu/velikost \(c_i\) a cenu/hodnotu (value) \(v_i\). Chceme maximalizovat hodnotu předmětů tak, aby předměty, které zvolíme nepřeplnily batoh, tedy součet jejich vah byl menší nebo rovný kapacitě \(C\).

Uvažují se 2 varianty, 0/1 knapsack znamená, že každý předmět máme jen jeden a rozhodujeme, zda ho vzít, či nevzít (0/1). Neomezená varianta pak znamená, že každý předmět můžeme vzít kolikrát chceme. Obě varianty řešíme tak, že uvažujeme optimální řešení pro batoh s menší kapacitou a do nich zkoušíme přidat další předměty.

Pro 0/1 knapsack pak vyplňujeme tabulku, kde řádky znamenají přidání konkrétního předmětu a sloupce jsou změny v kapacitě. Do tabulky pak zapisujeme maximální hodnotu, kterou můžeme dostat s batohem dané kapacity a s danými předměty.

\(h(i, j) = \begin{cases} 0 & \mathrm{pokud} \ i = 0 \lor j = 0 \\ \max(h(i-1, j), h(i-1, j-c_i) + v_i) & \mathrm{jinak} \end{cases}\)

Knapsack je tedy převoditelný na problém nejdelší cesty v DAGu či tabelaci, což jsme již řešili na minulých cvičeních.

Řešení neomezeného i 0/1 knapsacku má složitost \(\Theta(C \cdot n)\), protože vyplňujeme tabulku o dimenzích \(C \times n\), či procházíme DAG s \(\Theta(C \cdot n)\) hranami.

Toto je úloha, kde máme sestrojit BVS, pro který známe pravděpodobnosti dotazů na jednotlivé klíče. Chceme minimalizovat očekávaný počet operací, kdy nalezení klíče \(k\) v hloubce \(h_k\) vyžaduje \(h_k+1\) operací. Pokud je pravděpodobnost dotazu na klíč \(k\) rovna \(p_k\), celková cena umístění klíče \(k\) do hloubky \(h_k\) bude \(p_k(h_k + 1)\). Minimalizujeme součet přes všech \(n\) klíčů.

Podobně jako při závorkování, optimální strom o \(n\) uzlech lze vidět jako kořen a 2 optimální podstromy v levé a pravé větvi. Toto je naše “optimal substructure”. Když budeme hledat optimální strom o \(n\) uzlech tak, že budeme zkoušet každý z \(n\) uzlů jako kořen, budeme využívat stejné podstromy vícekrát - “overlapping subproblems”. Cenu stromu vypočteme vždy jako součet pravděpodobností výskytu všech uzlů + ceny obou podstromů.

Složitost bude také \(\Theta(n^3)\), výpočet je podobný výpočtu závorkování.

Řešená úloha 1:

Při popisu úlohy batohu jsme si řekli, že se jedná o klasickou NP-těžkou úlohu, ale zároveň jsme si řekli, že její složitost je \(\Theta(C \cdot n)\). Ale to je přeci polynom! Vysvětlete, proč zdánlivě polynomiální složitost úlohy batohu není v rozporu s tvrzením, že se jedná o NP-těžkou úlohu.

Řešená úloha 2: Řešte neomezenou variantu úlohy batohu pro kapacitu 10 a tři předměty, jejichž váhy jsou postupně 1, 3, 6 a ceny jsou ve stejném pořadí předmětů 11, 33, 65.

Jaká bude maximální cena předmětů v batohu?

Jaké bude řešení pro 0/1 knapsack pro stejné předměty a kapacitu 7?

Řešená úloha 3: Určete, jak bude vypadat optimální BVS, když jej vybudujeme pro 7 klíčů s frekvencemi:

⭐ Úloha 4: Řešte 0/1 variantu úlohy batohu pro kapacitu 130 a pět předmětů, jejichž váhy jsou postupně 20, 30, 40, 50, 60 a ceny jsou ve stejném pořadí předmětů 11, 33, 45, 58, 65.

Jaká bude maximální cena předmětů v batohu?

Uvažte, jak se vyhnout tabulce se cca 130 sloupci a upravte postup řešení tak, aby stačilo řádově méně sloupců.

⭐ Úloha 5: Pravděpodobnost dotazu na jednotlivé klíče v obou daných BVS je tato:

A: 0.10 B: 0.20 C: 0.25 D: 0.05 E: 0.10 F: 0.25 G: 0.05

Vypočtěte, který strom je výhodnější pro operaci FIND.

Úloha 6: Určete, jak bude vypadat optimální BVS, když jej vybudujeme pro 7 klíčů s frekvencemi:

E: 0.04 F: 0.05 G: 0.22 H: 0.04 I: 0.06 J: 0.05 K: 0.15

⚡ Úloha 7: Každá zásilka ve skladu má určenou váhu a je nutno všechny zásilky naložit na dvě přistavené dodávky tak, aby se váhy nákladů na obou dodávkách lišily co nejméně.

Zdůvodněte, zda lze či nelze metodu DP pro řešení úlohy batohu využít i v této situaci.

Úloha 8: Kryštof staví malé sportovní lodě. Vyrábí jich několik typů a vždy se věnuje stavbě jen jedné lodě, dokud není hotová. Pro každý typ lodě zná počet dní potřebný ke stavbě lodě a zná svůj zisk z jejího prodeje. Ví, kolik dní bude letos v sezóně věnovat své práci.

Navrhněte metodu dynamického programování, která bude maximalizovat Kryštofův výdělek za letošní sezónu.