Algoritmus Christofides - Christofides algorithm

Christofides algoritmus nebo algoritmus Christofides-Serdyukov je algoritmus pro nalezení přibližné řešení k problému obchodního cestujícího , v případech, kdy jsou vzdálenosti tvoří metrický prostor (jsou symetrické a poslouchat trojúhelník nerovnost ). Jedná se o aproximační algoritmus, který zaručuje, že jeho řešení bude v rozmezí 3/2 optimální délky řešení, a je pojmenován po Nicosovi Christofidesovi a Anatoliji I. Serdyukovovi , kteří jej objevili nezávisle v roce 1976.

Tento algoritmus stále stojí jako nejlepší algoritmus aproximace polynomiálního času, který byl důkladně přezkoumán příslušnou vědeckou komunitou pro problém obchodního cestujícího v obecných metrických prostorech. V červenci 2020 však Karlin, Klein a Gharan vydali předtisk, ve kterém představili nový aproximační algoritmus a tvrdili, že jeho aproximační poměr je 1,5 - 10 ⁻³⁶ . Jejich metoda se řídí podobnými principy jako Christofidesův algoritmus, ale místo náhodného stromu používá náhodně vybraný strom z pečlivě zvoleného náhodného rozdělení.

Algoritmus

Nechť $G = (V, w)$ je příkladem problému obchodního cestujícího. To znamená, že $G$ je kompletní graf na množině $V$ vrcholů a funkce $w$ přiřadí každé hraně $G$ nezápornou skutečnou váhu . Podle nerovnosti trojúhelníku by pro každé tři vrcholy $u$ , $v$ a $x$ mělo platit, že $w (uv) + w (vx) \geq w (ux)$ .

Potom lze algoritmus popsat v pseudokódu následovně.

Vytvořte minimální kostra $T$ a $G$ .
Nechť $O$ je množina vrcholů s lichým stupněm v $T$ . Podle handshaking lemmatu , $O$ má sudý počet vrcholů.
Najděte v indukovaném podgrafu daném vrcholy z $O$ dokonalou shodu $M$ s minimální hmotností .
Zkombinujte hrany $M$ a $T$ a vytvořte spojený multigraf $H,$ ve kterém má každý vrchol rovnoměrný stupeň.
Tvoří Eulerian obvod v $H$ .
Přeměňte obvod nalezený v předchozím kroku na hamiltonovský obvod přeskočením opakovaných vrcholů ( zkratka ).

Aproximační poměr

Cena řešení vytvořeného algoritmem je v rozmezí 3/2 optima. Chcete-li to dokázat, nechte $C$ být optimální prohlídkou obchodního cestujícího. Odstraněním hrany z $C$ vznikne kostra, která musí mít váhu alespoň váhu minimálního kostry, z čehož vyplývá, že $w (T) \leq w (C)$ . Dále číslujte vrcholy $O$ v cyklickém pořadí kolem $C$ a rozdělte $C$ na dvě sady cest: ty, ve kterých má první vrchol cesty v cyklickém pořadí liché číslo a ty, ve kterých má první cesta vrchol sudé číslo . Každá sada cest odpovídá dokonalému párování $O,$ které odpovídá dvěma koncovým bodům každé cesty, a váha tohoto párování se maximálně rovná hmotnosti cest. Protože tyto dvě sady cest rozdělení okraje $C$ , jeden ze dvou sad má maximálně polovinu hmotnosti $C$ , a to díky nerovnosti trojúhelníku její odpovídající přizpůsobení má hmotnost, která je také nejvýše polovina hmotnosti $C$ . Dokonalé přizpůsobení minimální hmotnosti nemůže mít větší váhu, takže $w (M) \leq w (C) / 2$ . Přidáním vah $T$ a $M získáte$ váhu turné Euler, maximálně $3 w (C) / 2$ . Díky nerovnosti trojúhelníku nezkracuje zkratka váhu, takže váha výstupu je také maximálně $3 w (C) / 2$ .

Dolní hranice

Existují vstupy do problému obchodního cestujícího, které způsobují, že Christofidův algoritmus najde řešení, jehož aproximační poměr je libovolně blízký 3/2. Jedna taková třída vstupů jsou tvořeny cestou z $n$ vrcholů, s okraji dráhy, které mají hmotnost $1$ , spolu se sadou hran spojujících vrcholy dva kroky od sebe v dráze s hmotností $1 + ε$ pro číslo $e$ zvolené blížící se nule, ale pozitivní. Všechny zbývající okraje celého grafu mají vzdálenosti dané nejkratšími cestami v tomto podgrafu. Potom bude minimální kostra dána cestou o délce $n - 1$ a jedinými dvěma lichými vrcholy budou koncové body cesty, jejichž dokonalé přizpůsobení se skládá z jedné hrany o hmotnosti přibližně $n / 2$ . Spojení stromu a shody je cyklus bez možných zkratek as váhou přibližně $3 n / 2$ . Optimální řešení však používá hrany váhy $1 + ε$ společně se dvěma hranami hmotnosti $1, které$ dopadají na koncové body cesty, a má celkovou hmotnost $(1 + ε) (n - 2) + 2$ , blízko $n$ pro malé hodnoty $ε$ . Proto získáme přibližný poměr 3/2.

Příklad

	Dáno: kompletní graf, jehož okrajové váhy se řídí nerovností trojúhelníku
	Vypočítejte minimální kostru $T$
	Vypočítejte množinu vrcholů $O$ s lichým stupněm v $T$
	Vytvořte podgraf $G$ pouze s vrcholy $O$
	Vytvořte v tomto podgrafu dokonalou shodu $M$ s minimální hmotností
	Spojte odpovídající a překlenující strom $T \cup M$ a vytvořte euleriánský multigraf
	Vypočítejte Eulerovu prohlídku
	Odstraňte opakované vrcholy, čímž získáte výstup algoritmu