Всем привет!
Меня зовут Роман Удовиченко и я рад всем сообщить, что первый оптимизационный раунд Яндекс.Алгоритма в самом разгаре! В этот раз мы приглашаем вас порешать задачу от команды разработки беспилотного автомобиля Яндекса.
Беспилотное будущее, как мы надеемся, не за горами, поэтому мы предлагаем вам составить алгоритм для оптимального управления целым флотом беспилотных такси. Разумеется, задача довольно сильно упрощена и в реальности всё гораздо сложнее, но и времени на её решение у вас всего лишь неделя. Написать базовое решение для предложенной задачи очень просто, а вот улучшить его — задача не столь тривиальная. Сможете ли вы придумать и реализовать что-нибудь действительно интересное и необычное? Всё в ваших руках, а времени ещё более чем достаточно :)
Авторов лучших решений в оптимизационном треке ждет денежный приз, а топ-128 — крутые футболки с символикой мероприятия. А если вы хотите попробовать свои силы в разработке настоящего беспилотника, то пишите мне в личные сообщения ;)
Удачи!
There are two optimizations rounds, right? How does it work? Do we get gp30 scores for each?
Yes, rules are the same as for algorithm rounds.
Probably GP30 scores, since there's nothing explicitly written about them. Still, there are no finals and only the top 3 people get non-Tshirt prizes.
The last submission will be used for systest, but when I want to resubmit my old solution with a higher score, it says I can't, nice
Now you can. Hope it helps :)
that was fast, thanks :)
Задача крайне интересная, она сделала мои выходные)))
Спасибо авторам
Can you guys post your approach?
Well, I guess that my solution is mediocre, but whatever (it got slightly above 11k points in open testing stage).
Basically, I assigned an object (a passenger or a zone) to each taxi. On each iteration I shuffled the objects between taxis so that the minimal distance (let's call it dP) between a taxi and an object is as small as possible.
Then I iterated over taxis and checked, whether it's profitable to move a certain taxi in dP direction.
Sometimes no taxis can be moved in dP direction (because of some restrictions). In this case, I just moved the taxi, which is ruining the move, in a random direction by a small vector.
That's basically it.
How did you choose dP direction ? As I've understood this is direction for whole group moving ?
dP is the the shortest possible vector, that connects a taxi and an object.
This is not a direction for the whole group. Instead, it's a direction for a subgroup of taxis. You can greedily decide, whether to include a taxi in this subgroup or not.
My approach.
Taxi driving.
How we can effectively drive a car to some point?
I iterate over all moves starting after last one that contains this car up to end and add car to it if it's profitable.
Then simply add new move directly to target point.
Travel selection.
For each possible travel (car -> fan/zone) I calculated penalty using driving method described above and choose one with lowest score.
Do travel.
Do step 1 for selected travel. If target point occupied then first we push another car to nearby free position.
Do steps 2 and 3 until all fans delivred.
This approach gives around 12k point on pretests.
Improvement
I realized that if we apply some random factor to travel selection then the results are widely scattered.
So I producing solutions until time limit nearly reached and select the best one.
Basically that's all, it's gives around 13k points on pretests.
The most hard part for me is "on fly" detect if cars coordinates coincides. I spent a lot of time to try to guarantee correctness of result but still it's not perfect, in about 0.1% of cases my solution can not produce valid result.
Will we be able to submit solutions afyer the contest has ended?
For training purposes
Upsolving has been opened, feel free to submit your solutions.
Набросок решения
В зависимости от того, что нагенерировалось в тесте, хорошо работает одно из двух решений. Первое строит гамильтонов цикл на пассажирах и водит по нему такси, второе направляет каждое такси к ближайшей цели и перестраивается на лету после каждого изменения.
Решение с гамильтоновым циклом
Из-за маленьких ограничений по времени поиск цикла надо писать весьма аккуратно. В последний день я добавил несколько перезапусков с целью уменьшить дисперсию, так что на каждый поиск цикла у меня уходит 60мс. Сам цикл ищется методом отжига с 2-opt в качестве единственного хода.
После того, как цикл найден, я перебираю первого пассажира и дальше развожу всех пассажиров, начиная с первого, строго в порядке, в котором они идут в цикле, выбирая для очередного пассажира самое подходящее такси.
Я успеваю найти пять разных циклов и перебрать в них сколько-то сдвигов, с которых надо начинать (зависит от числа пассажиров). Если запустить сто разных циклов, то на некоторых тестах итоговые результаты между худшим и лучшим могут отличаться на несколько процентов, причём не обязательно более короткий цикл даст лучший итоговый результат, но мне не удалось гарантированно уловить эту разницу.
Можно для каждого такси отдельно искать место, начиная с которого оно будет проходить цикл, или вообще искать не цикл, а набор путей. У меня не получилось таким решением выиграть сколько-то баллов. Например, если искать набор путей минимального суммарного веса, количество вершин в путях из разных такси начинают сильно различаться, и через какое-то время после начала остаётся только несколько такси, не закончивших работать, и это отрицательно сказывается на второй множитель в пенальти. Если же добавлять ограничение на примерную одинаковость размеров путей, теряется преимущество в итоговой длине по сравнению с циклом.
Решение с перестроением на лету
На каждом шаге для такси выбираются цели. В качестве пассажиров берутся несколько в каком-то смысле ближайших ко всем такси. Количество кандидатов (размер окна) меняется от запуска к запуску в отличие от решения с гамильтоновым циклом, где увеличение даже на единицу ощутимо влияет на результат.
Каждое изменение состояния пассажиров (кто-то подобран или доехал до зоны) приводит к пересчёту всех целей и началу следующего шага.
У меня были также варианты, в которых всё расписание (т.е. для каждого такси последовательность всех пассажиров и зон, которые оно должно посетить) строится заранее, и в которых такси, выбрав пассажира в качестве цели, уже не отдавало его другому такси, даже если то в какой-то момент оказалось ближе. Эти варианты послабее, хотя в паре процентов тестов и набирают приличный результат.
Перемещение такси
После того, как цели назначены, нужно выбрать последовательность команд, которая отправит такси к этим целям. Ближе к началу соревнования я пытался как-то организовывать цели, чтобы можно было захватить за одну команду как можно больше такси, т.е. чтобы у всех такси векторы к целям были направлены более-менее в одну сторону. Это плохо работает, и в итоге лишнее проходимое расстояние является более важным фактором.
Поэтому я просто выбираю ближайшее к цели такси и двигаю вдоль его вектора всех, кого это приблизит. Если сначала сдвинуть на половинное расстояние, а потом на остаток, это добавляет ещё немного очков.
После того, как команда на перемещение создана, она добавляется в ответ и уже не изменяется.
Функции расстояний
Для первого приближения везде подойдёт евклидово расстояние, но на изменении метрик можно выиграть около тысячи очков.
В гамильтоновом цикле расстояние между двумя пассажирами складывается из взвешенных евклидового расстояния между ними и расстояний от каждого из них до их ближайшей общей зоны.
В поисках ближайших зон и пассажиров к такси тоже можно менять метрики. Где-то это помогает, где-то нет.
Мелочи
Запрет на нахождение двух такси в одной точке раздражает поначалу, но забывается после написания правильных вспомогательных функций (немного поменять вектор, чтобы запрещённый ход стал разрешён; убрать из зоны такси перед тем, как туда заезжает другое). Надо также не забыть, что направляющееся к пассажиру такси не должно случайно забрать другого пассажира.
Назначение такси их целям делается венгерским алгоритмом для пассажиров и жадно для зон.
У меня были и локальное тестирование, и простенький визуализатор. Немного неожиданно, что авторы контеста не предоставили ни то, ни другое.
Вывод на стандартный поток ошибок в системе посмотреть нельзя, поэтому о реальном быстродействии решения при настройке констант можно только догадываться.
Очень важно не получить TL/WA/PE, т.к. даже один не пройденный тест из ста существенно отбрасывает назад.
Предварительный результат: 12856.53
Итоговый результат: 9663.44
100 случайных тестов, среднее: 396621
5000 случайных тестов, среднее: 481550