Metrický TSP + trojúhelníková nerovnost + shortcutting
V [L3.6] Neexistence r-aproximace pro obecný TSP jsme dokázali, že obecný TSP nejde aproximovat s žádnou zárukou (pokud $P \ne NP$). Slíbená záchrana se jmenuje metric TSP (metrický TSP). Dnešní lekce ho definuje a vytěží z definice první nástroj — shortcutting (zkracování přes opakované vrcholy). Je to jeden ze tří stavebních kamenů, ze kterých pak složíme double-tree [L3.9] i Christofidese [L3.10]; zbylé dva přijdou v [L3.8b] (dolní mez) a [L3.8c] (Eulerovský tah).
Co přesně zabilo aproximace — a jak to zakázat
Zkus sám: prohlédni si zabijáckou instanci z [L3.6] — hrany grafu $G$ stojí $1$, ostatní $2 + (r-1)n$. Čím se tahle „mapa“ liší od skutečných vzdáleností mezi městy? Najdi trojici měst, kde se chová nereálně.
Vezmi města $i, k$ spojená drahou hranou a libovolné mezilehlé $j$ spojené s oběma levně. Pak oklika přes $j$ stojí $1 + 1 = 2$, zatímco přímá hrana $2 + (r-1)n$ — oklika je řádově levnější než přímé spojení. U vzdáleností na mapě to nejde: přímé spojení nikdy není delší než zajížďka přes třetí město. Přesně tahle vlastnost reálných vzdáleností se jmenuje trojúhelníková nerovnost — a zabijácké instance ji porušují. Zákaz takových instancí je tedy přirozená (a prakticky všudypřítomná) restrikce.
Slide 22 (EN 1:1): „In most common applications the distances of the TSP satisfy the triangle inequality.“
- Instance: Complete undirected graph $K_n$ ($n \ge 3$) with weights $c : E(K_n) \to \mathbb{R}^+$ such that $c(\{i,j\}) + c(\{j,k\}) \ge c(\{k,i\})$ for all $i, j, k \in V(K_n)$.
- Goal: Find the Hamiltonian circuit $T$ such that $\sum_{e \in E(T)} c(e)$ is minimal.
Hamiltonovskou kružnici znáš z [L3.3]; nové je jen omezení na ceny. Čti ho jako „přímá hrana není nikdy dražší než oklika přes třetí vrchol“.
Zkus sám: trojúhelníkovou nerovnost jsi v učebnici už dvakrát potkal — kde? A v čem je dnešní použití jiné?
V [L2.1] jako větu o nejkratších vzdálenostech: $l(i,j) \le l(i,k) + l(k,j)$ platí v každém grafu bez záporného cyklu — je to dokázaná vlastnost funkce $\mathrm{dist}$, zadarmo. A v [L3.7] na ní stála detekce záporného cyklu Bellman-Fordem.
Dnes je role obrácená: trojúhelníková nerovnost je předpoklad o vstupních cenách $c$, který instance buď splňuje, nebo ne. Ekvivalentní čtení: instance je metrická právě tehdy, když je přímá hrana $\{i,k\}$ nejkratší cestou mezi $i$ a $k$ — ceny $c$ se rovnají vlastní metrice vzdáleností.
Metrický ≠ snadný
Zkus sám: zachránili jsme se restrikcí z těžkosti? Vrať se k důkazu silné NP-těžkosti TSP [L3.5] — instance tam měly váhy $1$ a $2$. Splňují trojúhelníkovou nerovnost?
Ano. Nejhorší případ: dvě nejlevnější hrany proti nejdražší, $1 + 1 \ge 2$ — platí (a všechny ostatní kombinace tím spíš: $1+2 \ge 2$, $2+2 \ge 2$, …). Celý důkaz z [L3.5] tedy běží uvnitř metrických instancí beze změny — metrický TSP je pořád silně NP-těžký. Restrikce nezachránila optimální řešení v polynomiálním čase; zachrání (až) aproximace.
„The metric TSP is strongly NP-hard. Can be proved in the same way as the complexity of TSP because weights 1 and 2 preserve the triangle inequality. Therefore the pseudopolynomial algs do not exist.“
„But approximation algorithms do exist.“
To je celá pointa kapitoly: NP-těžkost zůstává, ale na metrických instancích už jde slíbit záruku — faktor 2 (double-tree [L3.9]) a dokonce 3/2 (Christofides [L3.10], žebříček #1). Oba důkazy stojí na dnešním shortcuttingu.
Zmetrikovat umí každý: posun $+h$ (a proč to nic neřeší)
„We can make the TSP instance metric simply by adding the same constant $h$ to the cost of every edge (the criterion function is higher by $n * h$), but this does not lead to approx. alg. for non-metric TSP.“
Zkus sám: v [L2.15] jsme dokázali, že posun $+h$ rozbíjí nejkratší cesty. Proč je u TSP bezpečný — proč se po $+h$ nezmění, KTERÝ okruh je optimální?
U nejkratších cest vadilo, že porovnávané cesty mají různý počet hran — příplatek $h \cdot |P|$ pak není všude stejný. Ale každá Hamiltonovská kružnice na $n$ vrcholech má přesně $n$ hran: každý vrchol právě jednou opustíš. Příplatek je tedy pro všechny porovnávané objekty stejných $n \cdot h$, pořadí okruhů se nezmění a kritérium se jen posune o $n \cdot h$ — přesně výjimka „stejný počet hran“ z infoboxu [L2.15]. A dost velké $h$ trojúhelníkovou nerovnost spraví: chceme $(c(i,j)+h) + (c(j,k)+h) \ge c(k,i)+h$, tj. $h \ge c(k,i) - c(i,j) - c(j,k)$ pro všechny trojice — stačí $h \ge c_{\max}$ (spočítáš přesněji v T01).
Zkus sám (těžší, ale klíčové): tak proč tedy neumíme aproximovat obecný TSP takhle: „přičti $h$, pusť aproximaci pro metrický TSP, odečti $n \cdot h$“? Kdyby to šlo, byli bychom ve sporu s [L3.6] — najdi, kde se faktor ztratí.
Nechť $\mathcal{A}$ je r-aproximace pro metrický TSP a $H$ její výstup na posunuté instanci $c' = c + h$. Záruka platí v posunutém světě:
$$c'(H) \le r \cdot \mathrm{OPT}' = r\,(\mathrm{OPT} + n h).$$Po návratu do původních cen ($c(H) = c'(H) - nh$):
$$c(H) \le r \cdot \mathrm{OPT} + (r-1)\,n h.$$Aditivní člen $(r-1)\,n h$ se neodečte — a vůči $\mathrm{OPT}$ může být libovolně velký, takže žádný násobný faktor v původním světě nedostaneš. Poznáváš ho? Je to přesně rozdíl $(r-1)n$, kterým zabijácká konstrukce v [L3.6] roztáhla mezeru mezi „HC existuje“ a „HC neexistuje“. Všechno do sebe zapadá: kdyby se faktor přenášel, [L3.6] by dávala $P = NP$. (Odvození je naše vlastní rozepsání — slide konstatuje jen závěr „does not lead to approx. alg.“.)
Zobecněná trojúhelníková nerovnost: zkratka přes víc vrcholů
Definice mluví o trojicích. Pro shortcutting budeme potřebovat přeskakovat i několik vrcholů najednou.
Zkus sám: v metrické instanci vezmi řetěz $u \to x \to y \to v$ (tři hrany). Platí $c(\{u,v\}) \le c(\{u,x\}) + c(\{x,y\}) + c(\{y,v\})$? Odvoď to dvojím použitím trojúhelníkové nerovnosti — a rozmysli, jak by šlo pokračovat pro libovolně dlouhý řetěz.
Dvakrát „srovnej roh“:
$$c(\{u,y\}) \le c(\{u,x\}) + c(\{x,y\}), \qquad c(\{u,v\}) \le c(\{u,y\}) + c(\{y,v\}).$$Dosazením první do druhé: $c(\{u,v\}) \le c(\{u,x\}) + c(\{x,y\}) + c(\{y,v\})$. Obecně indukcí přes počet hran řetězu: přímá hrana mezi konci není nikdy dražší než součet cen podél libovolného řetězu (sledu) mezi nimi. Říkejme tomu zobecněná trojúhelníková nerovnost.
Shortcutting: z uzavřeného sledu Hamiltonovský okruh
Teď ten nástroj nasadíme. Algoritmy v [L3.9] a [L3.10] budou vyrábět uzavřený sled (closed walk, [L2.1]), který projde všemi vrcholy — ale některými víckrát, takže to ještě není Hamiltonovský okruh. Konkrétní příklad (vlastní ilustrační instance; ceny tvoří metriku, ověříš v T02):
| $c(\{\cdot,\cdot\})$ | B | C | D | E |
|---|---|---|---|---|
| A | 2 | 3 | 3 | 2 |
| B | — | 1 | 2 | 3 |
| C | — | — | 2 | 4 |
| D | — | — | — | 5 |
Dán je uzavřený sled $W = A \to B \to C \to B \to D \to B \to A \to E \to A$ — 8 hran, délka $2+1+1+2+2+2+2+2 = 14$, navštíví všech 5 vrcholů, ale $B$ třikrát a $A$ třikrát.
Zkus sám: navrhni, jak ze sledu $W$ vyrobit Hamiltonovský okruh — a zdůvodni, proč tvá úprava celkovou cenu nezvýší. (Nápověda: graf je úplný, takže „rovnou dál“ se dá vždycky.)
Jdi podél sledu a přeskakuj vrcholy, které už jsi navštívil: místo abys z $C$ couval do $B$ (už viděno) a teprve pak šel do $D$, skoč přímo $C \to D$ — v úplném grafu $K_n$ ta hrana existuje. Zůstane posloupnost prvních návštěv $A, B, C, D, E$ a návrat do $A$: Hamiltonovský okruh (každý vrchol právě jednou [L3.3]).
A cena? Každá zkratka nahrazuje souvislý úsek sledu přímou hranou mezi jeho konci — a ta podle zobecněné trojúhelníkové nerovnosti není dražší než nahrazený úsek. Žádná jiná hrana se nemění, takže celková cena neporoste. Tomuhle postupu se říká shortcutting (zkracování).
Přesně takhle to dělá krok 3 double-tree algoritmu (slide 24, EN 1:1 — tam je vstupem Eulerovský tah $L$, což je speciální uzavřený sled; potkáš ho v [L3.8c]):
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;Slide 25, bod 1: „due to the triangle inequality, the skipped nodes don't prolong the route, i.e. $c(E(L)) \ge c(E(H))$“.
Zkus sám: které DVĚ vlastnosti metrické instance shortcutting potřebuje? (Jednu na to, aby vůbec šel; druhou na to, aby nezdražoval.)
- Úplnost $K_n$ — zkratková hrana mezi koncem a prvním dalším nenavštíveným vrcholem musí existovat. V obecném (neúplném) grafu by zkratka nemusela vést kudy.
- Trojúhelníková nerovnost — zkratka nesmí být dražší než obcházený úsek. V nemetrické instanci může přímá hrana stát víc než celá oklika (přesně to dělaly instance z [L3.6]) a shortcutting by okruh zdražil.
Obě vlastnosti má metrický TSP z definice — proto je shortcutting „zadarmo“.
K čemu to bude: plán na příští lekce
Shortcutting je poslední krok obou aproximačních algoritmů: vyrobí z laciného uzavřeného sledu přípustný Hamiltonovský okruh, aniž by pokazil cenu — v řetízcích důkazů obstará nerovnost $c(E(L)) \ge c(E(H))$. Zbývá umět sled lacino vyrobit (Eulerovský tah nad zdvojenou kostrou, [L3.8c]) a cenu sledu svázat s neznámým $\mathrm{OPT}$ (dolní mez $\mathrm{OPT} \ge c(\mathrm{MST})$, [L3.8b] — hned další lekce). Pak už faktory 2 [L3.9] a 3/2 [L3.10] vypadnou složením tří nerovností.
Pozor: nebezpečné polopravdy- „Trojúhelníková nerovnost platí vždycky.“ NE — pro vstupní ceny $c$ je to předpoklad, který nemetrické instance porušují (zabijácké instance z [L3.6]: $1 + 1 < 2 + (r-1)n$). Nezaměň s větou z [L2.1] o vzdálenostech $\mathrm{dist}$ — ta platí v každém grafu bez záporného cyklu.
- „Metrický TSP už je snadný.“ NE — je pořád silně NP-těžký (váhy 1/2 z [L3.5] jsou metrické), pseudopolynomiální algoritmus neexistuje. Restrikce zachraňuje jen aproximovatelnost.
- „Shortcutting okruh zkrátí.“ NE nutně — zaručeno je jen nezhoršení ($\le$). Pokud jsou ceny „degenerované“ (zkratka stojí přesně tolik co oklika), vyjde rovnost; v důkazech proto stojí $c(E(L)) \ge c(E(H))$, žádné ostré $>$.
- „Posunem $+h$ převedu aproximaci metrického TSP na obecný.“ NE — záruka se přenese jako $c(H) \le r \cdot \mathrm{OPT} + (r-1)nh$ a aditivní člen faktor zničí; jinak by to byl spor s [L3.6].
Key takeaways — L3.8a- Metrický TSP (slide 22): úplný $K_n$ ($n \ge 3$), $c : E(K_n) \to \mathbb{R}^+$ s trojúhelníkovou nerovností $c(\{i,j\}) + c(\{j,k\}) \ge c(\{k,i\})$ pro všechny trojice; hledá se nejlevnější Hamiltonovský okruh [L3.3].
- Metrický TSP je stále silně NP-těžký (váhy 1 a 2 z [L3.5] trojúhelníkovou nerovnost splňují) — ale na rozdíl od obecného TSP [L3.6] aproximační algoritmy existují.
- Zobecněná trojúhelníková nerovnost (indukcí): přímá hrana mezi konci není dražší než libovolný řetěz mezi nimi.
- Shortcutting: uzavřený sled přes všechny vrcholy → posloupnost prvních návštěv = Hamiltonovský okruh; každá zkratka nahrazuje úsek sledu přímou hranou, takže $c(E(L)) \ge c(E(H))$. Potřebuje úplnost (zkratka existuje) i metriku (zkratka nezdraží) — proto jdou Eulerovské tahy [L3.8c] převést na Hamiltonovský okruh bez zhoršení.
- Posun $+h$ zmetrikuje každou instanci (všechny okruhy mají $n$ hran, kritérium $+\,n h$ — výjimka z [L2.15]), ale aproximační faktor se nepřenese.
Metric TSP. Instance: Complete undirected graph $K_n$ ($n \ge 3$) with weights $c : E(K_n) \to \mathbb{R}^+$ such that $c(\{i,j\}) + c(\{j,k\}) \ge c(\{k,i\})$ for all $i, j, k \in V(K_n)$. Goal: Find the Hamiltonian circuit $T$ such that $\sum_{e \in E(T)} c(e)$ is minimal.
Study questions (own): (i) Show that the metric TSP is strongly NP-hard. (ii) Show that every TSP instance can be made metric by adding the same constant $h$ to the cost of every edge — how large must $h$ be, and what happens to the criterion function? (iii) Explain why (ii) does not yield an r-approximation algorithm for the non-metric TSP.
a) Co je v zadání?
Teoretická otázka formátu ústní zkoušky: definice metrického TSP a tři tvrzení ze slidu 22, která máš umět nejen citovat, ale i zdůvodnit — těžkost se dědí, $+h$ zmetrikuje, faktor se nepřenese.
b) Co k tomu budeme potřebovat?
- Tato lekce — definice, trojúhelníková nerovnost, rozbor posunu $+h$.
- [L3.5] TSP je silně NP-těžký — konstrukce s váhami 1 a 2.
- [L3.6] Neexistence r-aproximace — proč se faktor nesmí přenést.
- [L2.15] Škálování vah — kdy posun $+h$ zachová pořadí řešení.
c) Jak nad úlohou uvažovat?
(i) Nedokazuj nic nového — zkontroluj, že stará konstrukce žije uvnitř nové restrikce. (ii) Rozepiš trojúhelníkovou nerovnost pro posunuté ceny a izoluj $h$; pak spočítej, o kolik se zvedne cena každého okruhu. (iii) Napiš záruku aproximace v posunutém světě a převeď ji zpět — sleduj, co se stane s členem $r \cdot nh$.
d) Úplné řešení (vlastní, dle slidu 22)
(i) Důkaz silné NP-těžkosti TSP [L3.5] používá instance s váhami $c \in \{1, 2\}$ (hrana $G$ → 1, nehrana → 2; HC v $G$ existuje $\iff$ OPT $= n$). Tyto váhy trojúhelníkovou nerovnost splňují: nejhorší případ je $1 + 1 \ge 2$, všechny ostatní kombinace ($1{+}2 \ge 2$, $2{+}2 \ge 2$, …) tím spíš. Každá instance konstrukce je tedy metrická a redukce z HC funguje beze změny i pro metrický TSP — ten je silně NP-těžký a (pokud $P \ne NP$) nemá ani pseudopolynomiální algoritmus. Slide 22 (1:1): „Can be proved in the same way as the complexity of TSP because weights 1 and 2 preserve the triangle inequality.“
(ii) Pro $c' = c + h$ chceme $(c(i,j) + h) + (c(j,k) + h) \ge c(k,i) + h$, tj. po úpravě
$$h \ge c(k,i) - c(i,j) - c(j,k) \quad \text{pro všechny trojice } i,j,k.$$Stačí tedy $h \ge \max_{i,j,k}\big(c(k,i) - c(i,j) - c(j,k)\big)$; hrubě (ale vždy bezpečně) $h \ge c_{\max}$, protože pak $c(i,j) + c(j,k) + h \ge h \ge c_{\max} \ge c(k,i)$ (ceny jsou nezáporné). Každá Hamiltonovská kružnice má přesně $n$ hran, takže cena každého okruhu vzroste o stejných $n \cdot h$ — pořadí okruhů se nezmění (výjimka „stejný počet hran“ z [L2.15]), optimální okruh zůstane optimální a kritérium je vyšší o $n \cdot h$ (slide 22, 1:1: „the criterion function is higher by $n * h$“).
(iii) Nechť $\mathcal{A}$ je r-aproximace metrického TSP. Na posunuté instanci platí $c'(H) \le r \cdot \mathrm{OPT}' = r(\mathrm{OPT} + nh)$. Zpět v původních cenách:
$$c(H) = c'(H) - nh \le r \cdot \mathrm{OPT} + (r-1)\,nh.$$Záruka už není násobná — aditivní člen $(r-1)nh$ může být vůči $\mathrm{OPT}$ libovolně velký (a u nemetrických instancí $h$ musí být velké, aby nerovnost spravil). Konzistence s teorií: kdyby se faktor přenášel, dostali bychom polynomiální r-aproximaci obecného TSP, a tedy $P = NP$ podle [L3.6] — mezera $(r-1)n$ v tamní konstrukci je přesně tenhle aditivní člen. $\blacksquare$
Step 3 of the double-tree algorithm transforms a closed walk into a tour: „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.“
(a) Prove the claim of slide 25: „due to the triangle inequality, the skipped nodes don't prolong the route, i.e. $c(E(L)) \ge c(E(H))$“ — for an arbitrary closed walk $L$ visiting all nodes of a metric TSP instance. (b) Verify that the cost matrix from the lesson (nodes A–E) satisfies the triangle inequality, and run the shortcutting on the closed walk $W = A,B,C,B,D,B,A,E,A$.
a) Co je v zadání?
Důkazová mini-úloha + propočet: zdůvodnit obecně, že shortcutting nezdražuje (to je nerovnost ①, kterou pak důkazy faktorů 2 i 3/2 jen citují), a přehrát ho na konkrétní pětivrcholové instanci z výkladu.
b) Co k tomu budeme potřebovat?
- Tato lekce — zobecněná trojúhelníková nerovnost, mechanika shortcuttingu.
- [L3.3] Hamiltonovská kružnice — co přesně má vzniknout.
- [L2.1] — sled vs. cesta (uzavřený sled smí vrcholy opakovat).
c) Jak nad úlohou uvažovat?
(a) Rozděl sled na úseky mezi po sobě jdoucími prvními návštěvami — úseky pokrývají celý sled a žádná hrana sledu není ve dvou úsecích. Každou hranu okruhu $H$ pak porovnej s „jejím“ úsekem zobecněnou trojúhelníkovou nerovností a sečti. (b) U metriky stačí prověřit všech $3\binom{5}{3} = 30$ nerovností (po trojicích; využij symetrii a kontroluj vždy největší cenu v trojici proti součtu zbylých dvou).
d) Úplné řešení (vlastní)
(a) Nechť $L = w_0, w_1, \ldots, w_m$ ($w_m = w_0$) je uzavřený sled obsahující všechny vrcholy a nechť $v_1, v_2, \ldots, v_n$ jsou vrcholy v pořadí prvních výskytů na $L$ (tedy $v_1 = w_0$). Shortcutting vrátí $H = v_1, v_2, \ldots, v_n, v_1$ — každý vrchol právě jednou, v úplném $K_n$ všechny hrany existují, takže $H$ je Hamiltonovský okruh.
Pro každé $i$ je dvojice $v_i, v_{i+1}$ (a nakonec $v_n, v_1$) spojena souvislým úsekem sledu $L$: od výskytu $v_i$, za nímž následovala první návštěva $v_{i+1}$, vede po hranách sledu úsek $L_i$ do $v_{i+1}$ (mezilehlé vrcholy jsou ty přeskočené); poslední úsek $L_n$ vede od posledního z prvních výskytů zpátky do $w_m = v_1$. Úseky $L_1, \ldots, L_n$ na sebe navazují a beze zbytku rozdělí celý sled: $\sum_{i} c(E(L_i)) = c(E(L))$, žádná hrana se nepočítá dvakrát.
Zobecněná trojúhelníková nerovnost (indukcí přes délku úseku; báze = hrana samotná, krok = jedno použití $c(\{u,v\}) \le c(\{u,x\}) + c(\{x,v\})$ na první roh úseku) dává pro každý úsek
$$c(\{v_i, v_{i+1}\}) \le c(E(L_i)).$$Sečtením přes $i = 1, \ldots, n$:
$$c(E(H)) = \sum_{i=1}^{n} c(\{v_i, v_{i+1}\}) \le \sum_{i=1}^{n} c(E(L_i)) = c(E(L)). \qquad \blacksquare$$(Slide 25 tenhle argument shrnuje jednou větou — „due to the triangle inequality, the skipped nodes don't prolong the route“; u zkoušky stačí věta + náčrt úseků a jedné zkratky.)
(b) Metrika. Po trojicích vždy největší cena proti součtu zbylých (ostatní dvě nerovnosti pak platí triviálně, protože ceny jsou kladné): ABC: $3 \le 2{+}1$ ✓; ABD: $3 \le 2{+}2$ ✓; ABE: $3 \le 2{+}2$ ✓; ACD: $3 \le 3{+}2$, $3 \le 3{+}2$ ✓ (remíza největších); ACE: $4 \le 3{+}2$ ✓; ADE: $5 \le 3{+}2$ ✓ (rovnost); BCD: $2 \le 1{+}2$ ✓; BCE: $4 \le 1{+}3$ ✓ (rovnost); BDE: $5 \le 2{+}3$ ✓ (rovnost); CDE: $5 \le 2{+}4$ ✓. Instance je metrická.
Běh. Posloupnost vrcholů na $W$: $A, B, C, \cancel{B}, D, \cancel{B}, \cancel{A}, E, (A)$ → první návštěvy $A, B, C, D, E$, tedy $H = A,B,C,D,E,A$. Úseky a zkratky:
- $A \to B$ a $B \to C$: úseky délky 1, beze změny ($2$, $1$).
- $C \to B \to D$ → zkratka $\{C,D\}$: $2 \le 1 + 2 = 3$ (ušetřena 1).
- $D \to B \to A \to E$ → zkratka $\{D,E\}$: $5 \le 2 + 2 + 2 = 6$ (ušetřena 1; dvojí použití trojúhelníkové nerovnosti).
- $E \to A$: úsek délky 1, beze změny ($2$).
Celkem $c(E(H)) = 2+1+2+5+2 = 12 \le 14 = c(E(W))$. ✓