4430
правок
Конкурс по реализации алгоритмов поиска кратчайших путей: различия между версиями
Материал из WEGA
Конкурс по реализации алгоритмов поиска кратчайших путей (посмотреть исходный код)
Версия от 11:10, 29 мая 2018
, 29 мая 2018→Наборы данных
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 159: | Строка 159: | ||
Таблица 1. Дорожные сети США, созданные на основе набора TIGER/Line | Таблица 1. Дорожные сети США, созданные на основе набора TIGER/Line | ||
PREPROCE | |||
{| class="wikitable" | |||
|- | |||
! АЛГОРИТМ | |||
! Время (в минутах) | |||
! Память (в МБ) | |||
! Скан. вершины | |||
! Время (в мс) | |||
! Эталонное отношение | |||
|- | |||
| HH-based transit [14] | |||
| 104 | |||
| 3664 | |||
| неизв. | |||
| 0,019 | |||
| 4,78 -10~6 | |||
|- | |||
| TRANSIT [4] | |||
| 720 | |||
| неизв. | |||
| неизв. | |||
| 0,052 | |||
| 10,77 -10~6 | |||
|- | |||
| HH Star [6] | |||
| 32 | |||
| 2662 | |||
| 1082 | |||
| 1,14 | |||
| 287,32 -10-6 | |||
|- | |||
| REAL(16,1) [9] | |||
| 107 | |||
| 2435 | |||
| 823 | |||
| 1,42 | |||
| 296,30 -10-6 | |||
|- | |||
| HH с DistTab [ ] | |||
| 29 | |||
| 2101 | |||
| 1671 | |||
| 1,61 | |||
| 405.77 -10~6 | |||
|- | |||
| RE[ ] | |||
| 88 | |||
| 861 | |||
| 3065 | |||
| 2,78 | |||
| 580,08 -10~6 | |||
|} | |||
Таблица 2 | Таблица 2 | ||
Результаты конкурса на графе США (23,9 миллионов вершин и 58,3 дуг) с дугами единичной длины. Эталонным показателем считалось среднее время выполнения запроса, деленное на время выполнения вопроса при помощи эталонного кода Дейкстры (Challenge Dijkstra) на той же платформе. Время выполнения запроса и количество просканированных вершин представляют собой средние значения в пересчете на запрос на выборке из более чем 1000 случайных запросов | Результаты конкурса на графе США (23,9 миллионов вершин и 58,3 дуг) с дугами единичной длины. Эталонным показателем считалось среднее время выполнения запроса, деленное на время выполнения вопроса при помощи эталонного кода Дейкстры (Challenge Dijkstra) на той же платформе. Время выполнения запроса и количество просканированных вершин представляют собой средние значения в пересчете на запрос на выборке из более чем 1000 случайных запросов | ||
