Problém obchodního cestujícího

Problém obchodního cestujícího (Travelling salesman problem) je úloha kombinatorické optimalizace, jejíž cílem je nalézt v zadaném ohodnoceném úplném grafu kružnici takovou, že prochází všemi vrcholy a zároveň je její cena minimální. Jinými slovy se jedná o nalezení nejkratší hamiltonovské kružnice v ohodnoceném grafu.

Motivace

V dané zemi existuje mnoho měst, mezi všemi městy je postavené silnice. Cílem obchodního cestujícího je objet všechna města takovým způsobem, aby cena za jízdenky byla minimální (odpovídá vzdálenosti měst) a vrátit se do výchozího města.

Obtížnost problému

Problém je NP-úplný a silně NP-obtížný, což znamená, že pokud platí $P \\neq NP$ , pak pro problém obchodního cestujícího neexistuje žádný polynomiální k-aproximační algoritmus – neexistuje polynomiální algoritmus, který by našel libovolné řešení, které je nejhůře k-násobkem optimálního řešení.

ILP formulace

Pomocí celočíselného lineárního programování lze problém asymetrického obchodního cestujícího (tzn. hrany $A \\rightarrow B$ a $B \\rightarrow A$ nemusejí mít stejnou váhu) formulovat jako:

$\\min \\sum_{i=1}^{n} \\sum_{j=1}^{n} x_{ij} \\cdot c_{ij}$
Za podmínek:
$\\sum_{i = 1}^{n} x_{ij} = 1 \\hspace{20mm} j \\in \\{1, \\cdots, n\\}$
$\\sum_{j = 1}^{n} x_{ij} = 1 \\hspace{20mm} i \\in \\{1, \\cdots, n\\}$
$s_{i} + c_{ij} - (1-x_{i, j}) \\cdot M \\leq s_{j} \\hspace{20mm} i \\in \\{1, \\cdots, n\\} \\;\\; j \\in \\{2, \\cdots, n\\}$
$x_{ij} \\in \\{0, 1\\}$

První dvě podmínky zaručují, že daný uzel bude navštíven právě jednou, třetí podmínka zajišťujě nedělitelnost výsledné hamiltonovské kružnice.

Metrický obchodní cestující

Variantou tohoto problému je problém metrického obchodního cestujícího, ve kterém vzdálenosti na grafu splňují trojúhelníkovou nerovnost. Toto zjednodušení odpovídá velkému množství reálných problémů (např. hledání na mapě), a zároveň umožňuje konstrukci aproximačních algoritmů.

2-aproximační algoritmus

Problém metrického obchodního cestujícího lze řešit jednoduchým algoritmem v polynomiálním čase. Algoritmus nejprve zkonstruuje minimální kostru grafu. Z definice kostry plyne, že $cena(kostra) \\leq cena(optimum)$ protože kostra obsahuje $\\vert U \\vert -1$ minimálních hran, zatímco kružnice jich obsahuje $\\vert U \\vert$ .

V druhém kroku projde algoritmus kostru z libovolného uzlu do hloubky a poznamená si všechny průchody přes vrcholy – protože se jedná o průchod do hloubky, budou zde některé uzly zpracovány vícekrát.

V posledním kroku – zkrácení cest – algoritmus tento seznam projde a vynechá všechny duplicity (zanechá pouze první výskyty uzlů). Tímto dojde k vytvoření samotné kružnice. Protože v grafu platí trojúhelníková nerovnost, tak se cena kružnice oproti původní cestě maximálně zdvojnásobí, tj. platí

$cena(kružnice) \\leq 2 \\cdot cena(kostra) \\leq 2\\cdot cena(optimum)$

Příklad

2-aproximační algoritmus - příklad

V levé části ilustrace je zkonstruována minimální kostra grafu (například pomocí Kruskalova algoritmu). Poté byl graf prohledán do hloubky z uzlu , algoritmus vrátil pořadí uzlů A, B, A, D, E, D, A, C, A . Poslední krok agoritmu tuto cestu zkrátil na kružnici A, B, D, E, C (pravá část ilustrace).

Christofidesův algoritmus

Christofidesův algoritmus řeší problém metrického obchodního cestujícího tak, že je výsledná trasa v nejhorším případě dlouhá 3/2 délky trasy optimálního řešení. Toto zlepšení je ovšem vykoupeno výrazně obtížnější implementací, a zároveň se na reálných datech ukazuje, že výsledek není v průměrném případě o mnoho lepší než při použití 2-aproximačního algoritmu uvedeného výše.

Christofidesův algoritmus nejprve zkonstruuje minimální kostru grafu. Poté kostru projde z libovolného uzlu do hloubky a vybere ty uzly, jež mají lichý stupeň a zkonstruuje na nich úplný graf . Na grafu nalezne nejlevnější perfektní párování . Hrany z přidá do minimální kostry. Graf $K \\cup P$ je nyní eulerovský (tzn. existuje v něm tah, který obsahuje všechny hrany grafu). Algoritmus nyní nalezne eulerovský tah – výsledná trasa odpovídá pořadí prvních návštěv uzlů při konstrukci tohoto tahu.