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

Задача поиска кратчайшего пути — классическая оптимизационная задача. Данная область стремительно развивается благодаря распространению систем спутниковой навигации (GPS). В частности, стали популярны алгоритмы с препроцессингом. Такие алгоритмы предобрабатывают граф и сохраняют некоторую информацию, так чтобы потом отвечать на запросы нахождения кратчайшего пути очень быстро даже на мобильном устройстве.

Алгоритм пометок (labeling algorithm) предпосчитывает пометку для каждой вершины графа. Эта информация позволяет ответить на запрос нахождения кратчайшего пути между s и t, используя метки вершин s и t и не просматривая весь граф. Для некоторых классов графов метки удаётся сделать короткими, что, в свою очередь, позволяет отвечать на запросы очень быстро. Алгоритм пометок хабов (hub labeling algorithm) — частный случай алгоритма меток, который является эффективным, в частности, на дорожных картах.

Мы опишем алгоритм пометок хабов и эффективные реализации запросов для такого алгоритма. Увидим, что запросы для дорожных карт могут обрабатываться быстрее, чем за микросекунду. Изучим предпосчёт меток хабов. Мы начнём с эвристического алгоритма, после чего перейдём к приближённому алгоритму Коэна и других, рассмотрим его реализации и улучшения.

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

Проекты

Открытая реализация алгоритма меток хабов Руслана Савченко: https://github.com/savrus/hl Она может быть использована как отправная точка для экспериментов в данной области. Можно также реализовывать более сложные известные алгоритмы или пробовать свои подходы.

Аннотация на английском:

This is a mini-course on resent results in the area. First lectures will require minimal prerequisites: basicknowledge of graph algorithms, including Dijkstra’s shortest paths algorithm and elementary data structures. For subsequent lectures, more prior exposure to algorithms, including approximation algorithms, will be helpful but not required.

DESCRIPTION

The point-to-point shortest path problem is a classical optimization problem. Motivated by the proliferation of GPS-based navigation systems, a lot of progress has been recently made in the area. Algorithms with preprocessing received a special attention. These algorithm precompute auxiliary data that allows answering queries in real time on a server, or in a fraction of a second on a mobile device.

Labeling algorithm precompute a label for every vertex in a graph. An s-t query is answered based on the labels of s and t, without looking at the input graph. For some classes of graphs, labels are small and queries are efficient. Hub labeling algorithms are a special kind of labeling algorithms that work well on some problem classes, in particular road networks. After introducing hub labeling algorithms, we will discuss efficient query implementation and see why distance queries on road networks can be answered in less than a microsecond. Then we will study hub labeling preprocessing. We will start with a heuristic algorithm that works well on road networks. Next we will study the Cohen at. al. approximation algorithm for the preprocessing problem, its improvements and efficient implementations.

Cohen et. al. algorithm produces good labels on a wider set of problem classes, but cannot solve large problems in reasonable time. We will discuss the use of sampling to make the algorithm more efficient in practice. In conclusion, we will survey other results, including theoretical results on computational complexity of problems related to hub labelling

POSSIBLE PROJECTS

A public-domain implementation of basic Hub Labeling algorithms https://github.com/savrus/hl, developed by Ruslan Savchenko, can be used as a starting point for experimental projects in the area. One can implement more sophisticated algorithms from the literature, or try their own ideas on the topic.