Конкурс по реализации алгоритмов поиска кратчайших путей: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 6: | Строка 6: | ||
Первый конкурс был проведен в 1990-1991 годах и был посвящен сетевым потокам и паросочетаниям. Далее рассматривались следующие задачи: | Первый конкурс был проведен в 1990-1991 годах и был посвящен сетевым потокам и паросочетаниям. Далее рассматривались следующие задачи: поиск максимальной клики, раскраска графа и выполнимость (1992-1993), параллельные алгоритмы для решения комбинаторных задач (1993-1994), сборка фрагментов и перестройка генома (1994-1995), очереди с приоритетами, словари и многомерные множества точек (1995-1996), поиск ближайших соседей (1998-1999), полуопределенные и родственные задачи оптимизации (1999-2000) и задача коммивояжера (2000-2001). | ||
| Строка 14: | Строка 14: | ||
'''9-й конкурс DIMACS по реализации алгоритмов: задача нахождения кратчайших путей''' | '''9-й конкурс DIMACS по реализации алгоритмов: задача нахождения кратчайших путей''' | ||
Задачи о нахождении кратчайших путей входят в число самых фундаментальных задач комбинаторной оптимизации, имеющих множество приложений – как непосредственно, так и в виде подпрограмм других алгоритмов комбинаторной оптимизации. Алгоритмы решения этих задач | Задачи о нахождении кратчайших путей входят в число самых фундаментальных задач комбинаторной оптимизации, имеющих множество приложений – как непосредственно, так и в виде подпрограмм других алгоритмов комбинаторной оптимизации. Алгоритмы решения этих задач изучались еще с 1950-х годов и остаются сферой активных исследований по настоящий день. | ||
Одной из задач этого конкурса было создание воспроизводимой картины состояния дел в области алгоритмов поиска кратчайших путей, которая позволила бы сформировать стандартный набор экземпляров эталонных тестов | Одной из задач этого конкурса было создание воспроизводимой картины состояния дел в области алгоритмов поиска кратчайших путей, которая позволила бы сформировать стандартный набор экземпляров и генераторов эталонных тестов, а также эталонные реализации хорошо известных алгоритмов поиска кратчайших путей. Еще одной задачей была возможность сравнения разработчиками текстов программ друг с другом для определения самых эффективных из недавно предложенных алгоритмических инноваций. | ||
Участники конкурса изучали следующие варианты задачи нахождения кратчайших путей: | Участники конкурса изучали следующие варианты задачи нахождения кратчайших путей: | ||
• ''Поточечное вычисление кратчайших путей'' [4,5,6,9,10,11,14]: | • ''Поточечное вычисление кратчайших путей'' [4, 5, 6, 9, 10, 11, 14]: | ||
Задача заключается в ответе на множество | Задача заключается в ответе в режиме онлайн на множество вопросов о кратчайших путях между парами вершин и/или их длинах. Наиболее эффективные подходы к решению этой задачи включают предварительную обработку графа для создания структуры данных, позволяющей быстро отвечать на вопросы. | ||