L3.9 Kapitola K3 — Důkaz / teorie (Slot 3) · [MUST] · žebříček #3 (TSP aproximace)

Double-tree algoritmus (2-aproximace metrického TSP)

Jedna nová věc Double-tree algoritmus: MST → zdvojení hran → Eulerovský tah → shortcutting — a důkaz, že výsledný okruh $H$ splňuje $c(E(H)) \le 2 \cdot \mathrm{OPT}(K_n, c)$. První kompletně dokázaná aproximace v učebnici.

Tři stavební kameny z minulých lekcí dnes poprvé zapadnou do sebe: shortcutting [L3.8a], dolní mez $\mathrm{OPT} \ge c(E(T))$ [L3.8b] a Eulerovský tah ze zdvojené kostry s cenou $c(E(L)) = 2\,c(E(T))$ [L3.8c]. Výsledkem je 2-aproximační algoritmus ve smyslu definice z [L3.1] — polynomiální algoritmus se zaručeným worst-case faktorem. U obecného TSP je i tohle nemožné (pokud P ≠ NP, [L3.6]); metrika to mění.

Slož si algoritmus sám

Než ti slide ukáže pseudokód, máš na něj všechno v ruce. Inventura nástrojů:

Zkus sám: poskládej z nástrojů A, B, C algoritmus pro metrický TSP — v jakém pořadí je zapojíš a co poteče mezi nimi?

Přesně v pořadí A → B → C: (1) najdi MST $T$ v $K_n$; (2) zdvoj její hrany a v multigrafu najdi Eulerovský tah $L$ (existuje — všechny stupně sudé, graf souvislý); (3) shortcuttingem převeď $L$ na Hamiltonovský okruh $H$. Mezi kroky teče: kostra → uzavřený tah přes všechny vrcholy (kostra je spojuje všechny) → okruh. A cena se kontrolovaně kutálí: $c(E(T)) \le \mathrm{OPT}$, pak $\times 2$, pak už jen dolů. To je celý double-tree algoritmus — jméno má podle „zdvojeného stromu“ z kroku 2.

Slide 24 (EN 1:1):

Slide 24 — Double-tree Algorithm (1:1)
Input:  An Instance (K_n, c) of the metric TSP.
Output: Hamiltonian circuit H.

  1  Find a minimum weight spanning tree T in K_n;
  2  By doubling every edge in T we get multigraph in which we find
     the Eulerian walk L (i.e., a closed walk containing every edge);
  3  Transform the Eulerian walk L to the Hamiltonian circuit H
     in the complete graph K_n:
        - create a sequence of nodes on the Eulerian walk L;
        - we skip nodes that are already in the sequence;
        - the rest creates the Hamiltonian circuit H;

Observation (1:1): „the doubling of edges in $T$ ensures even degree of all vertices in the multigraph, which is a sufficient and necessary condition for existence of Eulerian walk.“ — to je přesně věta z [L3.8c].

Zkus sám: než budeme měřit cenu — proč je výstup $H$ vůbec přípustné řešení, tedy Hamiltonovský okruh? Projdi kroky a u každého řekni, co garantuje, že další krok má co žrát.

Krok 1 vždy uspěje: $K_n$ je souvislý, kostra existuje a Kruskal/Prim ji najde [L0.5]. Krok 2: zdvojená kostra má všechny stupně sudé a je souvislá → Eulerovský tah $L$ existuje (Observation, dokázáno v [L3.8c]); $L$ prochází všemi hranami, a protože kostra pokrývá všechny vrcholy, navštíví $L$ všechny vrcholy — je to uzavřený sled přes celé $V$. Krok 3: posloupnost prvních návštěv obsahuje každý vrchol právě jednou a zkratky existují, protože $K_n$ je úplný [L3.8a] → $H$ je Hamiltonovský okruh [L3.3]. Přípustnost tedy stojí na úplnosti $K_n$ a na sudých stupních — metrika zatím nebyla potřeba; ta přijde až u ceny.

Celý běh na známé instanci

Pusť si celou linku najednou — na metrické $K_5$ z [L3.8a] (tabulka cen tam), na které jsme všechny tři kroky už jednotlivě trénovali. Detailní rozbory kroků: MST Kruskalem [L3.8b] T02, Eulerovský tah [L3.8c] T02, shortcutting [L3.8a] T02.

Důkaz faktoru 2: tři nerovnosti, jeden řetízek

