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

Материал из WEGA
Перейти к навигации Перейти к поиску
 
(не показаны 24 промежуточные версии этого же участника)
Строка 3: Строка 3:


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




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




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


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




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




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


•  Поточечное вычисление кратчайших путей [4,5,6,9,10,11,14]: Задача заключается в ответе на множество онлайн-вопросов о кратчайших путях между парами вершин и/или их длинах. Наиболее эффективные подходы к решению этой задачи включают предварительную обработку графа для создания структуры данных, позволяющей быстро отвечать на вопросы.


•  ''Поточечное вычисление кратчайших путей'' [4, 5, 6, 9, 10, 11, 14]:
Задача заключается в ответе в режиме онлайн на множество вопросов о кратчайших путях между парами вершин и/или их длинах. Наиболее эффективные подходы к решению этой задачи включают предварительную обработку графа для создания структуры данных, позволяющей быстро отвечать на вопросы.
• ''Поиск кратчайших путей во внешней памяти'' [2]:
Задача заключается в нахождении кратчайших путей в графе, размер которого слишком велик для хранения во внутренней памяти. Во время конкурса фактически решалась задача нахождения кратчайших путей с единственным источником в неориентированных графах с единичными весами ребер.


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


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


• Параллельный поиск кратчайших путей [8, 12]: Задача заключается в вычислении кратчайших путей при помощи нескольких процессоров с целью ускорения поиска по сравнению с традиционными последовательными реализациями. Во время конкурса фактически решалась задача нахождения кратчайших путей с единственным источником.
Задача заключается в вычислении кратчайших путей при помощи нескольких процессоров с целью ускорения поиска по сравнению с традиционными последовательными реализациями. Во время конкурса фактически решалась задача нахождения кратчайших путей с единственным источником.




• K-точечная задача поиска кратчайших путей [13, 15]: Задача заключается в ранжировании путей между парой вершин в порядке неубывания их длины.
''K-точечная задача поиска кратчайших путей'' [13, 15]:


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


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


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


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


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


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


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


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


{| class="wikitable"
{| class="wikitable"
|-
|-
! НАЗВАНИЕ
! Название
! ОПИСАНИЕ
! Описание
! ЧИСЛО ВЕРШИН
! Число вершин
! ЧИСЛО ДУГ
! Число ребер
! ШИРОТА ОГРАНИЧ. ПРЯМ. (С)
! Широта огранич. прям. (С)
! ДОЛГОТА ОГРАНИЧ. ПРЯМ. (В)
! Долгота огранич. прям. (В)
|-
|-
| USA
| USA
Строка 80: Строка 94:
| CTR
| CTR
| Центр США
| Центр США
| 14081816
| 14 081 816
| 34 292496
| 34 292 496
| [25,0; 50,0]
| [25,0; 50,0]
| [79,0; 100,0]
| [79,0; 100,0]
Строка 87: Строка 101:
| W
| W
| Запад США
| Запад США
| 6 262104
| 6 262 104
| 15 248146
| 15 248 146
| [27.0; 50.0]
| [27.0; 50.0]
| [100.0; 130.0]
| [100.0; 130.0]
Строка 94: Строка 108:
| E
| E
| Восток США
| Восток США
| 3 598623
| 3 598 623
| 8778114
| 8 778 114
| [24,0; 50,0]
| [24,0; 50,0]
| [-1; 79,0]
| [<math>- \infty</math>; 79,0]
|-
|-
| LKS
| LKS
| Великие озера
| Великие озера
| 2758119
| 2 758 119
| 6885 658
| 6 885 658
| [41,0; 50,0]
| [41,0; 50,0]
| [74,0; 93,0]
| [74,0; 93,0]
Строка 108: Строка 122:
| CAL
| CAL
| Калифорния и Невада
| Калифорния и Невада
| 1890815
| 1 890 815
| 4657 742
| 4 657 742
| [32,5; 42,0]
| [32,5; 42,0]
| [114.0; 125.0]
| [114.0; 125.0]
Строка 115: Строка 129:
| NE
| NE
| Северо-восток США
| Северо-восток США
| 1 524453
| 1 524 453
| 3 897 636
| 3 897 636
| [39,5; 43,0]
| [39,5; 43,0]
| [-1; 76,0]
| [<math>- \infty</math>; 76,0]
|-
|-
| NW
| NW
Строка 129: Строка 143:
| FLA
| FLA
| Флорида
| Флорида
| 1070 376
| 1 070 376
| 2 712 798
| 2 712 798
| [24,0; 31,0]
| [24,0; 31,0]
Строка 136: Строка 150:
| COL
| COL
| Колорадо
| Колорадо
| 435 666.
| 435 666
| 1057 066
| 1 057 066
| [37,0; 41,0]
| [37,0; 41,0]
| [102,0; 109,0]
| [102,0; 109,0]
Строка 144: Строка 158:
| Область Залива
| Область Залива
| 321 270
| 321 270
| 800172
| 800 172
| [37,0; 39,0]
| [37,0; 39,0]
| [121; 123]
| [121; 123]
Строка 155: Строка 169:
| [73,5; 74,5]
| [73,5; 74,5]
|}
|}


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


PREPROCE


{| class="wikitable"
{| class="wikitable"
|-
|-
! АЛГОРИТМ
!  
! colspan="2" | Предварительная обработка
! colspan="3" | Ответы на запросы
|-
! Алгоритм
! Время (в минутах)
! Время (в минутах)
! Память (в МБ)
! Память (в МБ)
Строка 214: Строка 229:
|}
|}


Таблица 2. Результаты конкурса на графе США (23,9 миллионов вершин и 58,3 дуг) с дугами единичной длины. Эталонным показателем считалось среднее время выполнения запроса, деленное на время выполнения вопроса при помощи эталонного кода Дейкстры (Challenge Dijkstra) на той же платформе. Время выполнения запроса и количество просканированных вершин представляют собой средние значения в пересчете на запрос на выборке из более чем 1000 случайных запросов
Таблица 2. Результаты конкурса на графе США (23,9 миллионов вершин и 58,3 миллионов ребер) с ребрами единичной длины. Эталонным отношением считалось среднее время выполнения запроса, деленное на время выполнения вопроса при помощи эталонного кода Дейкстры на той же платформе. Время выполнения запроса и количество просканированных вершин представляют собой средние значения в пересчете на запрос на выборке из более чем 1000 случайных запросов
 
 
 
Эталонный пакет входных данных также содержит генераторы запросов для задач нахождения [[Алгоритм поиска кратчайших путей с единственным источником|кратчайших путей с единственным источником]] либо поточечного вычисления кратчайших путей. В версии задачи с единственным источником источники выбираются случайным образом. В поточечной задаче рассматриваются как случайные, так и локальные запросы. Локальные запросы вида (s, t) генерируются посредством случайного выбора t среди вершин с рангом из интервала <math>[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.
 
== См. также ==
* [[Разработка алгоритмов для применения в больших сетях]]
* [[Экспериментальные методы анализа алгоритмов]]
* [[Разработка высокоэффективных алгоритмов для крупномасштабных задач]]
* [[Конкурс по реализации эвристик для задачи коммивояжера]]
* [[LED A: Библиотека эффективных алгоритмов]]
 
== Литература ==
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

Текущая версия от 12:01, 21 августа 2018

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

Наборы тестов и экспериментальная оценка программ для решения задач поиска кратчайших путей; 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