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