Мой первый опыт решения неточных задач или почему стоит заниматься олимпиадами

Только что закончился vk winter quest — мини соревнование по решению неточных задач, о котором я совершенно случайно узнал за день до начала и решил, что это будет неплохим способом занять время на новогодних каникулах. Задача, которую предлагалось решить, была связана с гонками на клетчатой бумаге. Опуская некоторые подробности (о которых вы можете почитать на сайте соревнования), задача заключалась в том, чтобы из заданной стартовой клетки обойти за наименьшее количество шагов все целевые клетки. Неожиданно для меня, мое решение показало себя очень хорошо и забралось в топ-3. Наверное поэтому меня и попросили его описать, чем я сейчас и буду заниматься, попутно объясняя, как я к нему пришел.

Подступаемся к задаче

Когда нет идей, что делать с задачей, первое, что стоит попробовать сделать — решить более простую ее версию. Как можно ее упростить? Ну, нам нехило мешает решать задачу то, что целевых клеток много и мы не знаем, в каком порядке их лучше обходить, поэтому давайте уменьшим количество целевых клеток до одной и попробуем решить задачу для этого случая. А именно, предположим мы находимся в клетке с координатами (x_s, y_s) и хотим за наименьшее количество ходов попасть в клетку (x_t, y_t) при том, что есть клетки, в которые мы не можем наступать, за границы поля мы выходить не можем и у каждой клетки поля есть свой показатель максимального ускорения (в данной задаче было 3 типа клеток: со значением максимального ускорением 0 (лед), 1(снег) и 2 (дорога)), улучшения клеток пока рассматривать не будем. Текущее состояние саней можно описать четыремя числами: (x, y, dx, dy) — текущие координаты саней и их текущая скорость. Из этого состояния мы можем сделать переход в состояние (x + dx + ddx, y + dy + ddy, dx + ddx, dy + ddy) (ddx и ddy это ускорение по оси x и по оси y соответвтвенно, они ограничены по модулю максимальным ускорением клетки (x, y)). Далее не сложно свести задачу к графовой: в графе есть стартовая вершина (xs, ys, 0, 0), мы хотим найти кратчайший путь из нее в одну из конечных вершин, конечной будет вершина вида (xt, yt, a, b) для любых a и b, т.к. скорость, с которой мы приедем в конечную клетку нам не важна. Эту задачу можно решить любым алгоритмом для поиска кратчайших путей (например bfs). Доказательство того, что этот алгоритм работает за , где n и m — длины сторон поля, оставим читателям как упражнение. Конечно тут можно придумать что-то более хорошее, например A^*, но для него нужна хорошая оценка снизу на оставшееся расстояние, а за 5 минут у меня ее придумать не получилось и я решил, что эта часть и так неплохо работает.

Постепенно возвращаемся к исходной задаче

Далее есть два пути, по которым мы можем приближать задачу, которую мы умеем решать к исходной: качественный и количественный, начнем, пожалуй, с качественного.

Допустим теперь, у нас не одна целевая клетка, а несколько и мы хотим их посетить за наименьшее количество шагов, как это решать хоть как-нибудь? В прошлый раз неплохо сработали графы, попробуем то же самое провернуть и тут. Теперь просто информации о положении саней нам будет недостаточно, нужно еще как-то понимать, какие целевые клетки мы еще не посетили. Первое и самое наивное решение — добавить пятым параметром в состояние подмножество целевых клеток, которые мы посетили, хранить это можно в виде битовой маски, если целевых вершин не много. Итого получается решение за , где k — количество целевых клеток. К сожалению этот подход в текущем виде неприменим к исходной задаче, т.к. в ней k=176 и этот алгоритм на текущем железе не успеет найти ответ до тепловой смерти вселенной. Далее хочется попытаться придумать какие-то оптимизации для этого решения, которые позволят убрать k из показателя степени, но кажется, что эта задача принадлежит классу NP и ее абсолютно оптимальное решение все равно будет зависеть экспоненциально от k, так что этот алгоритм сильно лучше не сделать.

