Studenti informatiky z Fakulty elektrotechnické ČVUT bodují na světové úrovni.
Studenti doktorského studia Petr Váňa, Robert Pěnička a výzkumník Vojtěch Vonásek z katedry počítačů FEL ČVUT se v říjnu zúčastnili 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 úkolem 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.
„Večer před začátkem soutěže jsem si o ní přečetl článek na webu a okamžitě jsem si řekl, že máme šanci, protože já i Petr řešíme v rámci doktorského studia na Fakultě elektrotechnické podobné problémy. Hned další den ráno jsem mu napsal a ještě spolu s Vojtou jsme vytvořili tým,“ říká Robert Pěnička, jeden z členů týmu.
Vítězné řešení se podařilo najít právě trojici výzkumníků z ČVUT, a to prostřednictvím Breadth-first search (BFS) algoritmu, 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ů. „Pro úlohu obchodního cestujícího by ovšem klasický BFS algoritmus nezvládl vyzkoušet všechny možné kombinace letů, protože jejich počet vzrůstá exponenciálně s počtem navštívených měst (tzv. kombinatorická exploze),” vysvětluje Petr Váňa, další ze členů týmu. “Bylo tedy nezbytně nutné strom obsahující možné kombinace letů vhodně prořezávat.” To by ovšem mohlo odstranit kvalitní řešení, a proto autoři do algoritmu přidali takzvané heuristiky, které na základě částečného řešení (několik prvních letů) odhadovaly výslednou cenu a umožňovaly odstraňovat neperspektivní kombinace letů. Důležitým aspektem vítězného řešení byla také vhodná optimalizace, která umožnila vyzkoušet více než sto milionů letů během časového limitu omezeného na 15 sekund.
„Stejně jako další soutěže a akce, které pořádáme, i Travelling Salesman Challenge je pro nás způsob, jak se spojit s nadějnými talenty a vzájemně navázat dobré vztahy. Díky tomu se dozvídáme, jak a na čem třeba právě studenti na ČVUT pracují a poznáváme zajímavé projekty a výzkumy. V Kiwi.com máme zase kvanta zajímavých dat, která mohou být pro studenty a jejich výzkum zajímavá i do budoucna,“ říká Jan Plhák, který v Kiwi.com vede tým zodpovědný za vývoj NOMADa a problém obchodního cestujícího tak převádí do praxe.
Vítězství tří výzkumníků znamená úspěch i pro FEL a centrum umělé inteligence (Artificial Intelligence Center), kde všichni působí.
„Pro AIC je úspěch v soutěži velmi cennou trofejí. Je zajímavé vidět, že naše zkušenost a technické znalosti v oblasti umělé inteligence představují kompetitivní výhodu při řešení netriválních průmyslových výzev,” říká prof. Michal Pěchouček z centra umělé inteligence AIC na FEL ČVUT. Dle jeho slov jsou v AIC oblíbené zejména průmyslové a aplikační problémy, které výzkumníkům umožňují se efektivně pohybovat na hraně technologického pokroku. „Kiwi.com tu navíc všichni fandíme, startup, který uspěje v mezinárodní konkurenci, je pro nás obrovskou motivací. I v rámci AIC se rekrutují některé úspěšné projekty,” dodává s tím, že největší úspěchy má centrum v oblastech plánování, robotiky, inteligentních dopravních systémů, cyber security nebo teorie her.
