4446
правок
Конкурс по реализации алгоритмов поиска кратчайших путей: различия между версиями
Перейти к навигации
Перейти к поиску
Конкурс по реализации алгоритмов поиска кратчайших путей (посмотреть исходный код)
Версия от 10:57, 29 мая 2018
, 29 мая 2018→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 38: | Строка 38: | ||
== Основные результаты == | == Основные результаты == | ||
В качестве основных результатов 9-го конкурса DIMACS по реализации алгоритмов можно упомянуть следующие: | |||
• Определение общих форматов файлов для нескольких вариантов задачи о нахождении кратчайших путей – как статических, так и динамических. Они включают расширение известного графового формата DIMACS, используемого несколькими библиотеками алгоритмических приложений. С форматами можно ознакомиться по адресу http://www.dis.uniroma1.it/~challenge9/formats.shtml. | |||
• Определение общего набора базовых экземпляров входных данных для оценки алгоритмов вычисления кратчайших путей. | |||
• Определение эталонных программ для задач вычисления кратчайших путей. | |||
• Экспериментальная оценка самых современных алгоритмов нахождения кратчайших путей на семействах базовых входных данных. | |||
• Обсуждение направлений будущих исследований в этой области, определение проблем, играющих важнейшую роль в решении реальных задач, для которых до сих пор не разработано эффективных решений. | |||
Основным источником информации о материалах и решениях 9-го конкурса DIMACS по реализации алгоритмов является сайт http://www.dis. uniroma1.it/~challenge9. | |||
== Применение == | |||
Задачи о нахождении кратчайших путей естественным образом возникают в огромном количестве ситуаций. В качестве примеров сценариев применения можно привести такие задачи, как дорожно-транспортная планировка, оптимизация сетей, маршрутизация пакетов, сегментация изображений, распознавание речи, форматирование документов, робототехника, компиляторы, системы управления информацией о дорожном движении и анализ потоков данных. Они также встречаются в виде подзадач нескольких других задач комбинаторной оптимизации – таких как организация сетевого потока. Исчерпывающее обсуждение областей применения алгоритмов нахождения кратчайших путей приведено в [1]. | |||
== Открытые вопросы == | |||
До сих пор остаются нерешенными некоторые вопросы, связанные с задачами нахождения кратчайших путей – как теоретические, так и практические. Одним из самых перспективных направлений, обсуждавшимся во время семинара на 9-м конкурсе 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 | |||
Таблица 1. Дорожные сети США, созданные на основе набора TIGER/Line | |||
НАЗВАНИЕ ОПИСАНИЕ ЧИСЛО ВЕРШИН ЧИСЛО ДУГ ШИРОТА ОГР. ПРЯМ. (С) ДОЛГОТА ОГР. ПРЯМ. (В) | |||
USA США (вся страна) 23 947 347 58 333 344 - - | |||
CTR Центр США 14081816 34 292496 [25.0; 50.0] [79.0; 100.0] | |||
W Запад США 6 262104 15 248146 [27.0; 50.0] [100.0; 130.0] | |||
E Восток США 3 598623 8778114 [24.0; 50.0] [-1; 79.0] | |||
LKS Великие озера 2758119 6885 658 [41.0; 50.0] [74.0; 93.0] | |||
CAL Калифорния и Невада 1890815 4657 742 [32.5; 42.0] [114.0; 125.0] | |||
NE Северо-восток США 1 524453 3 897 636 [39.5,43.0] [-1; 76.0] | |||
NW Северо-запад США 1 207 945 2 840 208 [42.0; 50.0] [116.0; 126.0] | |||
FLA Флорида 1070 376 2 712 798 [24.0; 31.0] [79; 87.5] | |||
COL Колорадо 435 666. 1057 066 [37.0; 41.0] [102.0; 109.0] | |||
BAY Область Залива 321 270 800172 [37.0; 39.0] [121; 123] | |||
NY Нью-Йорк 264 346 733 846 [40.3; 41.3] [73.5; 74.5] | |||
Таблица 2 | |||
Результаты конкурса на графе США (23,9 миллионов вершин и 58,3 дуг) с дугами единичной длины. Эталонным показателем считалось среднее время выполнения запроса, деленное на время выполнения вопроса при помощи эталонного кода Дейкстры (Challenge Dijkstra) на той же платформе. Время выполнения запроса и количество просканированных вершин представляют собой средние значения в пересчете на запрос на выборке из более чем 1000 случайных запросов | |||
PREPROCE | |||
АЛГОРИТМ Время (в минутах) Память (в МБ) Скан. вершины Время (в мс) Эталонное отношение | |||
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-lO"6 | |||
REAL(16,1) [9] 107 2435 823 1.42 296,30-lO"6 | |||
HH с DistTab [ ] 29 2101 1671 1.61 405.77 -10~6 | |||
RE[ ] 88 861 3065 2.78 580.08 -10~6 | |||