Дейкстра за линейное время

Приветствую всех и особенно тех кто интересуется задачами дискретной математики и теорией графов.

Предыстория

Так уж вышло, что ведомый интересом я занимался разработкой сервиса построения тур. маршрутов. Задача состояла в том, чтобы на основании интересующего пользователя города, категорий заведений и временных рамок спланировать оптимальные маршруты. Ну и одной из подзадач было рассчитывать время в пути от одного заведения до другого. Так как я был юн и глуп я решал эту задачу в лоб, алгоритмом Дейкстры, но справедливости ради стоит заметить, что только с ним можно было запустить итерацию из одного узла до тысяч других, кэшировать эти расстояния было не вариантом, заведений больше 10к только в одной Москве, а решения типа манхэттенского расстояния на наших городах не работает от слова совсем.

И так вышло, что проблему производительности в задаче комбинаторики решить удалось, а вот большую часть времени на обработку запроса отъедало поиск незакэшированных путей. Проблема усложнялась тем, что граф дорог Osm в Москве довольно большой (полмиллиона узлов и 1.1 млн дуг).

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

Дейкстра за логарифмическое время

Всем известно, а кому неизвестно почитайте ^[1], что алгоритм Дейкстры за счет использования очереди с логарифмической сложностью вставки и удаления можно привести к сложности вида O(nlog(n) + mlon(n)). При использовании фиббоначиевой кучи сложность можно опустить до O(n*lon(n) + m), но все равно не линейно, а хотелось бы.

В общем случае алгоритм с очередью описывается следующим образом:

Пусть:

• V — множество вершин графа
• E — множество ребер графа
• w[i, j] — вес ребра из узла i в узел j
• a — начальная вершина поиска
• q -очередь вершин
• d[i] — расстояние до i-го узла
• d[a] = 0, для всех остальных d[i] = +inf

Пока q не пустой:

• v — вершина с минимальным d[v] из q
• Для всех вершин u для которых есть переход в E из вершины v
  • if d[u] > w[vu] + d[v]
    • удалить u из q с расстоянием d[u]
    • d[u] = w[vu] + d[v]
    • добавить u в q с расстоянием d[u]
• удалить v из q

Если в качестве очереди использовать красно-черное дерево, где вставка и удаление происходят за log(n), а поиск минимального элемента аналогично за log(n), то сложность алгоритма составит O(nlog(n) + mlog(n)).

И тут стоит заметить одну важную особенность: ничего не мешает, в теории, рассмотреть вершину несколько раз. Если вершина была рассмотрена и расстояние до нее было обновлено на некорректное, большее, чем истинное значение, то при условии, что рано или поздно система сойдется и расстояние до u будет обновлено на корректное значение позволительно делать такие трюки. Но стоит заметить — одна вершина должна рассматриваться больше чем 1 раз с некоторой малой вероятностью.

Сортирующая хэш-таблица

Для сведения времени работы алгоритма Дейкстры к линейному предлагается структура данных, представляющая из себя хэш-таблицу с номерами узлов(node_id) в качестве значений. Замечу, потребность в массиве d никуда не девается, он все так же нужен, что получать расстояние до i-го узла за константное время.

На рисунке ниже приведен пример работы предлагаемой структуры.

Опишем по шагам предложенную структуру данных:

• узел u записывается в ячейку под номером равным d[u] // bucket_size, где bucket_size мощность ячейки (к примеру 20 метров, т.е. ячейка под номером 0 будет содержать узлы расстояние до которых будет лежать в диапазоне [0, 20) метров)
• минимальным узлом будет считаться последний узел первой непустой ячейки, т.е. операция извлечения минимального элемента будет выполняться за O(1). Необходимо поддерживать актуальное состояние идентификатора номера первой непустой ячейки (min_el).
• операция вставки выполняется посредством добавления в конец ячейки нового номера узла и в тоже выполняется за O(1), т.к. вычисление номера ячейки происходит за константное время.
• операция удаления, как в случае с хэш-таблицей, возможен обычный перебор, и можно было бы сделать допущение и сказать, что при малом размере ячейки это тоже O(1). Если вам не жалко памяти (в принципе и не так много нужно, еще один массив на n), то можно завести массив позиций в ячейке. При этом, если удаляется элемент в середине ячейки, необходимо переместить последнее значение в ячейке на удаляемое место.
• важный момент при выборе минимального элемента: он является минимальным лишь с некоторой вероятностью, но, алгоримт будет просматривать ячейку min_el пока она не станет пустой и рано или поздно реальный минимальный элемент будет рассмотрен, и если мы случайно обновили некорректно значение расстояния до узла, достижимого из минимального, то смежные с минимальным узлы снова смогут окажутся в очереди и значение расстояния до них будет корректным и т.д.
• можно также удалять пустые ячейки до min_el, тем самым экономя память. В этом случае, удаление узла v из очереди q необходимо производить только после рассмотрения всех смежных узлов.
• а еще можно менять мощность ячейки, параметры увеличения размера ячейки и количества ячеек, когда нужно увеличить размер хэш-таблицы.

Результаты замеров

Проверки делались на карте osm Москвы, выгруженной через osm2po в postgres, а затем загруженной в память. Тесты писались на Java. Имелось 3 версии графа:

• исходный граф — 0.43 млн узлов, 1.14 млн дуг
• сжатая версия графа с 173k узлами и 750k дугами
• пешеходная версия сжатой версии графа, 450к дуг, 100к узлов.

Ниже приведен рисунок с замерами на разных версиях графа:

Если рассматривать вероятностную сторону вопроса повторного просмотра вершины, то на графе в 100к узлов были получены результаты примерно в 110к просмотров узлов, т.е. каждый узел был пересмотрен с вероятностью в 10%. Необходимо заметить, что вероятность также конфигурируется посредством изменения мощности ячейки.

Были проведены также качественные замеры для практического подтверждения сравнения корректности результата работы алгоритмы с новой структурой данных, показавшие полное совпадение длины кратчайшего пути от 1000 рандомных узлов до 1000 других рандомных узлов на графе. (и так 250 итераций) при работе с сортирующей хэш-таблицей и красно-черным деревом.

Исходный код предложенной структуры данных лежит по ссылке ^[2]

P.S.: Про алгоритм Торупа и то, что он решает эту же задачу тоже за линейное время знаю, но я не смог осилить этот фундаментальный труд за один вечер, хотя и понял в общих чертах идею. По крайней мере, как я понял, там предлагается другой подход, основанный на построении минимального остовного дерева.

Автор: Junkers

Источник ^[3]