L3.14 Kapitola K3 — Důkaz / teorie (Slot 3) · [NICE] · mikro-lekce (odložitelná)

k-OPT local search [NICE]

Poslední lekce K3 — a tečka za TSP. Z [L3.1] víš, že nearest neighbor okruh sice vyrobí, ale nic neslibuje (heuristika). Z [L3.9] a [L3.10] máš aproximace s faktory 2 a 3/2 pro metrický TSP [L3.8a]. Dnešní otázka je jiná: okruh už nějaký mám — jde levně vylepšit? Slide 28 odpovídá principem, kterému se říká local search (lokální prohledávání), a jeho TSP instancí je algoritmus $k$-OPT — podle slidu „one of the most successful techniques for TSP instances in practice“.

Local search: dvě rozhodnutí (slide 28)

Tedy: startovní řešení dodá libovolná heuristika (klidně nearest neighbor) a pak se řešení opakovaně „pošťuchuje“ malými úpravami. Návrh konkrétního local search algoritmu = zodpovědět dvě rozhodnutí: (1) jaké úpravy jsou povolené (to definuje „okolí“ řešení), (2) kdy úpravu přijmout ($k$-OPT přijímá jen zlepšení — improvements only).

Algoritmus $k$-OPT (slide 29)

1. Let H be any Hamiltonian circuit;
2. Let S be the family of k-element subsets S of E(H);
   for all S ∈ S do            // outer loop deals with removed edges
       for all Ham. circuits H' ≠ H such that E(H') ⊇ E(H) \ S do
                                // inner loop deals with inserted edges
           if c(E(H')) < c(E(H)) then H := H' a go to 2.;
       end
   end

Vnější smyčka vybírá, kterých $k$ hran okruhu se zbavit; vnitřní smyčka zkouší všechny okruhy $H' \ne H$, které zbylé hrany $E(H)\setminus S$ obsahují (tj. doplňují je nějakými novými hranami). Jakmile nějaký $H'$ vyjde ostře levněji, stane se novým $H$ a vše začíná znovu od kroku 2 — s novou rodinou $\mathcal{S}$, protože okruh (a tedy jeho hrany) se změnil.

2-opt: zisk výměny (slide 30)

Drobnost, která u písemky dělá dobrý dojem: po 2-opt výměně se jeden z oblouků projíždí v opačném směru („path $(b,\ldots,d)$ has changed orientation“). U symetrického TSP je to jedno ($c$ nezávisí na směru), u asymetrického by se cena oblouku přepočítávala celá — proto se 2-opt v této podobě používá pro symetrické instance.

Běh 2-OPT na známé instanci

Vezmi metrickou $K_5$ z [L3.8a] (tabulka cen tam; $c(A,B){=}2$, $c(B,C){=}1$, $c(C,D){=}2$, $c(D,E){=}5$, $c(E,A){=}2$, $c(A,D){=}3$, $c(B,E){=}3$, …) a jako startovní okruh výstup double-tree algoritmu z [L3.9]: $H = A,B,C,D,E,A$ s cenou $12$ (tentýž okruh dostaneš i shortcuttingem v [L3.8a]).

Po výměně algoritmus skočí na krok 2 a prověří novou rodinu $\mathcal{S}$ — a žádná z pěti výměn už nepomůže (zisky $+1, +1, +1, +4, +3$, propočet v T02). Algoritmus končí: $H' = A,D,C,B,E,A$ je 2-OPT lokální optimum. Na téhle malé instanci je to shodou okolností i globální optimum ($\mathrm{OPT} = 11$ enumerací, [L3.8b]) — ale to je výjimka malé instance, ne pravidlo.

3-opt a 4-opt „double bridge“ (slidy 30–31)

Pro $k = 3$ už vnitřní smyčka jednou neproběhne: po vyhození tří navzájem nesousedních hran zbydou tři oblouky a slide 30 ukazuje at least two ways, jak je pospojovat do nového okruhu (jeden bez otáčení oblouků, druhý s otočením oblouku $(c,\ldots,b)$).

A pro $k = 4$ slide 31 ukazuje slavnou rekonstrukci: One possible solution called the "double bridge" - no path has changed orientation (1:1). Čtyři oblouky se přeskládají do jiného pořadí, aniž by se kterýkoli z nich otáčel — proto je double bridge oblíbený i pro asymetrický TSP a jako „rozkopávací“ tah, který 2-opt neumí napodobit.

Heuristika, ne aproximace

Nebezpečná polopravda

„2-OPT našel na naší instanci optimum, takže je to aproximační algoritmus.“ — NE. Lokální optimum ($k$ hran nepomůže vyměnit) obecně není globální optimum a žádný faktor $r$ pro $k$-OPT dokázán není: je to heuristika, stejně jako nearest neighbor [L3.1]. Záruky mají až aproximace pro metrický TSP: double-tree (faktor 2) [L3.9] a Christofides (faktor 3/2) [L3.10]. V praxi se obojí kombinuje: aproximace dodá startovní okruh se zárukou, $k$-OPT ho dál vylepšuje.

Key takeaways — L3.14

• Local search = princip daný dvěma rozhodnutími (slide 28): which modifications are allowed + when to modify the solution ($k$-OPT: výměna $k$ hran okruhu; jen ostrá zlepšení).
• $k$-OPT (slide 29): vyhoď $k$-prvkovou podmnožinu $S \subseteq E(H)$, projdi všechny okruhy $H' \ne H$ s $E(H') \supseteq E(H)\setminus S$; je-li $c(E(H')) < c(E(H))$, přijmi a začni znovu.
• 2-opt: po vyhození 2 nesousedních hran existuje právě jedna nová rekonstrukce; zisk $= c(a,d) + c(b,c) - c(c,d) - c(a,b)$, oblouk $(b,\ldots,d)$ otočí orientaci (slide 30).
• 3-opt má aspoň 2 rekonstrukce; 4-opt „double bridge“ přeskládá 4 oblouky bez otáčení (slide 31).
• $k$-OPT skončí v lokálním optimu — heuristika bez záruky faktoru; doplněk k aproximacím [L3.9], [L3.10], ne jejich náhrada.