Теперь рассмотрим количественный путь. В качественном пути мы уткнулись в невозможность решить задачу точно и быстро, но что если мы хотим решить задачу хоть как-нибудь, но за разумное время? Основная проблема в этой задаче, как я говорил в самом начале, в том, что мы не знаем, в каком порядке нужно обходить целевые вершины, именно из-за этого в предыдущем решении всплывает k в показателе степени. Что ж, давайте попробуем это исправить — зафиксируем порядок, в котором будем обходить целевые клетки. Эту задачу можно решить так же, как и простую версию лишь с одним дополнением: в состояние нужно добавить еще одно число — номер целевой вершины, которую мы хотим посетить сейчас. Как только мы приходим в целевую вершину, которую хотели посетить, делаем +1 в этом параметре состояния, говоря тем самым, что теперь мы хотим идти к следующей. Это уже работает за и как-то применимо к исходной задаче, но не очень, т.к. порядка мы не знаем. Тем не менее его можно попытаться подобрать локальными оптимизациями вроде отжига, но это долго и почти наверняка не даст достаточно хороший ответ, т.к. в этом комбинаторном пространстве достаточно много плохих локальных минимумов из-за структуры задачи.

Так как решать?

Чтобы придумать хорошее решение, нужно посмотреть на входные данные (в задаче был ровно один тест и он был в открытом доступе). Карта выглядит так:

Тут синее это лед, белое — снег, серое — дорога, зеленое — целевая клетка, красное — стартовая клетка, черное — стена.

Что можно сказать, глядя на эту карту? Видно, что целевые клетки расположены группами, а так как целевая клетка имеет значение наибольшего ускорения такое же, как и дорога, то, находясь на целевых клетках, сани мобильные и почти наверняка в оптимальном ответе будут посещать клетки одной группы последовательно, это и стало ключом к решению.

Как решать теперь?

Предположим, что мы знаем, в каком порядке оптимальнее всего посетить эти группы клеток, как решать задачу в этом случае? Несложно заметить, что в каждой группе маленькое количество целевых клеток, а значит внутри группы можно применить алгоритм, который ищет наиболее оптимальный ответ. А для того, чтобы последовательно обойти все группы, можно применить второй описанный алгоритм. Короче говоря, нужно скрестить быстрый и качественный алгоритмы и получить кучу баллов. Как это будет выглядеть: текущее состояние будем описывать 6 (шестью!) параметрами: (x, y, dx, dy, gnum, gmask) — текущие координаты и скорость саней, номер текущей группы, которую мы хотим обойти и подмножество клеток в текущей группе, которое мы еще не обошли. И в графе этих состояний мы хотим найти кратчайший путь от стартового состояния до какого-нибудь конечного и задача решена. Оценивать асимптотику этого я не хочу, к тому же она будет иметь мало общего с реальностью, т.к. в реализации я использовал эвристики, которые очень сильно ускоряют это решение. Осталось три вопроса: как использовать улучшение клеток, как разбить целевые клетки на группы (не ручками, разумеется, мы же программисты) и как определить оптимальный порядок посещения групп. Начнем с того, что попроще

Добавляем улучшение клеток

В исходной задаче можно было потратить одно действие и улучшить одну клетку (из льда сделать снег, из снега дорогу). Чтобы алгоритм мог учитывать и такую возможность, достаточно сделать одно наблюдение: почти наверняка, если мы где-то улучшаем клетку, мы пройдем через нее не более одного раза. Это связано с правилами хода и структурой поля. В частности это связано с тем, что рядом со всеми домами есть хотя бы снег, и он дает уже неплохую мобильность саням, а так же с тем, что целевые клетки имеют характеристику такую же, как и дороги, т.е. можно ходить только по ним и иметь неплохую мобильность. А в зоне между группами домов мы вряд ли побываем дважды. Как это наблюдение помогает решить задачу: давайте будем учитывать улучшение клетки при переходе в графе, а именно, если мы, например, находимся на льду, то мы можем изменить скорость, например, на 1, но при этом должны потратить на одно действие больше, т.к. мы должны сначала расчистить эту клетку. Т.е. вес ребра, соответствующего этому действию, будет не 1, а 2 (раньше мы такое ребро вообще не проводили бы).

Разбиваем целевые клетки на группы

