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

Одной из главных задач конкурса было сравнение различных техник и алгоритмических подходов. Самой популярной темой оказалось поточечное вычисление кратчайших путей, которое в контексте конкурса изучали шесть исследовательских групп. Для этой задачи было дополнительно проведено состязание между участниками с целью оценки эффективности и надежности различных реализаций алгоритмов. Состязание включало в себя предварительную обработку версии полного графа USA из таблицы 1 с ребрами единичной длины и ответ на последовательность из 1000 случайных запросов о расстоянии. Детали состязания были анонсированы в первый день конкурса, а результаты получены во второй день. Для сравнения экспериментальных результатов на различных платформах каждый участник выполнял эталонный код Дейкстры [7] на графе USA с целью калибровки. Показателем для окончательной расстановки стало среднее время выполнения запроса, деленное на время выполнения запроса при помощи эталонного кода на той же платформе ("эталонное отношение"). Учитывались также такие показатели эффективности, как объем использованной памяти и среднее количество вершин, просканированных операциями поиска.

Шесть поточечных алгоритмов были успешно выполнены на графе USA, определенном специально для конкурса. Самым быстрым среди них оказался алгоритм HH-based transit [14]. Результаты приведены в таблице 2. Алгоритмы RE и REAL(16, 1) [9] не были допущены к состязанию, однако использовались организаторами для доказательства разрешимости задачи. Некоторые другие алгоритмы не сумели справиться с размером полного графа USA либо вызвали ошибки в ходе выполнения.

== См. также ==