[Из песочницы] Дейкстра за линейное время04.07.2018 22:32

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

Предыстория

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

И так вышло, что проблему производительности в задаче комбинаторики решить удалось, а вот большую часть времени на обработку запроса отъедало поиск незакэшированных путей. Проблема усложнялась тем, что граф дорог Osm в Москве довольно большой (полмиллиона узлов и 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 итераций) при работе с сортирующей хэш-таблицей и красно-черным деревом.

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

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