Конкурс по реализации алгоритмов поиска кратчайших путей
Ключевые слова и синонимы
Наборы тестов и экспериментальная оценка программ для решения задач поиска кратчайших путей; 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.
| Название | Описание | Число вершин | Число ребер | Широта огранич. прям. (С) | Долгота огранич. прям. (В) |
|---|---|---|---|---|---|
| USA | США (вся страна) | 23 947 347 | 58 333 344 | - | - |
| CTR | Центр США | 14081816 | 34 292496 | [25,0; 50,0] | [79,0; 100,0] |
| W | Запад США | 6 262104 | 15 248146 | [27.0; 50.0] | [100.0; 130.0] |
| E | Восток США | 3 598623 | 8778114 | [24,0; 50,0] | [-1; 79,0] |
| LKS | Великие озера | 2758119 | 6885 658 | [41,0; 50,0] | [74,0; 93,0] |
| CAL | Калифорния и Невада | 1890815 | 4657 742 | [32,5; 42,0] | [114.0; 125.0] |
| NE | Северо-восток США | 1 524453 | 3 897 636 | [39,5; 43,0] | [-1; 76,0] |
| NW | Северо-запад США | 1 207 945 | 2 840 208 | [42,0; 50,0] | [116,0; 126,0] |
| FLA | Флорида | 1070 376 | 2 712 798 | [24,0; 31,0] | [79; 87,5] |
| COL | Колорадо | 435 666. | 1057 066 | [37,0; 41,0] | [102,0; 109,0] |
| BAY | Область Залива | 321 270 | 800172 | [37,0; 39,0] | [121; 123] |
| NY | Нью-Йорк | 264 346 | 733 846 | [40,3; 41,3] | [73,5; 74,5] |
Таблица 1. Дорожные сети США, созданные на основе набора TIGER/Line
PREPROCE
| Алгоритм | Время (в минутах) | Память (в МБ) | Скан. вершины | Время (в мс) | Эталонное отношение |
|---|---|---|---|---|---|
| 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 ребер) с ребрами единичной длины. Эталонным показателем считалось среднее время выполнения запроса, деленное на время выполнения вопроса при помощи эталонного кода Дейкстры (Challenge Dijkstra) на той же платформе. Время выполнения запроса и количество просканированных вершин представляют собой средние значения в пересчете на запрос на выборке из более чем 1000 случайных запросов
Файлы предоставлены географическим подразделением Бюро переписи населения США (US Census Bureau) в Вашингтоне, округ Колумбия. Набор TIGER/Line доступен по адресу http://www.census.gov/geo/www/tiger/ tigerua/ua_tgr2k.html. Базовое семейство USA содержит граф, представляющий всю дорожную сеть США с 24 миллионами вершин и 58 миллионами ребер, а также 11 подграфов, полученных в результате разрезания ее при помощи различных ограничивающих прямоугольников, как показано в таблице 1. Графы в этом наборе также содержат координаты вершин и представлены в формате DIMACS.
Эталонный пакет входных данных также содержит генераторы запросов для задач нахождения кратчайших путей с единственным источником либо двухточечных. В версии задачи с единственным источником источники выбираются случайным образом. В двухточечной задаче рассматриваются как случайные, так и локальные запросы. Локальные запросы вида (s, t) генерируются посредством случайного выбора t среди вершин с рангом из интервала [2i, 2i + 1) согласно упорядочению, в котором вершины сканируются при помощи алгоритма Дейкстры с источником s для любого параметра i.
Очевидно, что чем меньше величина i, тем ближе друг к другу в графе располагаются вершины s и t. Локальные запросы важны для проверки влияния расстояния между конечными точками запроса на эффективность работы алгоритмов.
Семейства базовых входных данных 9-го конкурса DIMACS по реализации алгоритмов доступны по адресу http://www.dis.uniroma1.it/~challenge9/download.shtml.