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

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


Предыстория


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


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


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


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


Всем известно, а кому неизвестно почитайте, что алгоритм Дейкстры за счет использования очереди с логарифмической сложностью вставки и удаления можно привести к сложности вида O(nlog(n) + mlog(n)). При использовании фибоначчиевой кучи сложность можно опустить до O(n*log(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-го узла за константное время.


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


image


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


  • узел 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к узлов.

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


image


Рассмотрим зависимость вероятности повторного просмотра вершины и размера графа:


кол-во просмотров узлов кол-во вершин графа вероятность повторного просмотра узла
104915 100015 4.8
169429 167892 0.9
431490 419594 2.8

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


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


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


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

Поделиться публикацией
Комментарии 13
    +1
    Как проверялась корректность реализации? Например, верно ли, что ответы двух реализаций (стандартной и с корзинами) совпали на всех вершинах графа при поиске расстояний от фиксированной вершины `V`?

    Не пробовали ли вы в каждой ячейке воспользоваться обычной кучей (например, для Java это `PriorityQueue`) вместо массива?

    Есть ли какой-то смысл в написании своей реализации `BitArray` и частичной реализации `ArrayList` внутри `NewSortedHashMapEntry`?

    А каковы длины дуг? Например, если длина дуги всегда больше, чем размер корзины, то можно отсортировать каждую корзину перед её первым посещением и появится гарантия, что каждая вершина посещается не больше одного раза. Ну или можно просто отсортировать и посмотреть, что будет. Или сделать `Collections.shuffle` перед первым проходом.
      0
      Корректность проверялась путем проверки полного совпадения массива d расстояний.
      Нет, но прелесть массива примитивов в скорости его работы. Тут скорее имеет смысл сравнить с бинарной кучей, к примеру.
      Да, интересно было попробовать реализовать битовую маску применяя сравнение без ifов. Вполне вероятно, что можно применить и готовые библиотеки.
      По поводу длины дуг, большое спасибо, очень интересное дополнение, попробую обязательно реализовать и дополню статью.
        0

        Да, неточно выразился, бинарная куча (binary heap) и подразумевалась. Это получится этакая оптимизация стандартного алгоритма с двоичной кучей, просто в которой куча разделена на несколько корзин. Мне кажется, чем-то напоминает radix sort.


        Не очень понял, что вы подразумеваете под "сравнением без if'ов". Можете пояснить? Я не понимаю, чем ваша реализация принципиально лучше массива boolean, кроме того, что может занимать меньше места. А вообще в Java есть встроенный битовый массив — BitSet.

          0
          Да, из radix sort идею я и подчерпнул.
          Про BitSet — принципиально мне кажется ничем, просто интересно было. А программирование без if-ов это когда, к примеру, необходимо сравнить a < b и если да то сделать c += 10. В этом случае можно сделать следующую магию:
          public static int getSign(int a, int b) {
              int c = a - b;
              return (c >> 31) & 0x1;
          }
          c += 10 * getSign(a, b);
          

          Такая штука:
          1) это прямые указания процессору и работу с очень быстрыми битовыми сдвигами
          2) и вы можете не надеется на то, что проц сам соптимизирует.
          3) работает, к сожалению, только с обратным порядком байт и в jvm, где размер int не зависит от 32-битная или 64 битная адресация памяти.
          0
          Корректность проверялась путем проверки полного совпадения массива d расстояний.

          В статье написано, что проверялись только расстояния до случайной тысячи узлов и её хорошо бы исправить или я чего-то не понимаю?


          показавшие полное совпадение длины кратчайшего пути от 1000 рандомных узлов до 1000 других рандомных узлов на графе.
            0
            Проверил на всякий случай. Весь массив d расстояний совпадает, как при расчете с использованием красно-черного дерева, так и в случае сортирующей хэш-таблицы.
        0
        Можете еще посмотреть на Radix heap. Там тоже корзины и все такое, а в реализации ИМХО попроще чем куча Фибоначчи.
          0
          Попробую, в течении месяца найду время и дополню статью, вроде готовая реализация на Java есть.
          +1
          Я немного затупил на том месте где хеш таблица описана. Там ключ это расстояние или диапазон расстояний (например 0..20, 20..40 и т.д.), а значение это номер узла в графе?

          Весьма годная идея. На вашем месте я бы такие статьи публиковал ещё и на github.io, чтобы была visibility за пределами русскоязычной аудитории. Очень полезно для резюме и повышения зарплаты :)

          Мелкий баг: надо поменять difficulty на complexity.
            0
            В хэш-таблице хранится диапазон значений расстояний, а номера в узле, все верно.
            За замечание по баге спасибо)
            0
            Насколько я понимаю, этот алгоритм имеет ограничения по сравнению с классическим алгоритмом Дейкстры. То что бросается в глаза это необходимость иметь равномерное распределение вершин по бакетам. Прокомментируйте, пожалуйста, т.к. не уверен что уловил все детали вашего подхода.

            Полагаю, вы сравнили по времени свое решение и классическое. Хорошая асимптотика может не означать ускорение на практике (пример: умножение матриц методом Штрассена), поэтому хочется увидеть эти сравнения тоже.

            PS: Поправьте, пожалуйста, опечатки («алгоримт», «lon(n)», «20 секунд» на картинке ...)
              0
              Ограничений нет, алгоритм так же корректно будет работать в случае любого графа, вопрос лишь в производительности.

              Равномерное распределение иметь вовсе не обязательно. Важно лишь уменьшить вероятность повторного просмотра вершины. Сама по себе вероятность повторного просмотра зависит от двух факторов:
              1. Мощность бакета должна быть чуть меньше чем, к примеру, 10% персентиль распределения длины дуг. Тогда вы получите гарантированно малую вероятность повторного просмотра.
              2. Распределение расстояний из точки: оно может быть равномерным по бакетам и так получиться, что даже при фиговом подборе параметра мощности бакета вы получите неплохую производительность, надо смотреть конкретные случаи, но в случае дорожного графа, замечу, проблем не возникло ни в одном из трех городов на которых алгоритм сейчас работает (Москва, Питер, Казань).

              По поводу производительности: я дополнительно произвел исследования на рандомно сгенерированном графе при различных параметрах и сравнил с бинарной кучей и фибоначчиевой кучей и в них алгоритм стабильно работал быстрее в несколько раз. Эти исследования я постараюсь дооформить в ближайшее время и дополнить ими публикацию.
              Графики, что вы видели в публикации это поиск на графе дорог Москвы (OSM) из рандомной точки в тысячи рандомных точек, это и есть сравнение на практике.

              Опечатки: 20 секунд это не опечатка, в моем случае путь действительно измерялся в секундах поэтому и длина дуги из метров конвертировалась в секунды.
              0
              комментарий удалён

              Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

              Самое читаемое