Na instanci to vyšlo ($12 \le 22$), ale faktor musí podle definice z [L3.1] platit pro každou instanci metrického TSP. Všechny tři dílčí fakty máme dokázané — zbývá je seřadit.

Zkus sám (klíčový krok): máš tři fakta — (1) $c(E(L)) \ge c(E(H))$, (2) $\mathrm{OPT}(K_n,c) \ge c(E(T))$, (3) $2\,c(E(T)) = c(E(L))$. Sestav z nich jediný řetízek nerovností, který začíná u $2\,\mathrm{OPT}$ a končí u $c(E(H))$.

Začni u $2\,\mathrm{OPT}$ a postupně „sestupuj“ k výstupu algoritmu: fakt (2) vynásob dvěma ($2\,\mathrm{OPT} \ge 2\,c(E(T))$ — nerovnost se násobením kladnou konstantou nepřeklopí), fakt (3) přepiš $2\,c(E(T))$ na $c(E(L))$ a fakt (1) sestup z tahu na okruh:

$$2\, \mathrm{OPT}(K_n, c) \;\stackrel{2.}{\ge}\; 2\, c(E(T)) \;\stackrel{3.}{=}\; c(E(L)) \;\stackrel{1.}{\ge}\; c(E(H)).$$

Čteno od konce: $c(E(H)) \le 2\,\mathrm{OPT}$ — double-tree je 2-aproximace. Všimni si dramaturgie: jediné místo, kde do důkazu vstupuje neznámé $\mathrm{OPT}$, je fakt (2) — algoritmus optimum nikdy nepočítá, jen se s ním nepřímo poměřuje přes MST.

Slide 25 (EN 1:1) říká totéž:

Slide 25 — Double-tree Algorithm is 2-approximation Algorithm (1:1)

Time complexity is $\mathcal{O}(n^2)$. It is a 2-approximation algorithm for the metric TSP:

$$2 \mathrm{OPT}(K_n, c) \stackrel{2.}{\ge} 2 c(E(T)) \stackrel{3.}{=} c(E(L)) \stackrel{1.}{\ge} c(E(H))$$

Body 1–3 nejsou nové — jsou to přesně věty z [L3.8a], [L3.8b] a [L3.8c] včetně důkazů. U zkoušky ale nestačí řetízek opsat — chtějí slyšet, proč každý článek drží. Závěrečná inventura:

Zkus sám (inventura předpokladů): který článek řetízku potřebuje trojúhelníkovou nerovnost, který nezápornost cen a který úplnost $K_n$? A kde přesně by se důkaz rozbil na obecném (nemetrickém) TSP?

Trojúhelníková nerovnost: jen článek 1 (shortcutting — zkratka není dražší než nahrazený úsek, [L3.8a]). Nezápornost: článek 2 ($\mathrm{OPT} - c(e) \le \mathrm{OPT}$ vyžaduje $c(e) \ge 0$, [L3.8b]). Úplnost $K_n$: článek 1 potřebuje, aby zkratkové hrany vůbec existovaly. Článek 3 je čisté počítání (každá hrana kostry dvakrát) — bez předpokladů.

Na obecném TSP se rozbije jen článek 1: bez metriky může být přímá hrana libovolně dražší než objížďka, shortcutting zdraží a celý řetízek se přetrhne. A nejde to opravit jinou fintou — z [L3.6] víš, že obecný TSP nemá žádnou r-aproximaci (jinak P = NP). Metrika není kosmetický předpoklad, je to dělicí čára mezi „žádná záruka“ a „faktor 2“.

Složitost a co dál: proč zrovna dvojka?

Slide 25 uvádí složitost $\mathcal{O}(n^2)$. (Rozklad — vlastní komentář, slide jen konstatuje: MST na úplném grafu najde Prim v $\mathcal{O}(n^2)$ [L0.5]; zdvojení, Eulerovský tah Hierholzerem [L3.8c] i shortcutting jsou lineární v počtu hran multigrafu, tedy $\mathcal{O}(n)$.) Polynomialita + dokázaný faktor = aproximační algoritmus podle [L3.1] — na rozdíl od nearest neighbor, který faktor nemá.

Zkus sám: kde přesně v řetízku „bydlí“ ta dvojka — a co bys musel zlevnit, kdybys chtěl faktor menší?

