4430
правок
Конкурс по реализации алгоритмов поиска кратчайших путей: различия между версиями
Материал из WEGA
Конкурс по реализации алгоритмов поиска кратчайших путей (посмотреть исходный код)
Версия от 12:01, 21 августа 2018
, 21 августа 2018→Ссылка на код
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) м (→Ссылка на код) |
||
| (не показано 17 промежуточных версий этого же участника) | |||
| Строка 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 годах и был посвящен сетевым потокам и паросочетаниям. Далее рассматривались следующие задачи: | Первый конкурс был проведен в 1990-1991 годах и был посвящен сетевым потокам и паросочетаниям. Далее рассматривались следующие задачи: поиск максимальной клики, раскраска графа и выполнимость (1992-1993), параллельные алгоритмы для решения комбинаторных задач (1993-1994), сборка фрагментов и перестройка генома (1994-1995), очереди с приоритетами, словари и многомерные множества точек (1995-1996), поиск ближайших соседей (1998-1999), полуопределенные и родственные задачи оптимизации (1999-2000) и задача коммивояжера (2000-2001). | ||
| Строка 14: | Строка 14: | ||
'''9-й конкурс DIMACS по реализации алгоритмов: задача нахождения кратчайших путей''' | '''9-й конкурс DIMACS по реализации алгоритмов: задача нахождения кратчайших путей''' | ||
Задачи о нахождении кратчайших путей входят в число самых фундаментальных задач комбинаторной оптимизации, имеющих множество приложений – как непосредственно, так и в виде подпрограмм других алгоритмов комбинаторной оптимизации. Алгоритмы решения этих задач | Задачи о нахождении кратчайших путей входят в число самых фундаментальных задач комбинаторной оптимизации, имеющих множество приложений – как непосредственно, так и в виде подпрограмм других алгоритмов комбинаторной оптимизации. Алгоритмы решения этих задач изучались еще с 1950-х годов и остаются сферой активных исследований по настоящий день. | ||
Одной из задач этого конкурса было создание воспроизводимой картины состояния дел в области алгоритмов поиска кратчайших путей, которая позволила бы сформировать стандартный набор экземпляров эталонных тестов | Одной из задач этого конкурса было создание воспроизводимой картины состояния дел в области алгоритмов поиска кратчайших путей, которая позволила бы сформировать стандартный набор экземпляров и генераторов эталонных тестов, а также эталонные реализации хорошо известных алгоритмов поиска кратчайших путей. Еще одной задачей была возможность сравнения разработчиками текстов программ друг с другом для определения самых эффективных из недавно предложенных алгоритмических инноваций. | ||
Участники конкурса изучали следующие варианты задачи нахождения кратчайших путей: | Участники конкурса изучали следующие варианты задачи нахождения кратчайших путей: | ||
Задача заключается в ответе на множество | • ''Поточечное вычисление кратчайших путей'' [4, 5, 6, 9, 10, 11, 14]: | ||
Задача заключается в ответе в режиме онлайн на множество вопросов о кратчайших путях между парами вершин и/или их длинах. Наиболее эффективные подходы к решению этой задачи включают предварительную обработку графа для создания структуры данных, позволяющей быстро отвечать на вопросы. | |||
• ''Поиск кратчайших путей во внешней памяти'' [2]: | • ''Поиск кратчайших путей во внешней памяти'' [2]: | ||
Задача заключается в | Задача заключается в нахождении кратчайших путей в графе, размер которого слишком велик для хранения во внутренней памяти. Во время конкурса фактически решалась задача нахождения кратчайших путей с единственным источником в неориентированных графах с единичными весами ребер. | ||
| Строка 47: | Строка 48: | ||
Кульминацией конкурса стал семинар в центре 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. | ||
== Основные результаты == | == Основные результаты == | ||
| Строка 58: | Строка 59: | ||
• Определение эталонных программ для задач вычисления кратчайших путей. | • Определение эталонных программ для задач вычисления кратчайших путей. | ||
• Экспериментальная оценка самых современных алгоритмов нахождения кратчайших путей на семействах | • Экспериментальная оценка самых современных алгоритмов нахождения кратчайших путей на базовых семействах входных данных. | ||
• Обсуждение направлений будущих исследований в этой области, определение проблем, играющих важнейшую роль в решении реальных задач, для которых до сих пор не разработано эффективных решений. | • Обсуждение направлений будущих исследований в этой области, определение проблем, играющих важнейшую роль в решении реальных задач, для которых до сих пор не разработано эффективных решений. | ||
| Строка 69: | Строка 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, предоставленных географическим подразделением Бюро переписи населения США (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" | ||
| Строка 92: | Строка 94: | ||
| CTR | | CTR | ||
| Центр США | | Центр США | ||
| | | 14 081 816 | ||
| 34 | | 34 292 496 | ||
| [25,0; 50,0] | | [25,0; 50,0] | ||
| [79,0; 100,0] | | [79,0; 100,0] | ||
| Строка 99: | Строка 101: | ||
| W | | W | ||
| Запад США | | Запад США | ||
| 6 | | 6 262 104 | ||
| 15 | | 15 248 146 | ||
| [27.0; 50.0] | | [27.0; 50.0] | ||
| [100.0; 130.0] | | [100.0; 130.0] | ||
| Строка 106: | Строка 108: | ||
| E | | E | ||
| Восток США | | Восток США | ||
| 3 | | 3 598 623 | ||
| | | 8 778 114 | ||
| [24,0; 50,0] | | [24,0; 50,0] | ||
| [- | | [<math>- \infty</math>; 79,0] | ||
|- | |- | ||
| LKS | | LKS | ||
| Великие озера | | Великие озера | ||
| | | 2 758 119 | ||
| | | 6 885 658 | ||
| [41,0; 50,0] | | [41,0; 50,0] | ||
| [74,0; 93,0] | | [74,0; 93,0] | ||
| Строка 120: | Строка 122: | ||
| CAL | | CAL | ||
| Калифорния и Невада | | Калифорния и Невада | ||
| | | 1 890 815 | ||
| | | 4 657 742 | ||
| [32,5; 42,0] | | [32,5; 42,0] | ||
| [114.0; 125.0] | | [114.0; 125.0] | ||
| Строка 127: | Строка 129: | ||
| NE | | NE | ||
| Северо-восток США | | Северо-восток США | ||
| 1 | | 1 524 453 | ||
| 3 897 636 | | 3 897 636 | ||
| [39,5; 43,0] | | [39,5; 43,0] | ||
| [- | | [<math>- \infty</math>; 76,0] | ||
|- | |- | ||
| NW | | NW | ||
| Строка 141: | Строка 143: | ||
| FLA | | FLA | ||
| Флорида | | Флорида | ||
| | | 1 070 376 | ||
| 2 712 798 | | 2 712 798 | ||
| [24,0; 31,0] | | [24,0; 31,0] | ||
| Строка 148: | Строка 150: | ||
| COL | | COL | ||
| Колорадо | | Колорадо | ||
| 435 666 | | 435 666 | ||
| | | 1 057 066 | ||
| [37,0; 41,0] | | [37,0; 41,0] | ||
| [102,0; 109,0] | | [102,0; 109,0] | ||
| Строка 156: | Строка 158: | ||
| Область Залива | | Область Залива | ||
| 321 270 | | 321 270 | ||
| | | 800 172 | ||
| [37,0; 39,0] | | [37,0; 39,0] | ||
| [121; 123] | | [121; 123] | ||
| Строка 167: | Строка 169: | ||
| [73,5; 74,5] | | [73,5; 74,5] | ||
|} | |} | ||
Таблица 1. Дорожные сети США, созданные на основе набора TIGER/Line | Таблица 1. Дорожные сети США, созданные на основе набора TIGER/Line | ||
{| class="wikitable" | {| class="wikitable" | ||
|- | |||
! | |||
! colspan="2" | Предварительная обработка | |||
! colspan="3" | Ответы на запросы | |||
|- | |- | ||
! Алгоритм | ! Алгоритм | ||
| Строка 226: | Строка 229: | ||
|} | |} | ||
Таблица 2. Результаты конкурса на графе США (23,9 миллионов вершин и 58,3 ребер) с ребрами единичной длины. Эталонным | Таблица 2. Результаты конкурса на графе США (23,9 миллионов вершин и 58,3 миллионов ребер) с ребрами единичной длины. Эталонным отношением считалось среднее время выполнения запроса, деленное на время выполнения вопроса при помощи эталонного кода Дейкстры на той же платформе. Время выполнения запроса и количество просканированных вершин представляют собой средние значения в пересчете на запрос на выборке из более чем 1000 случайных запросов | ||
Очевидно, что чем меньше величина i, тем ближе друг к другу в графе располагаются вершины s и t. Локальные запросы важны для проверки влияния расстояния между конечными точками запроса на эффективность работы алгоритмов. | Эталонный пакет входных данных также содержит генераторы запросов для задач нахождения [[Алгоритм поиска кратчайших путей с единственным источником|кратчайших путей с единственным источником]] либо поточечного вычисления кратчайших путей. В версии задачи с единственным источником источники выбираются случайным образом. В поточечной задаче рассматриваются как случайные, так и локальные запросы. Локальные запросы вида (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 из таблицы 1 с ребрами единичной длины и ответ на последовательность из 1000 случайных запросов о расстоянии. Детали состязания были анонсированы в первый день конкурса, а результаты получены во второй день. Для сравнения экспериментальных результатов на различных платформах каждый участник выполнял эталонный код Дейкстры [7] на графе USA с целью калибровки. Показателем для окончательной расстановки стало среднее время выполнения запроса, деленное на время выполнения запроса при помощи эталонного кода на той же платформе ("эталонное отношение"). Учитывались также такие показатели эффективности, как объем использованной памяти и среднее количество вершин, просканированных операциями поиска. | ||
Шесть поточечных алгоритмов были успешно выполнены на графе USA, определенном специально для конкурса. Самым быстрым среди них оказался | Шесть поточечных алгоритмов были успешно выполнены на графе USA, определенном специально для конкурса. Самым быстрым среди них оказался алгоритм HH-based transit [14]. Результаты приведены в таблице 2. Алгоритмы RE и REAL(16, 1) [9] не были допущены к состязанию, однако использовались организаторами для доказательства разрешимости задачи. Некоторые другие алгоритмы не сумели справиться с размером полного графа USA либо вызвали ошибки в ходе выполнения. | ||
| Строка 251: | Строка 249: | ||
Генераторы семейств задач и эталонные решатели для задач нахождения кратчайших путей можно найти по адресу http://www.dis.uniroma1.it/~challenge9/download.shtml. | Генераторы семейств задач и эталонные решатели для задач нахождения кратчайших путей можно найти по адресу http://www.dis.uniroma1.it/~challenge9/download.shtml. | ||
См. также | == См. также == | ||
* [[Разработка алгоритмов для применения в больших сетях]] | * [[Разработка алгоритмов для применения в больших сетях]] | ||
* [[Экспериментальные методы анализа алгоритмов]] | * [[Экспериментальные методы анализа алгоритмов]] | ||
* [[Разработка высокоэффективных алгоритмов для крупномасштабных задач]] | * [[Разработка высокоэффективных алгоритмов для крупномасштабных задач]] | ||
* [[ | * [[Конкурс по реализации эвристик для задачи коммивояжера]] | ||
* [[LED A: Библиотека эффективных алгоритмов]] | * [[LED A: Библиотека эффективных алгоритмов]] | ||
