На этой неделе мы объявили победителей нашего Конкурса коммивояжеров. Из почти 800 участников мы не могли найти более достойного победителя, чем Петр Лавичка.
Много лет назад Петр пообещал родителям, что отвезет их в какое-нибудь далекое место, где мечтают, например, на Гавайи. Теперь он выполнил это обещание.
Петр подумал, что его родители никогда не приняли бы такой подарок, если бы он заплатил за него своими деньгами, поэтому вместо этого он ввел их в свою команду в качестве «участников» нашего конкурса - без их ведома.
Мы поставили перед сообществом разработчиков задачу решить давнюю проблему np-hard. Мы использовали реальные данные о рейсах Kiwi.com, и им нужно было найти лучший маршрут для посещения всех городов из данного списка. На самом сложном уровне командам предстояло найти лучшую цену на посещение 300 городов за одну поездку.
Более десяти лет назад родители Петра продали свой дом в Йиглаве, где он вырос, чтобы он, его брат и сестра получили лучшее образование. Теперь вся семья живет вместе недалеко от Праги, у каждого своя квартира в одном большом доме. В свободное время Петр ремонтирует дом, играет в хоккей, изучает C ++ и ходит в спортзал с братом и зятем.
Чтобы отпраздновать тот момент, когда он был объявлен нашим чемпионом, мама Петра обняла его, и он и его брат стукнулись кулаками, прежде чем он подошел, чтобы принять свой гигантский чек. Они приехали сюда вместе на церемонию награждения. Его родители никогда раньше не летали, и Петр был очевиден радость от того, что смог выполнить свое обещание.
Чтобы создать победившее решение, он взял всего один день отпуска из своей работы в OKSystem, где он работает руководителем группы разработки программного обеспечения.
Нам было интересно узнать об этой великолепной команде, которая состояла из участников с одной фамилией. Мы предполагали, что разработчик надеялся взять с собой детей в кругосветное путешествие. Мы были близки.
Остальные команды-победители также полностью заслужили своего успеха. Все они объединились в Impact Hub Brno, где мы проводили мероприятие, и на афтепати в Malej Velkej.
Наши серебряные призеры
В команде, занявшей второе место, вошли трое парней из Словакии - Юрай Шкварла, Растислав Кудла и Томаш Путноки.
Юрай и Растислав приехали из Кошице на мероприятие. Они знают друг друга со школы и оба увлекаются сноубордингом. Юрай - химик в APIGENEX sro, а Растислав работает в Техническом университете Кошице с Томашем.
Совокупные познания Джурая в химии и программировании просто завораживают. Он сравнил один из их алгоритмов с процессом отпуска стали для повышения ее прочности. Еще он талантливый спортсмен, специализирующийся на десятиборье.
Растислав любит адреналиновые виды спорта и катается на горных велосипедах и занимается рафтингом, когда нет снега для катания. Со своим призом они могут отправиться в теплое место с солнечными пляжами и пальмами, хотя Скандинавия также подошла как вариант.
Наши бронзовые призеры
Третье место заняла группа ребят из Праги, давно знакомых друг с другом - Ондржей Ямришка, Ян Келлер и Рене Кратохвил.
Двое из них вместе ходили в начальную школу, и все они учились в одной средней школе. Ондра в настоящее время работает в области компьютерной графики в Чешском техническом университете в Праге, а Ян специализируется на технологиях визуального распознавания в Eyedea. Они использовали грубую силу намного больше, чем две другие команды-победители, и достигли результата, очень близкого к результату команды, занявшей второе место.
Эта проблема
Шесть месяцев назад Kiwi.com решил Задачу коммивояжера, чтобы мы могли начать предлагать нашим более предприимчивым путешественникам совершенно новый и уникальный способ планирования своих поездок в MultiCity. Проблема была сложной, и после ее решения мы хотели поделиться опытом с нашими последователями code.kiwi.com и большим ИТ-сообществом. Ради конкуренции мы удалили факторы, которые еще больше усложняли бы решение, например, желаемое время пребывания в каждом городе.
Взгляните на Резюме Ондржея Веселы, чтобы узнать, какие технологии мы использовали для проведения этого конкурса.
Выигрышное решение
Из 293 команд только 71 дошла до SSH, и только 49 из них вернули результаты в течение 30 секунд для всех уровней - до уровня 300 городов.
Среди трех лучших команд была определенная закономерность. Все они использовали C ++, и все они знали друг друга очень давно.
Две лучшие команды имели очень похожие решения, обе использовали алгоритм имитации отжига. Сначала они получили случайную перестановку, а затем поменяли местами города. Когда цена становилась лучше, они соглашались с новым состоянием, но также учитывали, как далеко они были от начала. Этот алгоритм превосходит алгоритм восхождения на холм, потому что он использует охлаждение для получения глобального оптимума вместо локального.
Разница между первым и вторым местом была горячей темой. Петру удалось получить самую низкую цену, потому что на уровне 300 городов он сделал 120 миллионов обменов, что вдвое увеличило скорость команды, занимающей второе место. Решение Петра включало распараллеливание с разными начальными числами рандомизации на каждом из четырех процессорных ядер сервера.
Как Kiwi.com решил эту проблему?
Мы использовали грубую силу с хорошо настроенной реализацией C ++. Нам также нужно обыскать небольшое количество городов, потому что никто в здравом уме не захочет посетить 300 городов за одну поездку. Нам все еще нужно учитывать другие факторы, такие как время пребывания в каждом городе, что увеличивает сложность в геометрической прогрессии.
Спасибо всем участникам!
Нас очень воодушевил позитивный настрой, который вы внесли в конкурс и церемонию награждения. Большое спасибо за ваше участие. Следите за обновлениями, потому что в ближайшем будущем мы будем проводить больше подобных соревнований.
Взгляните на некоторые картинки с мероприятия, результаты, наши слайды и видеоматериалы.
