Aproximační algoritmy

Máme-li optimalizační problémy, tak si kvůli složitosti často vystačíme s $\alpha$-aproximací, čili s řešením které má cenu $c^{\prime }\le \alpha c^{\ast }$, kde $c^{\ast }$ značíme optimum, pro $\alpha >1$ konstantu v případě minimalizačního problému. Je to totéž jako říci, že relativní chyba $\frac{c-c\ast }{c\ast }$ nepřekročí $\alpha -1$. Pro maximalizační problémy chceme alespoň $0<\alpha <1$ optima.

---

Problém Obchodního cestujícího

Máme neorientovaný graf $G$ s $\forall l(e)>0$ a chceme nejkratší hamiltonovskou kružnici. Hamiltonovskost je sama o sobě $NP$ úplná. Relaxujeme problém a budou nás zajímat je úplné grafy s platnou trojúhelníkovou nerovností.

---

Algoritmus

Najdeme minimální kostru a obejdeme ji, zakořeníme kostru projdeme ji do hloubky a poznamenáme si hrany kterými jsme prošli. Každou hranu kostry ale projdeme 2krát a je to sled. Sled upravíme tak, abychom vždy kdybychom měli navštívit již navštívený vrchol tak místo toho půjdeme do nejbližšího nenavštíveného. Máme tedy hamiltonovskost a jelikož v grafu platí trojúhelníková nerovnost, celková délka nevzrostla.

---

Algortimus je 2-aproximační

Označíme si $T$ délku minimální kostry a $O$ jako optimum a $A$ jako výsledek algoritmu. Z toho jak jsme vytvořili $A$ nám vychází $A\le 2T$ a vychází nám $A\le 2T\le 2O$.

---

Problém batohu

Máme $n$ předmětů s hmotnostmi $h_1,\dots ,h_n$ a cenami $c_1,\dots ,c_n$, a danou kapacitu batohu $H$.

Chceme najít takovou podmnožinu předmětů $S$, že:

• ${\sum }_{i\in S}{h}_i\le H$
• a ${\sum }_{i\in S}{c}_i$ je maximální.

---

Aproximace — kvantování cen

Chceme nalézt řešení s relativní chybou nejvýše $\epsilon >0$.

Idea:

Zmenšíme ceny, aby byly menší než pevné $M=\lceil n/\epsilon \rceil$ a tím zrychlíme DP.

---

Kvantování cen

• Označme $c_{\max }={\max }_i{c}_i$
• Kvantujeme ceny:

$${\hat{c}}_i=\lfloor \frac{c_i\cdot M}{c_{\max }}\rfloor$$

• Nové ceny ${\hat{c}}_i$ jsou celá čísla v intervalu $[0,M]$
• Zaokrouhlením může být každá cena snížena nejvýše o $c_{\max }/M$, tedy maximálně $n\cdot c_{\max }/M$ celkem
• Aby chyba byla $\le \epsilon \cdot c^{\ast }$, volíme $M\ge n/\epsilon$

---

Algoritmus AproximaceBatohu

1. Odstraňme ze vstupu všechny předměty s $h_i>H$
2. Spočítejme $c_{\max }={\max }_i{c}_i$, nastavíme $M=\lceil n/\epsilon \rceil$
3. Pro každé $i=1,\dots ,n$:

$${\hat{c}}_i=\lfloor \frac{c_i\cdot M}{c_{\max }}\rfloor$$

4. Vyřešíme batoh pomocí DP pro kvantované ceny ${\hat{c}}_i$, původní hmotnosti $h_i$ a kapacitu $H$
5. Vrátíme výběr předmětů z kvantovaného řešení a spočítej jejich hodnotu v původních cenách

---

Důkaz přesnosti

• Označme $P$ jako optimální řešení původního problému
• Označme $Q$ jako výstup našeho algoritmu Získáme:

$$\hat{c}(P)\ge \frac{M}{c_{\max }}\cdot c(P)-n$$

a

$$c(Q)\ge \hat{c}(Q)\cdot \frac{c_{\max }}{M}\ge \hat{c}(P)\cdot \frac{c_{\max }}{M}$$

Složením obou:

$$c(Q)\ge c(P)-\epsilon \cdot c(P)=(1-\epsilon )\cdot c(P)$$

---

Složitost

• Kvantované ceny mají maximální součet $nM=O(n^2/\epsilon )$
• Čas na řešení DP: $O(n^3/\epsilon )$
• Ostatní kroky běží v $O(n)$

---

Problém batohu s malými čísly (pseudopolynomiální algoritmus)

Zadání

Máme:

• $n$ předmětů
• každý s hmotností $h_i$ a cenou $c_i$
• kapacitu batohu $H$

Cílem je najít podmnožinu $P\subseteq \{1,\dots ,n\}$, která:

• se vejde do batohu: ${\sum }_{i\in P}{h}_i\le H$
• má co největší cenu: ${\sum }_{i\in P}{c}_i$ je maximální

Idea algoritmu

Namísto klasického dynamického programování podle hmotnosti, sledujeme všechny možné ceny a ke každé hledáme nejmenší možnou hmotnost, za kterou ji lze dosáhnout.

Definice

Označme:

• $C={\sum }_{i=1}^n{c}_i$ = celková suma cen (horní mez)
• $A_k(c)$ = minimální možná hmotnost, kterou lze získat pomocí prvních $k$ předmětů s přesnou cenou $c$
  • Pokud nelze ceny $c$ dosáhnout, položíme $A_k(c)=\infty$

Iniciace

Pro $k=0$ (žádné předměty):

• $A_0(0)=0$
• $A_0(c)=\infty$ pro $c>0$

Rekurence (přechod)

Pro $k=1,\dots ,n$:

• buď $k$-tý předmět nevybereme: pak $A_k(c)=A_{k-1}(c)$
• nebo ho vybereme: pak $A_k(c)=A_{k-1}(c-c_k)+h_k$ (pokud $c\ge c_k$)

Tedy celkově:

$$A_k(c)=\min (A_{k-1}(c),A_{k-1}(c-c_k)+h_k)$$

Výstup

Po výpočtu všech $A_n(c)$ najdeme největší $c^{\ast }$ takové, že:

$$A_n(c^{\ast })\le H$$

To je maximální dosažitelná cena při dané kapacitě.

Rekonstrukce řešení

Zavedeme si pomocné pole $B_k(c)$ = index posledního předmětu použitý k dosažení ceny $c$ s hmotností $A_k(c)$.

Pak zpětně dohledáme předměty:

• $i=B_n(c^{\ast })$ je poslední
• $i^{\prime }=B_{i-1}(c^{\ast }-c_i)$ je předposlední
• atd. To celé trvá $O(n)$

Časová složitost

• Přechod přes $n$ předmětů a $C$ možných cen: $O(nC)$
• Rekonstrukce: $O(n)$