4430
правок
Конкурс по реализации алгоритмов поиска кратчайших путей: различия между версиями
Материал из WEGA
Конкурс по реализации алгоритмов поиска кратчайших путей (посмотреть исходный код)
Версия от 11:11, 4 июня 2018
, 4 июня 2018→Наборы данных
Irina (обсуждение | вклад) м (→Наборы данных) |
Irina (обсуждение | вклад) м (→Наборы данных) |
||
| Строка 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. | Семейства базовых входных данных 9-го конкурса DIMACS по реализации алгоритмов доступны по адресу http://www.dis.uniroma1.it/~challenge9/download.shtml. | ||
