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

Ключевые слова и синонимы

Наборы тестов и экспериментальная оценка программ для решения задач поиска кратчайших путей; DIMACS

Постановка задачи

Конкурсы DIMACS по реализации алгоритмов (http://dimacs.rutgers.edu/Challenges/) представляют собой научные мероприятия, целью которых является оценка практической эффективности алгоритмов в экспериментальных условиях, что способствует эффективному распространению технологий и согласованию общих эталонных тестов для фундаментальных вычислительных задач. Эти конкурсы организует DIMACS – Центр дискретной математики и теории вычислительных систем (Center for Discrete Mathematics and Theoretical Computer Science). Одной из основных целей конкурсов DIMACS по реализации алгоритмов является разрешение вопросов определения производительности реалистичных алгоритмов, для которых наихудший случай оказывается чрезмерно пессимистичным, а вероятностные модели – слишком нереалистичными: экспериментальные подходы могут привести к получению алгоритмов с реалистичными показателями эффективности в случаях, когда их невозможно получить при помощи анализа. Эксперименты также позволяют приблизить алгоритмические вопросы к исходным задачам, которые стали стимулом для теоретических изысканий. Кроме того, они дают возможность проверить различные предположения о методах реализации и структурах данных. Они предоставляют возможность для разработки и тестирования экземпляров задач, генераторов экземпляров и иных методов тестирования и сравнения эффективности алгоритмов. И, наконец, они помогают распространению технологий за счет предоставления самых передовых подходов к реализации алгоритмов для освоения и внедрения другими людьми и организациями.

Первый конкурс был проведен в 1990-1991 годах и был посвящен сетевым потокам и паросочетаниям. Далее рассматривались следующие задачи: поиск максимальной клики, раскраска графа и выполнимость (1992-1993), параллельные алгоритмы для решения комбинаторных задач (1993-1994), сборка фрагментов и перестройка генома (1994-1995), очереди с приоритетами, словари и многомерные множества точек (1995-1996), поиск ближайших соседей (1998-1999), полуопределенные и родственные задачи оптимизации (1999-2000) и задача коммивояжера (2000-2001).

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

9-й конкурс DIMACS по реализации алгоритмов: задача нахождения кратчайших путей

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

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

Участники конкурса изучали следующие варианты задачи нахождения кратчайших путей:

• Поточечное вычисление кратчайших путей [4, 5, 6, 9, 10, 11, 14]:

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

• Поиск кратчайших путей во внешней памяти [2]:

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

• Параллельный поиск кратчайших путей [8, 12]:

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

• K-точечная задача поиска кратчайших путей [13, 15]:

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

• Поиск кратчайших путей с ограничениями регулярных языков [3]:

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

Кульминацией конкурса стал семинар в центре DIMACS в Ратгерском университете в Пискатавэе, штат Нью-Джерси, проведенный 13-14 ноября 2006 года. Представленные на конференции доклады можно найти по адресу http://www.dis.uniroma1.it/~challenge9/papers.shtml. Избранные материалы вошли в книгу, опубликованную Американским математическим сообществом в серии DIMACS Book Series.

Основные результаты

В качестве основных результатов 9-го конкурса DIMACS по реализации алгоритмов можно упомянуть следующие:

• Определение общих форматов файлов для нескольких вариантов задачи о нахождении кратчайших путей – как статических, так и динамических. Они включают расширение известного графового формата DIMACS, используемого несколькими библиотеками алгоритмических приложений. С форматами можно ознакомиться по адресу http://www.dis.uniroma1.it/~challenge9/formats.shtml.

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

• Определение эталонных программ для задач вычисления кратчайших путей.

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

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

Основным источником информации о материалах и решениях 9-го конкурса DIMACS по реализации алгоритмов является сайт http://www.dis.uniroma1.it/~challenge9.

Применение

Задачи о нахождении кратчайших путей естественным образом возникают в огромном количестве ситуаций. В качестве примеров сценариев применения можно привести такие задачи, как дорожно-транспортная планировка, оптимизация сетей, маршрутизация пакетов, сегментация изображений, распознавание речи, форматирование документов, робототехника, компиляторы, системы управления информацией о дорожном движении и анализ потоков данных. Они также встречаются в виде подзадач нескольких других задач комбинаторной оптимизации – таких как организация сетевого потока. Исчерпывающее обсуждение областей применения алгоритмов нахождения кратчайших путей приведено в [1].

Открытые вопросы

До сих пор остаются нерешенными некоторые вопросы, связанные с задачами нахождения кратчайших путей – как теоретические, так и практические. Одним из самых перспективных направлений, обсуждавшихся во время семинара на 9-м конкурсе DIMACS, является моделирование изменений трафика при помощи алгоритмов поточечного вычисления кратчайших путей. Самые быстрые современные алгоритмы выполняют предварительную обработку исходного графа для эффективного ответа на запросы о поточечных расстояниях, и эта операция может занимать несколько часов в случае графов, построенных на базе систем навигации по крупномасштабным картам дорожной сети. Изменение дорожной обстановки может потребовать неоднократного повторного сканирования графа. На настоящий момент не известно эффективных техник обновления информации, полученной на этапе предварительной обработки, не требующих повторного построения ее с нуля. Это серьезно сказывается на эффективности приложений для маршрутизации.

Наборы данных

Набор эталонных входных данных 9-го конкурса DIMACS по реализации алгоритмов включал как синтетические данные, так и реальные данные. Все графы являлись сильно связными. В число синтетических графов входили случайные графы, решетки, графы, уложенные на тор, и графы со свойствами «тесного мира». Реальные данные включали графы, представляющие дорожные сети Европы и США. Графы Европы были предоставлены компанией PTV из Карлсруэ (Германия) на основе бесплатного лицензионного соглашения. Они включали дорожные сети 17 европейских стран, среди которых были Австрия (AUT), Бельгия (BEL), Швейцария (CHE), Чехия (CZE), Германия (DEU), Дания (DNK), Испания (ESP), Финляндия (FIN), Франция (FRA), Великобритания (GBR), Ирландия (IRL), Италия (ITA), Люксембург (LUX), Нидерланды (NDL), Норвегия (NOR), Португалия (PRT) и Швеция (SWE), суммарно составляющие около 19 миллионов вершин и 23 миллионов ребер. Графы для США были созданы на основе файлов UA Census 2000 TIGER/Line, предоставленных географическим подразделением Бюро переписи населения США (US Census Bureau) в Вашингтоне, округ Колумбия. Набор TIGER/Line доступен по адресу http://www.census.gov/geo/www/tiger/tigerua/ua_tgr2k.html. Базовое семейство USA содержит граф, представляющий всю дорожную сеть США с 24 миллионами вершин и 58 миллионами ребер, а также 11 подграфов, полученных в результате разрезания ее при помощи различных ограничивающих прямоугольников, как показано в таблице 1. Графы в этом наборе также содержат координаты вершин и представлены в формате DIMACS.

Название	Описание	Число вершин	Число ребер	Широта огранич. прям. (С)	Долгота огранич. прям. (В)
USA	США (вся страна)	23 947 347	58 333 344	-	-
CTR	Центр США	14 081 816	34 292 496	[25,0; 50,0]	[79,0; 100,0]
W	Запад США	6 262 104	15 248 146	[27.0; 50.0]	[100.0; 130.0]
E	Восток США	3 598 623	8 778 114	[24,0; 50,0]	[[math]\displaystyle{ - \infty }[/math]; 79,0]
LKS	Великие озера	2 758 119	6 885 658	[41,0; 50,0]	[74,0; 93,0]
CAL	Калифорния и Невада	1 890 815	4 657 742	[32,5; 42,0]	[114.0; 125.0]
NE	Северо-восток США	1 524 453	3 897 636	[39,5; 43,0]	[[math]\displaystyle{ - \infty }[/math]; 76,0]
NW	Северо-запад США	1 207 945	2 840 208	[42,0; 50,0]	[116,0; 126,0]
FLA	Флорида	1 070 376	2 712 798	[24,0; 31,0]	[79; 87,5]
COL	Колорадо	435 666	1 057 066	[37,0; 41,0]	[102,0; 109,0]
BAY	Область Залива	321 270	800 172	[37,0; 39,0]	[121; 123]
NY	Нью-Йорк	264 346	733 846	[40,3; 41,3]	[73,5; 74,5]

Таблица 1. Дорожные сети США, созданные на основе набора TIGER/Line

	Предварительная обработка		Ответы на запросы
Алгоритм	Время (в минутах)	Память (в МБ)	Скан. вершины	Время (в мс)	Эталонное отношение
HH-based transit [14]	104	3664	неизв.	0,019	[math]\displaystyle{ 4,78 \cdot 10^{-6} }[/math]
TRANSIT [4]	720	неизв.	неизв.	0,052	[math]\displaystyle{ 10,77 \cdot 10^{-6} }[/math]
HH Star [6]	32	2662	1082	1,14	[math]\displaystyle{ 287,32 \cdot 10^{-6} }[/math]
REAL(16,1) [9]	107	2435	823	1,42	[math]\displaystyle{ 296,30 \cdot 10^{-6} }[/math]
HH с DistTab [6]	29	2101	1671	1,61	[math]\displaystyle{ 405,77 \cdot 10^{-6} }[/math]
RE[9]	88	861	3065	2,78	[math]\displaystyle{ 580,08 \cdot 10^{-6} }[/math]

Таблица 2. Результаты конкурса на графе США (23,9 миллионов вершин и 58,3 миллионов ребер) с ребрами единичной длины. Эталонным отношением считалось среднее время выполнения запроса, деленное на время выполнения вопроса при помощи эталонного кода Дейкстры на той же платформе. Время выполнения запроса и количество просканированных вершин представляют собой средние значения в пересчете на запрос на выборке из более чем 1000 случайных запросов

Эталонный пакет входных данных также содержит генераторы запросов для задач нахождения кратчайших путей с единственным источником либо поточечного вычисления кратчайших путей. В версии задачи с единственным источником источники выбираются случайным образом. В поточечной задаче рассматриваются как случайные, так и локальные запросы. Локальные запросы вида (s, t) генерируются посредством случайного выбора t среди вершин с рангом из интервала [math]\displaystyle{ [2^i, 2^{i + 1}) \; }[/math] согласно порядку сканирования вершин при помощи алгоритма Дейкстры с источником s для любого параметра i. Очевидно, что чем меньше величина i, тем ближе друг к другу в графе располагаются вершины s и t. Локальные запросы важны для проверки влияния расстояния между конечными точками запроса на эффективность работы алгоритмов.

Базовые семейства входных данных 9-го конкурса DIMACS по реализации алгоритмов доступны по адресу http://www.dis.uniroma1.it/~challenge9/download.shtml.

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

Одной из главных задач конкурса было сравнение различных техник и алгоритмических подходов. Самой популярной темой оказалось поточечное вычисление кратчайших путей, которое в контексте конкурса изучали шесть исследовательских групп. Для этой задачи было дополнительно проведено состязание между участниками с целью оценки эффективности и надежности различных реализаций алгоритмов. Состязание включало в себя предварительную обработку версии полного графа USA из таблицы 1 с ребрами единичной длины и ответ на последовательность из 1000 случайных запросов о расстоянии. Детали состязания были анонсированы в первый день конкурса, а результаты получены во второй день. Для сравнения экспериментальных результатов на различных платформах каждый участник выполнял эталонный код Дейкстры [7] на графе USA с целью калибровки. Показателем для окончательной расстановки стало среднее время выполнения запроса, деленное на время выполнения запроса при помощи эталонного кода на той же платформе ("эталонное отношение"). Учитывались также такие показатели эффективности, как объем использованной памяти и среднее количество вершин, просканированных операциями поиска.

Шесть поточечных алгоритмов были успешно выполнены на графе USA, определенном специально для конкурса. Самым быстрым среди них оказался алгоритм HH-based transit [14]. Результаты приведены в таблице 2. Алгоритмы RE и REAL(16, 1) [9] не были допущены к состязанию, однако использовались организаторами для доказательства разрешимости задачи. Некоторые другие алгоритмы не сумели справиться с размером полного графа USA либо вызвали ошибки в ходе выполнения.

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

Ссылка на код

Генераторы семейств задач и эталонные решатели для задач нахождения кратчайших путей можно найти по адресу http://www.dis.uniroma1.it/~challenge9/download.shtml.

См. также

Литература

1. Ahuja, R., Magnanti, T., Orlin, J.: Network Flows: Theory, Algorithms and Applications. Prentice Hall, Englewood Cliffs, NJ (1993)

2. Ajwani, D., Dementiev, U., Meyer, R., Osipov, V.: Breadth first search on massive graphs. In: 9th DIMACS Implementation Challenge Workshop: Shortest Paths, DIMACS Center, Piscataway, NJ, 13-14 Nov 2006

3. Barrett, C., Bissett, K., Holzer, M., Konjevod, G., Marathe, M., Wagner, D.: Implementations of routing algorithms for transportation networks. In: 9th DIMACS Implementation Challenge Workshop: Shortest Paths. DIMACS Center, Piscataway, NJ, 13-14 Nov2006

4. Bast, H., Funke, S., Matijevic, D.: Transit: Ultrafast shortest-path queries with linear-time preprocessing. In: 9th DIMACS Implementation Challenge Workshop: Shortest Paths, DIMACS Center, Piscataway, NJ, 13-14 Nov 2006

5. Delling, D., Holzer, M., Muller, K., Schulz, F., Wagner, D.: High-performance multi-level graphs. In: 9th DIMACS Implementation Challenge Workshop: Shortest Paths, DIMACS Center, Piscataway, NJ, 13-14 Nov 2006

6. Delling, D., Sanders, P., Schultes, D., Wagner, D.: Highway hierarchies star. In: 9th DIMACS Implementation Challenge Workshop: Shortest Paths, DIMACS Center, Piscataway, NJ, 13-14 Nov 2006

7. Dijkstra, E.: A note on two problems in connexion with graphs. Numerische Mathematik 1, 269-271 (1959)

8. Edmonds, N., Breuer, A., Gregor, D., Lumsdaine, A.: Single-source shortest paths with the parallel boost graph library. In: 9th DIMACS Implementation Challenge Workshop: Shortest Paths, DIMACS Center, Piscataway, NJ, 13-14 Nov 2006

9. Goldberg, A., Kaplan, H., Werneck, R.: Better landmarks within reach. In: 9th DIMACS Implementation Challenge Workshop: Shortest Paths. DIMACS Center, Piscataway, NJ, 13-14 Nov 2006

10. Kohler, E., Mohring, R., Schilling, H.: Fast point-to-point shortest path computations with arc-flags. In: 9th DIMACS Implementation Challenge Workshop: Shortest Paths, DIMACS Center, Piscataway, NJ, 13-14 Nov 2006

11. Lauther, U.: An experimental evaluation of point-to-point shortest path calculation on roadnetworks with precalculated edge-flags. In: 9th DIMACS Implementation Challenge Workshop: Shortest Paths, DIMACS Center, Piscataway, NJ, 13-14 Nov 2006

12. Madduri, K., Bader, D., Berry, J., Crobak, J.: Parallel shortest path algorithms for solving large-scale instances. In: 9th DIMACS Implementation Challenge Workshop: Shortest Paths, DIMACS Center, Piscataway, NJ, 13-14 Nov 2006

13. Pascoal, M.: Implementations and empirical comparison of k shortest loopless path algorithms. In: 9th DIMACS Implementation Challenge Workshop: Shortest Paths, DIMACS Center, Piscataway, NJ, 13-14 Nov 2006

14. Sanders, P., Schultes, D.: Robust, almost constant time shortest-path queries in road networks. In: 9th DIMACS Implementation Challenge Workshop: Shortest Paths, DIMACS Center, Piscataway, NJ, 13-14 Nov 2006

15. Santos, J.: K shortest path algorithms. In: 9th DIMACS Implementation Challenge Workshop: Shortest Paths, DIMACS Center, Piscataway, NJ, 13-14 Nov 2006