Конкурс по реализации алгоритмов поиска кратчайших путей
Ключевые слова и синонимы
Наборы тестов и экспериментальная оценка программ для решения задач поиска кратчайших путей; 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-1 конкурс 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.