Čtení: 25 minHodnotí se: zápočtový test, úloha 2 (6 b)

2 Self-redukce

Po přečtení umíš

najít hodnotu optima binárním vyhledáváním přes rozhodovací verzi
z odpovědí ANO a NE sestavit konkrétní řešení
vědět, proč musíš znát přesné optimum
spočítat počet dotazů na orákulum

Úloha zní: „Máš černou skříňku, která jen odpoví ANO nebo NE. Najdi konkrétní řešení.“ Má vždy stejnou kostru, takže je to nejjistějších 6 bodů v testu.

2.1 Ukázka: kudy jet

Skříňka odpoví, zda v grafu existuje okružní cesta délky nejvýš $W$ . Víme už, že optimum je 22, ale chceme hrany.

Zkus smazat hranu a zeptej se znovu:

Odpověď ANO: bez hrany to jde, nech ji smazanou.
Odpověď NE: hrana je nutná, vrať ji a označ.

Po projití všech hran zbude přesně $|V|$ hran a ty tvoří hledanou kružnici. Skříňka přitom nemusí být rychlá. Zajímá nás jen počet dotazů.

2.2 Kostra řešení

Definice 2.2 (Self-redukce)

Postup, který najde konkrétní řešení problému pomocí polynomiálně mnoha dotazů na jeho rozhodovací verzi.

Najdi hodnotu optima. Binárně vyhledej $k$ v rozsahu možných hodnot.
Projdi prvky řešení po jednom (vrcholy, hrany, proměnné).
Pro každý zkus odstranění nebo zafixování a zeptej se orákula.
Podle odpovědi úpravu nech, nebo vrať. Instance po každém kroku pořád má řešení.
Spočítej dotazy a řekni, proč je výsledek správný.

Varování 2.3 (Proč musíš znát přesné optimum)

Pokud spustíš mazání hran s $W = 25$ a optimum je 22, může orákulum odpovídat ANO díky horší kružnici délky 24. Hranu z optimální kružnice pak smažeš a optimum ztratíš. Dostaneš platné řešení, ale ne nejlepší.

2.3 Řešené příklady ze cvičení

Příklad 2.4 (Největší klika (cvičení 2.4))

Hodnota. Binárně vyhledej největší $k$ v $\{1, \dots, n\}$ , pro které orákulum řekne ANO. To je $O(\log n)$ dotazů.

Řešení. Pro každý vrchol $v$ se zeptej, zda $G - v$ obsahuje kliku velikosti $k$ .

ANO: smaž $v$ natrvalo, nějaká největší klika ho nepotřebuje.
NE: $v$ je v každé zbylé největší klice, nech ho.

Po průchodu zbude přesně $k$ vrcholů a ty tvoří kliku.

Dotazů: $n + O(\log n)$ .

Příklad 2.5 (3-obarvení (cvičení 2.5))

Orákulum umí jen říct, jestli je graf 3-obarvitelný. Barvu mu předat neumíme, ale můžeme ji vynutit grafem.

Paleta. Přidej trojúhelník $p_1, p_2, p_3$ . Jeho vrcholy mají tři různé barvy, které pojmenujeme 1, 2, 3.

Pro každý vrchol $v$ a barvu $c$ : spoj $v$ se dvěma vrcholy palety různými od $p_c$ . Tím má $v$ barvu $c$ . Zeptej se orákula.

ANO: hrany nech, $v$ má barvu $c$ .
NE: hrany odeber a zkus další barvu.

Protože původní graf obarvitelný je, nějaká barva vždy projde.

Dotazů: nejvýše $3n$ .

Příklad 2.6 (SAT)

Máme proměnné $x_1, \dots, x_n$ . Pro každou zkus přidat k formuli jednotkovou klauzuli $(x_i)$ . Je-li výsledek splnitelný, nech ji. Jinak přidej $(\neg x_i)$ . Na konci je ohodnocení hotové. Stačí $n$ dotazů.

Příklad 2.7 (Nejmenší vrcholové pokrytí)

Najdi nejmenší $k$ . Pro každý vrchol $v$ se ptej, zda má $G - v$ pokrytí velikosti $k - 1$ .

ANO: $v$ dej do pokrytí, smaž ho a sniž $k$ .
NE: $v$ není v žádném nejmenším pokrytí, jdi dál.

Stačí jeden průchod: kdyby $v$ patřil do nejmenšího pokrytí až později, patřil by do něj i dřív, protože vzaté vrcholy lze přidat zpět.

2.4 Typické chyby

Chybí krok s nalezením optima.
Tvrzení „ANO, takže prvek je v řešení“ u postupu s mazáním. Je to naopak: ANO znamená, že prvek není potřeba.
Orákulum dostane něco, co neumí, třeba graf s předbarvenými vrcholy. Povolený je jen vstup rozhodovací verze.
Chybí počet dotazů.

2.5 Kvíz

Kvíz

1. Při mazání hrany orákulum odpoví ANO. Co to znamená? Hrana je v řešení Hrana není potřeba, zůstane smazaná Výsledek je neplatný

2. Kolik dotazů potřebuje binární vyhledání

k

v rozsahu

1

až

n

O(1)

O(\log n)

O(n)

O(2^n)

3. Co se stane, když mažeš hrany s neoptimální mezí

W

? Algoritmus spadne Dostaneš nějaké platné řešení, ne nutně nejlepší Orákulum odpoví nesmysl

4. Graf má 10 vrcholů. Kolik nejvýše dotazů potřebuje postup pro 3-obarvení? Odpověď:

5. Proč u 3-obarvení přidáváme paletu, když orákulum neumí barvy?

Ukázat řešení

Hrany na dva vrcholy palety nechají vrcholu jedinou možnou barvu. Barvu tak vyjádříme v jazyce grafu, který orákulum umí.

2.6 Příklady na procvičení

Cvičení 2.8

Najdi hamiltonovskou kružnici pomocí orákula „obsahuje graf hamiltonovskou kružnici?“. Kolik dotazů potřebuješ?

Řešení

Nejdřív se zeptej na celý graf. Pak procházej hrany a zkus je mazat: ANO znamená smazat, NE vrátit. Zbude přesně $n$ hran kružnice. Dotazů je $|E| + 1$ . Optimum hledat nemusíš, protože tady žádná délka není.

Cvičení 2.9

Máš orákulum pro Independent Set. Najdi největší nezávislou množinu.

Řešení

Binárně najdi největší $k$ . Pro každý vrchol $v$ se zeptej, zda má $G - v$ nezávislou množinu velikosti $k$ . ANO: smaž $v$ . NE: nech ho. Zbylé vrcholy tvoří hledanou množinu. Dotazů je $n + O(\log n)$ . Je to stejná kostra jako u kliky.

2.7 Tahák

Tahák

1. optimum binárně, 2) po prvcích zkoušej mazat nebo fixovat, 3) spočítej dotazy.
ANO = úprava zůstane, NE = vrať ji.
Bez přesného optima můžeš optimum ztratit.
Orákulum dostává jen běžné instance. Co neumí, vynuť stavbou (paleta u barvení).
SAT: fixuj proměnné jednotkovými klauzulemi, $n$ dotazů.
Klika: $n + O(\log n)$ dotazů. 3-barvení: nejvýše $3n$ .

Kapitolu mám prostudovanou