Skip to main content

Traveling salesman problem

Projekt:
Zameranie projektu:
Fáza projektu:

TSP sa zaoberá problémom, keď obchodný zástupca má navštíviť istý počet miest, pričom každé mesto iba raz pri najmenšej vzdialenosti potrebnej na cestovanie. Tento problém je jednoduchý pri malom počte miest, ale pri ich narastajúcom počte narastá aj množstvo možných kombinácií. Riešenie sa môže javiť ako nedôležité z praktického hľadiska, ale má uplatnenie napríklad pri návrhoch integrovaných obvodov s potrebou konštantného času medzi signálmi, pri rezaní materiálov s čo najmenším odpadom, zoskupovaní dátových polí, alebo analýze kryštalických štruktúr. Optimálne riešenie doteraz nebolo nájdené a matematici určili za najlepší variant riešenia algoritmus s polynómovou variáciou, ktorá berie do úvahy počet miest potrebných navštíviť. TSP rieši prípad, keď treba navštíviť hlavné mestá 48 štátov kontinentálneho USA (vyradené sú štáty Aljaška a Hawaj). Projekt je v súčasnosti pozastavený s poslednou informáciou od autora projektu z 15. mája 2008.

Javascript is required to view this map.