Конкурс по реализации алгоритмов поиска кратчайших путей: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) м (→Наборы данных) |
||
Строка 64: | Строка 64: | ||
{| class="wikitable" | {| class="wikitable" | ||
|- | |- | ||
! | ! Название | ||
! | ! Описание | ||
! | ! Число вершин | ||
! | ! Число ребер | ||
! | ! Широта огранич. прям. (С) | ||
! | ! Долгота огранич. прям. (В) | ||
|- | |- | ||
| USA | | USA | ||
Строка 164: | Строка 164: | ||
{| class="wikitable" | {| class="wikitable" | ||
|- | |- | ||
! | ! Алгоритм | ||
! Время (в минутах) | ! Время (в минутах) | ||
! Память (в МБ) | ! Память (в МБ) | ||
Строка 214: | Строка 214: | ||
|} | |} | ||
Таблица 2. Результаты конкурса на графе США (23,9 миллионов вершин и 58,3 | Таблица 2. Результаты конкурса на графе США (23,9 миллионов вершин и 58,3 ребер) с ребрами единичной длины. Эталонным показателем считалось среднее время выполнения запроса, деленное на время выполнения вопроса при помощи эталонного кода Дейкстры (Challenge Dijkstra) на той же платформе. Время выполнения запроса и количество просканированных вершин представляют собой средние значения в пересчете на запрос на выборке из более чем 1000 случайных запросов | ||