Studenti pražského FELu zvítězili v mezinárodní soutěži efektivity AI
Tým složený ze studentů doktorského studia Petra Váni, Roberta Pěničky a výzkumníka Vojtěcha Vonáska z katedry počítačů FEL ČVUT se v říjnu zúčastnili developerské soutěže pořádané technologickou společností Kiwi.com. Jejich úkolem bylo vytvořit co nejideálnější algoritmus pro řešení tzv. problému obchodního cestujícího. Trojice uspěla v mezinárodní konkurenci více než 500 týmů 50 národností a 8697 odevzdaných řešení
Tato úloha, zabývající se hledáním ideální cesty mezi místy na mapě, bez ohledu na jejich pořadí se řadí do skupiny problémů označovaných jako NP-hard problém. Už pro 10 různých měst existuje přes 180 000 kombinací.
Účastníci letošního ročníku měli za úkol vyvinout algoritmus pro hledání letenek, který dokáže najít ideální cestu pro cestujícího, který chce navštívit určitý počet destinací a v každé z nich se zdržet právě jeden den.
„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
Tým k řešení využil metodu Breadth-first search (BFS) algoritmu, který se běžně používá pro prohledávání kombinatorických úloh. „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 vyřešili studenti tím, že naučili systém odhadovat ceny letů, podle několika počátečních pokusů. Cenově nerelevantní cesty potom vůbec neřešil. Porotu zaujala hlavně optimalizace, díky které zvládl program vyzkoušet více než sto milionů letů během časového limitu omezeného na 15 sekund.
„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.
Zdroj: Tisková zpráva
