Краткий обзор современных алгоритмов поиска кратчайшего пути и методов оптимизации графов

Таблица ссылок

Резюме и 1. Введение

1.1 Наш вклад

1.2 Настройка

1.3 Алгоритм

1. Связанные работы

2. Алгоритм

   3.1 Фаза структурной декомпозиции

   3.2 Фаза маршрутизации

   3.3 Варианты WormHole

3. Теоретический анализ

   4.1 Предварительные сведения

   4.2 Сублинейность внутреннего кольца

   4.3 Ошибка аппроксимации

   4.4 Сложность запроса

4. Экспериментальные результаты

   5.1 WormHole𝐸, WormHole𝐻 и BiBFS

   5.2 Сравнение с методами на основе индексов

   5.3 WormHole как примитив: WormHole𝑀

Ссылки

2 СВЯЗАННЫЕ РАБОТЫ

Существует обширный объем исследований по кратчайшим путям и расстояниям, охватывающий многие десятилетия и включающий сотни алгоритмов и эвристик, разработанных для различных условий. Здесь мы рассмотрим только несколько работ, наиболее тесно связанных с нашей. Для более полного обзора см. обзоры [42, 55] и ссылки в них.

\ Подходы на основе индексов. Как упоминалось ранее, повсеместно используемый набор алгоритмов основан на подходах с использованием ориентиров/эскизов [37, 61, 62], причем Pruned Landmark Labeling (PLL) [5], возможно, является наиболее влиятельным из них. Эти алгоритмы следуют двухэтапной процедуре: первый шаг генерирует упорядочивание вершин в соответствии с важностью (на основе различных эвристик), а второй шаг генерирует маркировку из обрезанных деревьев кратчайших путей, построенных в соответствии с упорядочиванием. Затем кратчайшее расстояние между произвольной парой вершин 𝑠 и t может быть быстро определено на основе их меток. Однако даже с обрезкой PLL требует значительного времени настройки. Следовательно, было предпринято много попыток распараллелить его [29, 37, 39].

\ Подходы на основе вложений. Некоторые недавние подходы используют вложения графов для оценки кратчайших путей. Как и в обучении представлениям, они стремятся найти эффективные представления расстояний между парами узлов [64, 65]. Современное направление работы также рассматривает гиперболические вложения графов, которые тесно связаны с древовидными декомпозициями, для ответа на запросы о кратчайших путях [11, 33]. Недавние работы также рассматривали ускорение этого процесса с использованием методов глубокого обучения на основе GPU [35, 47, 48]. Query-by-Sketch [57] рассматривает связанную, но несравнимую задачу ответа на запросы о графах кратчайших путей, где целью является вычисление подграфа, содержащего точно все кратчайшие пути между заданной парой вершин. Они предлагают альтернативную схему маркировки для улучшения масштабируемости и времени запросов.

\

\ Подходы на основе ядра-периферии. Несколько других работ используют структуру ядра-периферии сетей [6, 13, 38]. Брэди и Коэн [13] используют компактные схемы маршрутизации для разработки алгоритма с малой аддитивной ошибкой, основанного на сходстве периферии с лесом. Акиба, Соммер и Каварабаяши [6] используют свойство низкой древовидной ширины вне ядра, а в [38] авторы разрабатывают индекс на основе Core-Tree для улучшения времени предварительной обработки на массивных графах. Отметим, что во всех этих результатах накладные расходы памяти являются сверхлинейными.

\ Графы наихудшего случая. С теоретической стороны, было получено много результатов по точным и приближенным кратчайшим путям в графах наихудшего случая, например, [19, 20, 22, 49, 51, 67], с улучшениями, появившимися совсем недавно, в прошлом году. Большинство из них сосредоточено на случае 2-аппроксимации, впервые исследованном в основополагающей работе Эйнгворта и др. [4]. Мы отсылаем читателей к обзору Цвика [66] по алгоритмам точных и приближенных кратчайших путей и обзору Сена [53] по оракулам расстояний для общих графов с акцентом на снижение стоимости предварительной обработки. Примечательно, что поскольку мы делаем структурное предположение, выходящее за рамки наихудшего случая, которое является общим для больших сетей, а именно, структуру ядра-периферии, как наши результаты, так и алгоритм существенно отличаются от теоретической литературы о наихудших случаях.

\

:::info Авторы:

(1) Talya Eden, Bar-Ilan University ([e-mail]);

(2) Omri Ben-Eliezer, MIT ([e-mail]);

(3) C. Seshadhri, UC Santa Cruz ([e-mail]).

:::

---

:::info Эта статья доступна на arxiv под лицензией CC BY 4.0.

:::

\