Problém obchodního cestujícího

Autor: Leandro Alegsa Datum vytvoření: 11. října 2021

Problém obchodního cestujícího (často nazývaný TSP) je klasický algoritmický problém v oblasti informatiky a operačního výzkumu. Je zaměřen na optimalizaci. V tomto kontextu lepší řešení často znamená řešení, které je levnější, kratší nebo rychlejší. TSP je matematický problém. Nejsnáze se vyjadřuje jako graf popisující umístění množiny uzlů.

Problém obchodního cestujícího definovali v 19. století irský matematik W. R. Hamilton a britský matematik Thomas Kirkman. Hamiltonova Ikosova hra byla rekreační hádanka založená na hledání hamiltonovského cyklu. Obecnou podobu TSP zřejmě poprvé studovali matematici ve 30. letech 20. století ve Vídni a na Harvardu, zejména Karl Menger. Menger definuje problém, uvažuje o zřejmém algoritmu hrubé síly a pozoruje neoptimálnost heuristiky nejbližšího souseda:

Problémem posla (protože v praxi by tuto otázku měl řešit každý pošťák, každopádně i mnoho cestujících) označujeme úlohu najít pro ﬁniticky mnoho bodů, jejichž párové vzdálenosti jsou známy, nejkratší trasu spojující tyto body. Tato úloha je samozřejmě řešitelná konečně mnoha pokusy. Pravidla, která by počet pokusů stlačila pod počet permutací daných bodů, nejsou známa. Pravidlo, že je třeba jít nejprve z výchozího bodu do nejbližšího bodu, pak do bodu nejbližšího tomuto atd. obecně nevede k nejkratší trase.

Hassler Whitney na Princetonské univerzitě brzy poté zavedl název problém obchodního cestujícího.

Obchodník chce navštívit všechna města A, B, C a D. Jaký je nejlepší způsob, jak toho dosáhnout (nejlevnější letenky a minimální doba cesty)?

Optimální trasa prodejce, který navštíví 15 největších měst v Německu. Zobrazená trasa je nejkratší z 43 589 145 600 možných tras.

Uvedení problému

Problém obchodního cestujícího popisuje obchodního cestujícího, který musí cestovat mezi N městy. Na pořadí, v jakém tak učiní, mu nezáleží, pokud každé z nich během své cesty jednou navštíví a skončí tam, kde byl poprvé. Každé město je spojeno s dalšími blízkými městy neboli uzly, a to letadly nebo po silnici či železnici. Ke každému z těchto spojení mezi městy je přiřazena jedna nebo více vah (neboli nákladů). Náklady popisují, jak "obtížné" je projít tuto hranu grafu, a mohou být dány například cenou letenky nebo jízdenky na vlak, nebo třeba délkou hrany či časem potřebným k jejímu projití. Prodejce chce, aby náklady na cestu i vzdálenost, kterou urazí, byly co nejnižší.

Problém obchodního cestujícího je typický pro velkou třídu "těžkých" optimalizačních problémů, které již léta zajímají matematiky a informatiky. Nejdůležitější je, že má aplikace ve vědě a technice. Například při výrobě desky plošných spojů je důležité určit nejlepší pořadí, v jakém laser vyvrtá tisíce otvorů. Efektivní řešení tohoto problému snižuje výrobní náklady výrobce.

Obtížnost

Problém obchodního cestujícího je obecně obtížně řešitelný. Pokud existuje způsob, jak tento problém rozdělit na menší složkové problémy, budou tyto složky přinejmenším stejně složité jako původní problém. Tomu informatici říkají NP-těžké problémy.

Tento problém studovalo mnoho lidí. Nejjednodušším (a nejdražším) řešením je jednoduše vyzkoušet všechny možnosti. Problémem je, že pro N měst máte (N-1) faktoriál možností. To znamená, že pro pouhých 10 měst existuje více než 180 tisíc kombinací, které je třeba vyzkoušet (protože počáteční město je definováno, mohou existovat permutace na zbývajících devět). Počítáme pouze polovinu, protože každá trasa má stejnou trasu v opačném směru se stejnou délkou nebo náklady. 9! / 2 = 181 440

Přesné řešení problému lze nalézt pomocí algoritmů větvení a vazeb. V současné době je to možné až pro 85 900 měst.
Heuristické přístupy používají sadu řídicích pravidel pro výběr dalšího uzlu. Protože však heuristiky vedou k aproximacím, neposkytnou vždy optimální řešení, ačkoli kvalitní přípustné heuristiky mohou najít užitečné řešení za zlomek času potřebného pro úplné řešení problému hrubou silou. Příkladem heuristiky pro uzel může být součet toho, kolik nenavštívených uzlů je "blízko" připojeného uzlu. To by mohlo prodejce povzbudit, aby navštívil skupinu blízkých uzlů seskupených dohromady, než přejde na jiný přirozený shluk v grafu. Viz algoritmy Monte Carlo a algoritmy Las Vegas.

Otázky a odpovědi

Otázka: Co je to problém obchodního cestujícího?

Odpověď: Problém cestujícího prodavače (TSP) je klasický algoritmický problém v oblasti informatiky a operačního výzkumu. Zaměřuje se na optimalizaci, přičemž lepší řešení často znamená levnější, kratší nebo rychlejší řešení.

Otázka: Jak se TSP vyjadřuje?

Odpověď: TSP se nejsnáze vyjadřuje jako graf popisující umístění množiny uzlů.

Otázka: Kdo jako první definoval TSP?

Odpověď: Problém obchodního cestujícího definovali v 19. století irský matematik W. R. Hamilton a britský matematik Thomas Kirkman.

Otázka: Kdo se jím dále zabýval ve 30. letech 20. století?

Odpověď: Ve 30. letech 20. století se jím dále zabývali matematici Karl Menger ve Vídni a na Harvardu.

Otázka: Co brzy poté zavedl Hassler Whitney?

Odpověď: Hassler Whitney na Princetonské univerzitě zavedl název "problém obchodního cestujícího" brzy po jeho definici.

Otázka: Co v této souvislosti znamená "lepší řešení"?

Odpověď: V tomto kontextu lepší řešení často znamená řešení, které je levnější, kratší nebo rychlejší.

Otázka: Jaký algoritmus považoval Menger při studiu TSP za samozřejmý?

Odpověď: Menger při studiu TSP považoval za zřejmý algoritmus hrubé síly a vypozoroval, že použití heuristiky nejbližšího souseda nepřináší vždy optimální výsledky.