Дейкстра В Линейное Время

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

Фон

маршруты.

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

Ну и одной из подзадач было посчитать время в пути от одного заведения до другого.

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

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

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

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

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

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

При использовании кучи Фибоначчи сложность можно снизить до O(n*log(n) + m), но она всё равно не линейна, а мне бы хотелось, чтобы так было.

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

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

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

И здесь стоит отметить одну важную особенность: ничто не мешает теоретически рассмотреть пик несколько раз.

Если вершина была исследована и расстояние до нее обновлено до неверного значения, большего истинного значения, то при условии, что рано или поздно система сходится и расстояние до u обновится до правильного значения, допустимо делать такие трюки.

Но стоит отметить, что одна вершина должна рассматриваться более 1 раза с некоторой малой вероятностью.

Сортировка хеш-таблицы

Замечу, что необходимость в массиве 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 необходимо производить только после рассмотрения всех соседних узлов.

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

Результаты измерений

Тесты были написаны на Java. Было 3 варианта графика:

• исходный граф — 0,43 миллиона узлов, 1,14 миллиона дуг
• сжатая версия графа со 173 тыс.

  узлов и 750 тыс.

  дуг

• пешеходная версия сжатой версии графа, 450 тыс.

  дуг, 100 тыс.

  узлов.

Буду очень признателен за помощь в построении вероятностной модификации алгоритма с параметрами, гарантирующими доверительный интервал, в пределах которого вероятность повторного просмотра не превысит определенного процента.

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

.

(и так 250 итераций) при работе с сортирующей хеш-таблицей и красно-черным деревом.

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

По крайней мере, насколько я понимаю, они предлагают другой подход, основанный на построении минимального связующего дерева.

P.S.S. В течение недели постараюсь найти время и провести сравнение с кучей Фибоначчи и чуть позже добавлю примеры и тестовые коды в репозиторий на github. Теги: #Дийкстра #кратчайший путь #Алгоритмы

• Загрузка Фотографий Для Обмена И Сохранения

  19 Oct, 24

• Anybalance+ — Агрегатор, С Помощью Которого Вы Можете Контролировать Свои Финансы

  19 Oct, 24

• Юрист По Стартапам — Руководство По Юридическим Аспектам Запуска Стартапа

  19 Oct, 24

• Хабраравод?

  19 Oct, 24

• Социальный Повседневный

  19 Oct, 24

• Магия Макросов Для Объединения Объявления И Реализации

  19 Oct, 24

• Понимание Финансовых Аспектов Бизнес-Модели Saas

  19 Oct, 24

• Пробки На Google Maps В России

  19 Oct, 24

• Монгобд 2.0

  19 Oct, 24

• Марка Артемия Лебедева

  19 Oct, 24