4430
правок
Конкурс по реализации алгоритмов поиска кратчайших путей: различия между версиями
Материал из WEGA
Конкурс по реализации алгоритмов поиска кратчайших путей (посмотреть исходный код)
Версия от 12:01, 21 августа 2018
, 21 августа 2018→Ссылка на код
Irina (обсуждение | вклад) м (→Наборы данных) |
Irina (обсуждение | вклад) м (→Ссылка на код) |
||
| (не показаны 3 промежуточные версии этого же участника) | |||
| Строка 59: | Строка 59: | ||
• Определение эталонных программ для задач вычисления кратчайших путей. | • Определение эталонных программ для задач вычисления кратчайших путей. | ||
• Экспериментальная оценка самых современных алгоритмов нахождения кратчайших путей на семействах | • Экспериментальная оценка самых современных алгоритмов нахождения кратчайших путей на базовых семействах входных данных. | ||
• Обсуждение направлений будущих исследований в этой области, определение проблем, играющих важнейшую роль в решении реальных задач, для которых до сих пор не разработано эффективных решений. | • Обсуждение направлений будущих исследований в этой области, определение проблем, играющих важнейшую роль в решении реальных задач, для которых до сих пор не разработано эффективных решений. | ||
| Строка 74: | Строка 74: | ||
== Наборы данных == | == Наборы данных == | ||
Набор эталонных входных данных 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. | Набор эталонных входных данных 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" | ||
| Строка 232: | Строка 233: | ||
Эталонный пакет входных данных также содержит генераторы запросов для задач нахождения [[Алгоритм поиска кратчайших путей с единственным источником|кратчайших путей с единственным источником]] либо поточечного вычисления кратчайших путей. В версии задачи с единственным источником источники выбираются случайным образом. В поточечной задаче рассматриваются как случайные, так и локальные запросы. Локальные запросы вида (s, t) генерируются посредством случайного выбора t среди вершин с рангом из интервала [ | Эталонный пакет входных данных также содержит генераторы запросов для задач нахождения [[Алгоритм поиска кратчайших путей с единственным источником|кратчайших путей с единственным источником]] либо поточечного вычисления кратчайших путей. В версии задачи с единственным источником источники выбираются случайным образом. В поточечной задаче рассматриваются как случайные, так и локальные запросы. Локальные запросы вида (s, t) генерируются посредством случайного выбора t среди вершин с рангом из интервала <math>[2^i, 2^{i + 1}) \;</math> согласно порядку сканирования вершин при помощи алгоритма Дейкстры с источником s для любого параметра i. Очевидно, что чем меньше величина i, тем ближе друг к другу в графе располагаются вершины s и t. Локальные запросы важны для проверки влияния расстояния между конечными точками запроса на эффективность работы алгоритмов. | ||
Очевидно, что чем меньше величина 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. | ||
См. также | == См. также == | ||
* [[Разработка алгоритмов для применения в больших сетях]] | * [[Разработка алгоритмов для применения в больших сетях]] | ||
* [[Экспериментальные методы анализа алгоритмов]] | * [[Экспериментальные методы анализа алгоритмов]] | ||
