Конкурс по реализации алгоритмов поиска кратчайших путей

Ключевые слова и синонимы

Наборы тестов и экспериментальная оценка программ для решения задач поиска кратчайших путей; DIMACS

Постановка задачи

Конкурсы DIMACS по реализации алгоритмов (http://dimacs.rutgers.edu/Challenges/) представляют собой научные мероприятия, целью которых является оценка практической эффективности алгоритмов в экспериментальных условиях, что способствует эффективному распространению технологий и согласованию общих эталонных тестов для фундаментальных вычислительных задач. Эти конкурсы организует DIMACS – Центр дискретной математики и теории вычислительных систем (Center for Discrete Mathematics and Theoretical Computer Science). Одной из основных целей конкурсов DIMACS по реализации алгоритмов является разрешение вопросов определения производительности реалистичных алгоритмов, для которых наихудший случай оказывается чрезмерно пессимистичным, а вероятностные модели – слишком нереалистичными: экспериментальные подходы могут привести к получению алгоритмов с реалистичными показателями эффективности в случаях, когда их невозможно получить при помощи анализа. Эксперименты также позволяют приблизить алгоритмические вопросы к исходным задачам, которые стали стимулом для теоретических изысканий. Кроме того, они дают возможность проверить различные предположения о методах реализации и структурах данных. Они предоставляют возможность для разработки и тестирования экземпляров задач, генераторов экземпляров и иных методов тестирования и сравнения эффективности алгоритмов. И, наконец, они помогают технологиям сделать еще шаг вперед, предоставляя самые передовые подходы к реализации алгоритмов для освоения и внедрения другими людьми и организациями.

Первый конкурс был проведен в 1990-1991 годах и был посвящен сетевым потокам и паросочетаниям. Далее рассматривались следующие задачи: Поиск максимальной клики, раскраска графа и выполнимость (1992-1993), параллельные алгоритмы для решения комбинаторных задач (1993-1994), сборка фрагментов и перестройка генома (1994-1995), очереди с приоритетами, словари и многомерные множества точек (1995-1996), поиск ближайших соседей (1998-1999), полуопределенные и родственные задачи оптимизации (1999-2000) и задача коммивояжера (2000-2001). Далее будут рассмотрены цели и результаты 9-го конкурса DIMACS по реализации алгоритмов, проведенного в 2005-2006 годах и посвященного задачам нахождения кратчайших путей.

9-й конкурс DIMACS по реализации алгоритмов: Задача нахождения кратчайших путей

Задачи о нахождении кратчайших путей входят в число самых фундаментальных задач комбинаторной оптимизации, имеющих множество приложений – как непосредственно, так и в виде подпрограмм других алгоритмов комбинаторной оптимизации. Алгоритмы решения этих задач исследовались еще с 1950-х годов и остаются сферой активных исследований по настоящий день.

Одной из задач этого конкурса было создание воспроизводимой картины состояния дел в области алгоритмов поиска кратчайших путей, которая позволила бы сформировать стандартный набор экземпляров эталонных тестов и генераторов, а также эталонные реализации хорошо известных алгоритмов поиска кратчайших путей. Еще одной задачей была возможность сравнения разработчиками текстов программ друг с другом для определения самых эффективных из недавно предложенных алгоритмических инноваций.

Участники конкурса изучали следующие варианты задачи нахождения кратчайших путей:

• Поточечное вычисление кратчайших путей [4,5,6,9,10,11,14]: Задача заключается в ответе на множество онлайн-вопросов о кратчайших путях между парами вершин и/или их длинах. Наиболее эффективные подходы к решению этой задачи включают предварительную обработку графа для создания структуры данных, позволяющей быстро отвечать на вопросы.

• Поиск кратчайших путей во внешней памяти [2]: Задача заключается в нахождения кратчайших путей в графе, размер которого слишком велик для хранения во внутренней памяти. Во время конкурса фактически решалась задача нахождения кратчайших путей с единственным источником в неориентированных графах с единичными весами ребер.

• Параллельный поиск кратчайших путей [8, 12]: Задача заключается в вычислении кратчайших путей при помощи нескольких процессоров с целью ускорения поиска по сравнению с традиционными последовательными реализациями. Во время конкурса фактически решалась задача нахождения кратчайших путей с единственным источником.

• K-точечная задача поиска кратчайших путей [13, 15]: Задача заключается в ранжировании путей между парой вершин в порядке неубывания их длины.

• Поиск кратчайших путей с ограничениями регулярных языков [3]: Задача заключается в обобщении задачи о нахождении кратчайших путей таким образом, чтобы пути удовлетворяли определенным ограничениям, задаваемым регулярным языком. Во время конкурса изучались задачи нахождения кратчайших путей с единственным источником и поточечное вычисление кратчайших путей, а области применения варьировались от транспортных наук до баз данных.

Кульминацией конкурса стал семинар в центре DIMACS в Ратгерском университете в Пискатавэе, штат Нью-Джерси, проведенный 13-14 ноября 2006 года. Представленные на конференции доклады можно найти по адресу http://www.dis. uniroma1.it/~challenge9/papers.shtml. Избранные материалы вошли в книгу, опубликованную Американским математическим сообществом в серии DIMACS Book Series.

Основные результаты

В качестве основных результатов 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