Тут можно было бы применить какой-нибудь алгоритм кластеризации из пресловутого ML-я, о котором говорила половина чата, но я пошел по более простому пути — соеденил все пары целевых клеток, которые находились на расстоянии меньше 5, ребрами и полученные компоненты связянности и были искомыми группами, в качестве метрики расстояния я брал максимум из разностей координат между клетками (те, кто знаком с остовными деревьями, могли увидеть тут что-то знакомое, по факту тут применяется алгоритм Краскала, но берутся только первые сколько-то ребер). Далее можно еще посмотреть, что есть маленькие группы клеток, которые находятся рядом, но не достаточно близко, чтобы они объеденились в одну группу, но они достаточно маленькие, чтобы мы могли позволить себе объеденить их в одну группу. Поэтому если между какими-то клетками из различных маленьких групп расстояние меньше 7, мы их объединяем в одну группу. Это сделанно из соображений того, что почти наверняка эти две маленькие группы будут соседними в оптимальном ответе, внутри одной группы мы решаем задачу абсолютно оптимально, а алгоритм, который я опишу дальше, может поставить эти группы в неправильном порядке и ухудшить ответ. После всех описанных операций у меня получилась 21 группа с максимальным размером группы 15.

Определяем оптимальный порядок групп

Тут можно применить нехитрую эвристику: давайте мы «сожмем» каждую группу до одной вершины, добавим в полученный граф вершину, соответствующую стартовой, проведем между ними ориентированные взвешенные ребра и найдем в этом графе Гамильтонов путь наименьшей стоимости, который начинается в стартовой вершине. Его мы умеем искать за по времени, где n — количество вершин в графе, что нам подходит, т.к. групп целевых клеток, а значит и вершин в этом графе, будет 21 (и +1 стартовая). Осталось только понять, какие веса нужно писать на ребрах между вершинами, соответствующим группам. Давайте для каждой пары (<вершина первой группы>, <вершина второй группы>) посчитаем кратчайшее расстояние алгоритмом, который я описывал в самом начале, но сделаем одно изменение — ограничим максимальную скорость, с которой мы должны прийти в клетку второй группы (я ограничивал числом 5). Это сделано для более правильной оценки расстояний, т.к. нам примерно все равно, что мы можем дойти от первой группы до второй, например, за 5 ходов, но прийти туда со скоростью 10, т.к. нам нужно будет где-то там еще затормозить и начать обходить клетки группы. Далее, когда мы посчитали для каждой пары вершин кратчайшее расстояние, можно взять, например, минимум. Я брал 12.5 персентиль самых быстрых путей и оценивал этим значением длину ориентированного ребра между группами. Наверное, это все про эту часть, осталось только добавить, что в отличии от всего остального, часть с вычислением весов ребер очень хорошо параллелится. С решением, наверное, все, но кажется, что у многих читателей возникнет вопрос, на который я, пожалуй, тут и отвечу.

Что нужно курить, чтобы такое придумать?

На первый взгляд может показаться, что тут используется очень много сложных идей, и непонятно, как до всего этого можно додуматься. Секрет довольно прост, почти ничего из этого мне придумывать не нужно было, многое придумали более умные люди, чем я, задолго до меня, мне нужно было лишь правильно применить то, что они придумали. Но откуда брать всю эту информацию? Мне в этом соревновании очень сильно помог опыт занятий спортивным программированием, которым я очень много занимался в школе, алгоритмы, которые я тут описал, я узнал благодаря занятиям спортивным программированием, причем польза от него заключается не только в том, что я знаю все то, что тут применялось, но и понимаю, как это работает и какие области применимости имеет. Если у вас есть только сухие знания, не подкрепленные часами практики, то очень мал шанс того, что вы сможете в нужный момент их применить. Так что если вы еще учитесь в школе (или уже не учитесь) и не слышали про спортивное программирование — однозначно рекомендую, это не только улучшит ваши знания алгоритмов и прокачает силу рук, но так же, если вы школьник, возможно даст возможность поступить в ВУЗ без экзаменов (именно так я и поступал).

Заключение

Это, пожалуй, все, что я хотел бы рассказать, если будет сильный интерес, могу рассказать, как сделать так, чтобы описанное решение работало не только в теории, но и отрабатывало за вменяемое время на практике и так, чтобы вам не пришлось арендовывать облако с 1ТБ оперативки.

Спасибо за внимание)