4551
правка
Конкурс по реализации алгоритмов поиска кратчайших путей: различия между версиями
Перейти к навигации
Перейти к поиску
м
Конкурс по реализации алгоритмов поиска кратчайших путей (посмотреть исходный код)
Версия от 11:08, 4 июня 2018
, 4 июня 2018→Наборы данных
Irina (обсуждение | вклад) м (→Наборы данных) |
Irina (обсуждение | вклад) м (→Наборы данных) |
||
| Строка 73: | Строка 73: | ||
== Наборы данных == | == Наборы данных == | ||
Набор эталонных входных данных 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" | ||
| Строка 168: | Строка 168: | ||
| [73,5; 74,5] | | [73,5; 74,5] | ||
|} | |} | ||
Таблица 1. Дорожные сети США, созданные на основе набора TIGER/Line | Таблица 1. Дорожные сети США, созданные на основе набора TIGER/Line | ||
| Строка 231: | Строка 230: | ||
Таблица 2. Результаты конкурса на графе США (23,9 миллионов вершин и 58,3 миллионов ребер) с ребрами единичной длины. Эталонным отношением считалось среднее время выполнения запроса, деленное на время выполнения вопроса при помощи эталонного кода Дейкстры на той же платформе. Время выполнения запроса и количество просканированных вершин представляют собой средние значения в пересчете на запрос на выборке из более чем 1000 случайных запросов | Таблица 2. Результаты конкурса на графе США (23,9 миллионов вершин и 58,3 миллионов ребер) с ребрами единичной длины. Эталонным отношением считалось среднее время выполнения запроса, деленное на время выполнения вопроса при помощи эталонного кода Дейкстры на той же платформе. Время выполнения запроса и количество просканированных вершин представляют собой средние значения в пересчете на запрос на выборке из более чем 1000 случайных запросов | ||