Studenti FEL nejefektivněji řešili tzv. problém obchodního cestujícího a vyhráli cestu kolem světa

Studenti doktorského studia Petr Váňa z katedry počítačů, Robert Pěnička a vědec Vojtěch Vonásek z katedry kybernetiky Fakulty elektrotechnické ČVUT se v říjnu zúčastnili developerské soutěže pořádané technologickou společností Kiwi.com, během níž měli za úkol řešit tzv. problém obchodního cestujícího. Jejich úlohou bylo navrhnout algoritmus, který bude nabízet nejlevnější letecká spojení mezi vybranými oblastmi. Trojice uspěla v mezinárodní konkurenci více než 500 týmů 50 národností a 8697 odevzdaných řešení.

Problém obchodního cestujícího (travelling salesman) je považován za jeden z nejnáročnějších úkolů (řadí se do skupiny problémů označovaných jako NP-hard* problem). Obchodní cestující musí navštívit všechna zadaná města, u nichž není předem určené jejich pořadí. Klade si tedy základní otázku, jaký je nejefektivnější způsob, jak všechna  tato města navštívit. To, co dělá tento problém náročným, je ohromné množství možných kombinací - například už pro 10 různých měst existuje přes 180 000 kombinací. Aby obchodní cestující našel tu pravou kombinaci, musel by je vyzkoušet všechny, proto jsou k řešení využívány moderní technologie a algoritmy.

Letos s podobným úkolem přišla technologická společnost zaměřená na vyhledávání a prodej letenek Kiwi.com. Vyhlásila programátorskou soutěž, během které měli účastníci najít ideální algoritmus pro cestujícího, který chce navštívit n oblastí a v každé oblasti právě jedno město. V jednotlivých destinacích se navíc může zdržet jediný den, poté ze stejného letiště cestovat dále.

Vítězné řešení se využívá algoritmus Breadth-first search (BFS), který se běžně používá pro prohledávání kombinatorických úloh. Takovou úlohou může být například i desková hra šachy, ve které by algoritmus procházel možné budoucí kombinace tahů.

O úspěchu našich studentů informovala média: vedavyzkum.cz, iHNed.cz, nebo oTechnice.cz.

 

Za obsah odpovídá: