Obchodní cestující (Travelling Salesman)

Problém je pojmenovaný podle obchodníků, kteří jezdili od města k městu a snažili se tam prodat co nejvíce vysavačů, psacích strojů, nebo třeba encyklopedií. Proto se snažili svou cestu vybranými městy naplánovat tak, aby je všechna projeli s minimálními náklady, tedy po co nejkratší trase.

Problém obchodního cestujícího je NP-těžký optimalizační problém, jehož zadání neformálně zní například takto: je dáno několik měst a vzdálenosti mezi nimi. Úkolem je najít takovou cestu, která navštíví každé město právě jednou. Formálně se jedná o nalezení nejméně ohodnocené hamiltonovské kružnice v úplném ohodnocením grafu. Řešením úlohy je posloupnost měst, která udává, v jakém pořadí se mají města projet.

Problém je složitý především proto, že jeho složitost dramaticky narůstá s rostoucím počtem měst.

nejkratší cesta mezi hlavními městy v USA

nejkratší cesta mezi hlavními městy v USA

Praktických využití v plánování či logistice je mnoho, například:

  • v jakém pořadí vrtat díry skrz díl, aby výroba dílu zabrala co nejméně času (díry jsou "města")
  • v jakém pořadí zkoumat hvězdy na obloze, aby se posunem a nastavováním teleskopu strávilo co nejméně času (hvězdy jsou "města")
  • v jakém pořadí dodat poštovní balíky adresátům (adresáti jsou "města")

Řešení

Hrubá síla

Algoritmy používající "hrubou sílu" k nalezení optimálního řešení jsou principiálně velmi jednoduché, ale často jsou použitelné jen pro malé instance problému. Algoritmus zkrátka vygeneruje všechny možné cesty (tj. permutace měst) a vybere z nich takovou, jejíž ohodnocení je nejmenší. Tyto algoritmy vždy najdou optimální řešení, ale kvůli dramaticky narůstající složitosti jsou použitelné jen pokud je počet měst v řádu desítek až stovek.

Heuristika

Pokud z různých důvodů nepotřebujeme najít optimální řešení, ale stačí nám nějaké "dostatečně dobré", lze použít některé heuristické metody, které jsou šak o to rychlejší.

Nejbližší soused
Začíná se v náhodně zvoleném městě. Potom se opakovaně volí takové nenavštívené město, které je nejblíž k tomu aktuálnímu. Po navštívení všech měst se cesta uzavře návratem k prvnímu městu.
Hladový algoritmus
Nejprve se všechny dvojice měst seřadí podle vzdálenosti od nejkratší k nejdelší. Tyto hrany se potom postupně přidávají k výsledné cestě, přičemž se přeskakují ty, které by vytvořily "cyklus" nebo "křižovatku" (v grafové terminologii tedy kružnici nebo uzel se stupněm vyšším než dva).
Vkládání nejbližšího
Cesta je zpočátku tvořena pouze hranou mezi dvěma uzly, které k sobě mají nejblíž. V každém dalším kroce se vybere takové nenavštívené město, které má nejmenší vzdálenost k libovolnému navštívenému městu. Toto město se potom vloží mezi dvě již navštívená města vybraná tak, aby celková délka nově vzniklé cesty byla co nejmenší.
Vkládání nejvzdálenějšího
Podobný postup jako u "vkládání nejbližšího", ale pro maximální vzdálenosti. Cesta je zpočátku tvořena pouze hranou mezi dvěma uzly, které k sobě mají nejdál. V každém dalším kroce se vybere takové nenavštívené město, které má největší vzdálenost k libovolnému navštívenému městu. Toto město se potom vloží mezi dvě již navštívená města vybraná tak, aby celková délka nově vzniklé cesty byla co nejmenší (podobně jako u vkládání nejbližšího).

Reference