4446
правок
Конкурс по реализации алгоритмов поиска кратчайших путей: различия между версиями
Перейти к навигации
Перейти к поиску
Конкурс по реализации алгоритмов поиска кратчайших путей (посмотреть исходный код)
Версия от 09:59, 1 июня 2018
, 1 июня 2018→Наборы данных
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 215: | Строка 215: | ||
Таблица 2. Результаты конкурса на графе США (23,9 миллионов вершин и 58,3 дуг) с дугами единичной длины. Эталонным показателем считалось среднее время выполнения запроса, деленное на время выполнения вопроса при помощи эталонного кода Дейкстры (Challenge Dijkstra) на той же платформе. Время выполнения запроса и количество просканированных вершин представляют собой средние значения в пересчете на запрос на выборке из более чем 1000 случайных запросов | Таблица 2. Результаты конкурса на графе США (23,9 миллионов вершин и 58,3 дуг) с дугами единичной длины. Эталонным показателем считалось среднее время выполнения запроса, деленное на время выполнения вопроса при помощи эталонного кода Дейкстры (Challenge Dijkstra) на той же платформе. Время выполнения запроса и количество просканированных вершин представляют собой средние значения в пересчете на запрос на выборке из более чем 1000 случайных запросов | ||
Файлы предоставлены географическим подразделением Бюро переписи населения США (US Census Bureau) в Вашингтоне, округ Колумбия. Набор TIGER/Line доступен по адресу http://www.census.gov/geo/www/tiger/ tigerua/ua_tgr2k.html. Базовое семейство USA содержит граф, представляющий всю дорожную сеть США с 24 миллионами вершин и 58 миллионами ребер, а также 11 подграфов, полученных в результате разрезания ее при помощи различных ограничивающих прямоугольников, как показано в таблице 1. Графы в этом наборе также содержат координаты вершин и представлены в формате DIMACS. | |||
Эталонный пакет входных данных также содержит генераторы запросов для задач нахождения кратчайших путей с единственным источником либо двухточечных. В версии задачи с единственным источником источники выбираются случайным образом. В двухточечной задаче рассматриваются как случайные, так и локальные запросы. Локальные запросы вида (s, t) генерируются посредством случайного выбора t среди вершин с рангом из интервала [2i, 2i + 1) согласно упорядочению, в котором вершины сканируются при помощи алгоритма Дейкстры с источником s для любого параметра i. | |||
Очевидно, что чем меньше величина i, тем ближе друг к другу в графе располагаются вершины s и t. Локальные запросы важны для проверки влияния расстояния между конечными точками запроса на эффективность работы алгоритмов. | |||
Семейства базовых входных данных 9-го конкурса DIMACS по реализации алгоритмов доступны по адресу http://www.dis.uniroma1.it/~challenge9/download.shtml. | |||
== Экспериментальные результаты == | |||