L3.1 Kapitola K3 — Důkaz / teorie (Slot 3) · [MUST]

Co je aproximační algoritmus a faktor r

Vítej v kapitole důkazů. Slot 3 písemky padá v ~95 % termínů a žebříček nejpravděpodobnějších důkazů pro 15. 6. zní: Christofides 3/2 [L3.10], korektnost Dijkstry [L3.2], neexistence r-aproximace TSP [L3.6], korektnost Bellman-Forda [L3.7]. Tři ze čtyř položek mluví o „aproximaci“ a „faktoru“ — a všechny důkazy faktorů v této kapitole jsou jen řetízky nerovností kolem jedné definice. Tu definici si dnes postavíme; je to jediná nová věc téhle lekce a společný jazyk celé K3.

Když je optimum mimo dosah

Zatím jsme měli štěstí: nejkratší cesty řeší Dijkstra [L2.4] přesně a v polynomiálním čase. Jenže už v K2 jsme zahlédli druhý břeh — nejdelší cesta je NP-těžká [L2.17] a stejně na tom je obchodní cestující (TSP, traveling salesman problem: najdi nejlevnější okruh přes všechna města; pořádně ho zavedeme v [L3.4] a [L3.5]). U takových problémů přesný polynomiální algoritmus nejspíš neexistuje (pokud $P \ne NP$).

Domluvme značení (převzaté ze slidů): $I$ je instance problému, $J$ kriteriální funkce, $J^*(I)$ hodnota kritéria optimálního řešení instance $I$ a $J^A(I)$ hodnota kritéria řešení, které na instanci $I$ vrátí algoritmus $A$. (Slidy o TSP píší místo $J^*$ zkratku $\mathrm{OPT}(K_n,c)$ — je to totéž.)

Definice r-aproximace

Obě definice dohromady říkají: hodnota $J^A(I)$ je uvězněná v pásu kolem optima. U minimalizace v pásu $[\,J^*(I),\; r \cdot J^*(I)\,]$, u maximalizace v pásu $[\,\tfrac{1}{r} J^*(I),\; J^*(I)\,]$:

„Pro všechny instance“ — faktor je worst-case záruka

Slidy to zdůrazňují výslovně (05_Knapsack, slide 7, EN 1:1): „An approximation algorithm guarantees, that even in the worst case, the value of the objective function will be proportional to the optimum value. The frequency of the worst case is not considered by the approximation algorithm.“ Faktor tedy neříká nic o typickém ani průměrném chování — je to strop pro nejhorší možný vstup, bez ohledu na to, jak vzácný takový vstup je.

Místo faktoru $r$ se někdy používá relativní odchylka od optima $\epsilon$ (relative deviation), svázaná vztahem $r = 1 + \epsilon$: třeba „2-aproximace“ je totéž co „relativní odchylka nejvýš $100\,\%$“. Slide k tomu dodává provokativní otázku — proč je při poměrové záruce nesmyslné udávat absolutní chybu? To je úloha T01.

Heuristika ≠ aproximační algoritmus

Ne každý rychlý a rozumně vypadající algoritmus je aproximační. Příklad ze slidů: nearest neighbor (nejbližší soused) pro TSP — začni v libovolném městě a vždy jdi do nejbližšího dosud nenavštíveného. Přirozený nápad, $\mathcal{O}(n^2)$, často funguje slušně… a slide 23 k němu suše poznamenává: „This is not an approximation algorithm.“ Žádné $r$ pro něj neplatí — existují vstupy, na kterých je poměr $J^A/J^*$ libovolně velký (co přesně tahle věta znamená a jak by se dokazovala, rozebereme v úloze T02). Algoritmus bez dokázaného faktoru se nazývá heuristika (heuristic) — může být užitečný, ale nic neslibuje; další heuristikou tohoto typu je [L3.14] k-OPT local search.

Pozor: nebezpečné polopravdy