Dvojka bydlí v článku 3: platíme celou kostru dvakrát ($c(E(L)) = 2\,c(E(T))$), protože zdvojení je nejhrubší způsob, jak vyrobit sudé stupně. Kdo chce menší faktor, musí sudé stupně zařídit levněji než druhou kopií kostry. Přesně to udělá Christofides [L3.10]: liché vrcholy (je jich sudý počet [L0.2]) spáruje minimálním perfektním párováním $M$ s cenou $c(M) \le \mathrm{OPT}/2$ — místo $2\,c(E(T)) \le 2\,\mathrm{OPT}$ pak řetízek začíná $c(E(T)) + c(M) \le \tfrac{3}{2}\,\mathrm{OPT}$. Zbytek linky (Euler → shortcutting) zůstane stejný.

Pozor: nebezpečné polopravdy
Key takeaways — L3.9
T01 Double-tree Algorithm — 2-approximation for the metric TSP zdroj: banka #32 (= slidy 24–25 06_TSP) EN 1:1, v bance Unsolved; zkouškové znění otázky vlastní formulace (přiznáno), řešení dle slidů 24–25
Assignment (bank #32 quoted EN 1:1; exam-style question own)

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

  1. Find a minimum weight spanning tree $T$ in $K_n$.
  2. By doubling every edge in $T$ we get a multigraph in which we find the Eulerian walk $L$; i.e., a closed walk containing every edge.
  3. Transform the Eulerian walk $L$ to the Hamiltonian circuit $H$ in the complete graph $K_n$: create a sequence of nodes on the Eulerian walk $L$; skip nodes that are already in the sequence; the rest creates the Hamiltonian circuit $H$.

Observation: doubling the edges of $T$ ensures even degree of all vertices in the multigraph, which is a sufficient and necessary condition for existence of an Eulerian walk.

Exam-style question (own): Describe the double-tree algorithm and prove that it is a 2-approximation algorithm for the metric TSP. State where the triangle inequality is used.

a) Co je v zadání?

Důkazová úloha (žebříček #3 pro 15. 6.): popsat algoritmus (3 kroky) a dokázat faktor 2 — tedy odvodit řetízek $2\,\mathrm{OPT} \ge 2\,c(E(T)) = c(E(L)) \ge c(E(H))$ a každý článek zdůvodnit. Bonusová podotázka míří na nejčastější doplňující dotaz u ústní: kde přesně sedí trojúhelníková nerovnost.

b) Co k tomu budeme potřebovat?

c) Jak nad úlohou uvažovat?

Piš důkaz jako tři očíslovaná lemmata + závěrečné složení. U každého článku si polož kontrolní otázku: 1. proč zkratka nezdraží (a proč existuje)? 2. co vznikne z optimálního okruhu po odebrání hrany a proč je to dražší než MST? 3. kolikrát tah $L$ zaplatí každou hranu kostry? Nezapomeň na půlvětu, že $H$ je vůbec přípustné (Observation → $L$ existuje; úplnost → zkratky existují) — bez ní dokazuješ cenu něčeho, co možná neexistuje.

d) Úplné řešení (dle slidů 24–25; dílčí důkazy = [L3.8a]–[L3.8c])

Algoritmus. 1. Najdi minimální kostru $T$ v $K_n$. 2. Zdvoj každou hranu $T$; v multigrafu najdi uzavřený Eulerovský tah $L$. 3. Projdi $L$, vypiš posloupnost prvních návštěv vrcholů (opakované přeskoč) a uzavři ji do okruhu $H$. Složitost $\mathcal{O}(n^2)$ (Prim na $K_n$; Euler i shortcutting lineární).

Přípustnost. Zdvojení dává každému vrcholu sudý stupeň $2\,|\delta_T(v)|$ a multigraf je souvislý (zdvojená kostra), takže $L$ existuje (Observation; důkaz ekvivalence [L3.8c] T01) a navštěvuje všechny vrcholy. Zkratkové hrany existují, protože $K_n$ je úplný → $H$ je Hamiltonovský okruh.

Článek 1 ($c(E(L)) \ge c(E(H))$): každá zkratka nahrazuje souvislý úsek tahu přímou hranou mezi jeho konci; podle (zobecněné) trojúhelníkové nerovnosti není dražší než úsek — jediné místo důkazu, kde se metrika používá ([L3.8a] T02).