• „Vrací skoro optimální řešení, takže je to aproximační algoritmus.“ NE — aproximační algoritmus je jen ten s dokázanou worst-case zárukou $r$ pro všechny instance. Heuristika (nearest neighbor, [L3.14] k-OPT) žádnou záruku nemá, ať se v experimentech chová sebelíp.
• „Faktor 2 znamená, že výsledky bývají zhruba dvakrát horší.“ NE — $r$ je strop pro nejhorší případ; o četnosti špatných případů ani o průměru neříká nic. Typicky bývá výsledek mnohem blíž optimu.
• „U maximalizace: $J^A \le r \cdot J^*$.“ NE — to platí zadarmo (nad optimum se dostat nejde) a nezaručuje nic. Správně zdola: $J^A \ge \frac{1}{r} J^*$. Směr nerovnosti si vždy zkontroluj proti tomu, kterým směrem může algoritmus „kazit“.
• „Když má problém aproximaci v jedné variantě, má ji i obecně.“ NE — faktor je vlastnost dvojice (algoritmus, problém). Metrický TSP má 2-aproximaci [L3.9] i 3/2-aproximaci [L3.10], ale obecný TSP nemá žádnou r-aproximaci, pokud $P \ne NP$ [L3.6].

Jak se faktor dokazuje — mapa zbytku kapitoly

Tohle „sendvičování“ přes mez je celé tajemství důkazů faktorů a uvidíš ho v K3 třikrát:

• Double-tree pro metrický TSP [L3.9]: dolní mez = cena minimální kostry, $c(\mathrm{MST}) \le \mathrm{OPT}$ [L3.8b]. Celý důkaz faktoru 2 je pak jediný řetízek ze slidu 25: $2\,\mathrm{OPT} \ge 2\,c(E(T)) = c(E(L)) \ge c(E(H))$.
• Christofides [L3.10]: stejná kostra + chytřejší druhá mez $c(M) \le \mathrm{OPT}/2$ pro párování — dohromady faktor $\tfrac{3}{2}$.
• Knapsack 2-aproximace [L3.11] (maximalizace): horní mez optima ze zlomkového batohu, $\sum_{i=1}^{h} c_i \ge J^*$.

Až tedy v dalších lekcích uvidíš nerovnost typu $c(\mathrm{MST}) \le \mathrm{OPT}$, věz, že to není ornament — je to nosný trám, bez kterého se faktor s neznámým optimem vůbec nedá svázat. A ještě jedna výstraha dopředu: existence aproximace není samozřejmost. Pro obecný (nemetrický) TSP dokážeme [L3.6], že žádný polynomiální r-aproximační algoritmus neexistuje (pokud $P \ne NP$) — i „vzdát se optimality“ je někdy příliš ambiciózní plán.

Key takeaways — L3.1

• r-aproximace, $r \ge 1$: minimalizace $J^A(I) \le r \cdot J^*(I)$, maximalizace $J^A(I) \ge \frac{1}{r} J^*(I)$ — pro všechny instance $I$. Druhá strana pásu je zadarmo (optimum překonat nejde).
• $r = 1$ je exaktní algoritmus; $r = 2$ znamená „nejvýš dvakrát horší než optimum“ (resp. „aspoň polovina optima“). Alternativní zápis: relativní odchylka $\epsilon$, $r = 1 + \epsilon$.
• $r$ je worst-case záruka: o průměrném chování neříká nic; jeden běh faktor nedokáže (kvantifikátor ∀), ale jediný protipříklad ho vyvrátí.
• Dokázat faktor = ohraničit $J^A$ vůči $J^*$ přes vypočitatelnou mez: u minimalizace dolní mez $B \le J^*$ a $J^A \le r \cdot B$ (TSP: $c(\mathrm{MST}) \le \mathrm{OPT}$ [L3.8b]), u maximalizace horní mez $B \ge J^*$ a $J^A \ge B/r$ (knapsack [L3.11]).
• Heuristika bez dokázané záruky není aproximační algoritmus — nearest neighbor pro TSP není r-aproximace pro žádné $r$; a obecný TSP dokonce žádnou r-aproximaci nepřipouští, pokud $P \ne NP$ [L3.6].

Input:  An instance (K_n, c) of metric TSP.
Output: Hamiltonian circuit H.

Choose arbitrary node v_[1] ∈ V(K_n);
for i := 2 to n do
    choose v_[i] ∈ V(K_n) \ {v_[1], ..., v_[i-1]} such that c({v_[i-1], v_[i]})
      is minimal;
end
Hamiltonian circuit H is defined by the sequence {v_[1], ..., v_[n], v_[1]};