Článek 2 ($\mathrm{OPT}(K_n,c) \ge c(E(T))$): odeber z optimálního okruhu $H^*$ libovolnou hranu $e$ → vznikne kostra, takže $c(E(T)) \le c(E(H^*)) - c(e) \le \mathrm{OPT}$ díky minimalitě MST a nezápornosti cen ([L3.8b] T01).

Článek 3 ($2\,c(E(T)) = c(E(L))$): $L$ projde každou hranu multigrafu právě jednou a multigraf obsahuje každou hranu $T$ dvakrát ([L3.8c] T01).

Složení.

$$2\, \mathrm{OPT}(K_n, c) \;\stackrel{2.}{\ge}\; 2\, c(E(T)) \;\stackrel{3.}{=}\; c(E(L)) \;\stackrel{1.}{\ge}\; c(E(H)),$$

tedy $c(E(H)) \le 2\,\mathrm{OPT}(K_n,c)$ pro každou instanci metrického TSP a double-tree je (polynomiální) 2-aproximační algoritmus. $\blacksquare$

T02 Assumption audit — what exactly does each step need? zdroj: úloha VLASTNÍ (přiznáno) — syntéza předpokladů napříč [L3.8a]–[L3.8c], trénink na doplňující otázky u ústní
Assignment (own, EN)

Consider the double-tree algorithm and the proof of its approximation factor. For each of the following assumptions, identify exactly which part of the algorithm or proof needs it, and describe what breaks without it: (a) completeness of $K_n$, (b) the triangle inequality, (c) non-negativity of the costs $c$. (d) Does the algorithm remain well defined (i.e., does it still output some Hamiltonian circuit) on a complete instance with non-negative costs that violate the triangle inequality? Does the factor-2 guarantee survive?

a) Co je v zadání?

Rozbor předpokladů — typická doplňující otázka, když u ústní odvyprávíš důkaz faktoru 2. Cíl: umět ke každému předpokladu říct přesnou adresu (článek řetízku / krok algoritmu), ne jen „je to potřeba někde v důkazu“.

b) Co k tomu budeme potřebovat?

  • Tato lekce — řetízek a inventura předpokladů (poslední try).
  • [L3.8a] — shortcutting a role úplnosti + metriky.
  • [L3.8b] — kde v dolní mezi sedí nezápornost.
  • [L3.6] — proč se bez metriky nedá zachránit vůbec nic.

c) Jak nad úlohou uvažovat?

Projdi algoritmus krok po kroku a ptej se „co by tu selhalo?“; pak projdi tři články důkazu a totéž. U (d) odděl dvě různé otázky: přípustnost výstupu (potřebuje jen existenci hran a Eulerova tahu) vs. záruku ceny (potřebuje celý řetízek).

d) Úplné řešení (vlastní)

(a) Úplnost $K_n$: krok 3 — zkratka spojuje konce přeskočeného úseku přímou hranou, která musí existovat. Bez úplnosti se může stát, že okruh přes všechny vrcholy v grafu vůbec není (Hamiltonova kružnice je NP-úplná otázka [L3.3]); kroky 1–2 by přitom proběhly (kostra i Euler úplnost nepotřebují, stačí souvislost).

(b) Trojúhelníková nerovnost: jen článek 1 důkazu, $c(E(L)) \ge c(E(H))$. Bez ní může zkratka stát víc než nahrazený úsek a o $c(E(H))$ neumíme říct nic — viz (d).

(c) Nezápornost: článek 2, přesně v kroku $c(E(H^*)) - c(e) \le \mathrm{OPT}$ (odebraná hrana nesmí mít zápornou cenu [L3.8b]). V metrickém TSP je dána definicí $c : E(K_n) \to \mathbb{R}^+$ [L3.8a].

(d) Ano, algoritmus doběhne a vrátí Hamiltonovský okruh: kostra existuje, zdvojení dá sudé stupně (čistá kombinatorika), Euler existuje, zkratky existují (úplnost). Přípustnost tedy přežije. Záruka nepřežije: článek 1 padá a faktor 2 nelze dokázat — a nejde to obejít žádným jiným důkazem ani algoritmem, protože obecný TSP s nezápornými cenami nemá žádnou r-aproximaci, pokud P ≠ NP [L3.6] (instance z tamní konstrukce, ceny $1$ a $2 + (r-1)n$, trojúhelníkovou nerovnost porušují). Hranice „přípustné vždy / levné jen s metrikou“ je celá pointa.

← Předchozí L3.8c · Eulerovský tah a zdvojení hran (sudý stupeň)