4446
правок
Irina (обсуждение | вклад) м (→Нотация) |
Irina (обсуждение | вклад) мНет описания правки |
||
(не показано 6 промежуточных версий этого же участника) | |||
Строка 1: | Строка 1: | ||
== Ключевые слова и синонимы == | == Ключевые слова и синонимы == | ||
Поиск кратчайших путей в планарных графах с весами дуг общего вида; поиск кратчайших путей в планарных графах с произвольными весами дуг | Поиск кратчайших путей в планарных графах с весами дуг общего вида; поиск кратчайших путей в планарных графах с произвольными весами дуг | ||
== Постановка задачи == | == Постановка задачи == | ||
Строка 77: | Строка 76: | ||
== Применение == | == Применение == | ||
Задача поиска кратчайших путей давно | Задача поиска кратчайших путей давно стала предметом изучения, она находит применение в самых разных областях. Существует множество задач, сводимых к задаче поиска кратчайших путей, в которых предполагаются отрицательные веса ребер; в качестве примера можно привести поиск ориентированной схемы с минимальной средней длиной. Для планарных графов данная задача широко применяется даже в случаях, когда лежащий в основе задачи граф представляет собой решетку. Например, недавно разработанные подходы к сегментации изображений используют функцию определения отрицательных циклов [2, 3]. В числе других областей применения планарных графов можно упомянуть алгоритмы поиска сепараторов [13] и алгоритмы потока с несколькими источниками и несколькими стоками [13]. | ||
== Открытые вопросы == | == Открытые вопросы == | ||
Клейн [8] предложил технику, улучшающую время построения плотного графа расстояний до <math>O(n \; log^2 \; n)</math> для случая неотрицательных весов ребер; она также снижает амортизированное время выполнения для динамического случая до <math>O(n^{2/3} \; log^{5/3} \; n)</math>. Также для | Клейн [8] предложил технику, улучшающую время построения плотного графа расстояний до <math>O(n \; log^2 \; n)</math> для случая неотрицательных весов ребер; она также снижает амортизированное время выполнения для динамического случая до <math>O(n^{2/3} \; log^{5/3} \; n)</math>. Также для планарных графов с неотрицательными весами ребер Кабелло [1] приводит более быстрый алгоритм вычисления кратчайших расстояний между k парами вершин. Однако задача улучшения границы <math>O(n \; log^3 \; n)</math> алгоритма нахождения кратчайших путей в планарных графах с весами ребер общего вида все еще остается нерешенной. | ||
Неизвестно, как обрабатывать вставку и удаление ребер в динамической структуре данных. Возможно, потребуется введение новой структуры данных вместо плотного графа расстояний, поскольку последний определяется посредством декомпозиции. | Неизвестно, как обрабатывать вставку и удаление ребер в динамической структуре данных. Возможно, потребуется введение новой структуры данных вместо плотного графа расстояний, поскольку последний определяется посредством декомпозиции. | ||
== См. также == | == См. также == | ||
* ''[[Алгоритм поиска кратчайших путей в разреженных графах]] | * ''[[Алгоритм поиска кратчайших путей между всеми парами в разреженных графах]] | ||
* ''[[Алгоритм поиска кратчайших путей при помощи матричного произведения]] | * ''[[Алгоритм поиска кратчайших путей между всеми парами при помощи матричного произведения]] | ||
* ''[[ | * ''[[Аппроксимационные схемы для задач с планарными графами]] | ||
* ''[[Декрементный алгоритм нахождения кратчайших путей между всеми парами]] | * ''[[Декрементный алгоритм нахождения кратчайших путей между всеми парами]] | ||
* ''[[Полностью динамический алгоритм нахождения кратчайших путей между всеми парами]] | * ''[[Полностью динамический алгоритм нахождения кратчайших путей между всеми парами]] | ||
* ''[[ | * ''[[Конкурс по реализации алгоритмов поиска кратчайших путей]] | ||
* ''[[Отрицательные циклы во взвешенных орграфах]] | * ''[[Отрицательные циклы во взвешенных орграфах]] | ||
* ''[[Проверка на планарность]] | * ''[[Проверка на планарность]] | ||
* ''[[Подход к составлению расписания при помощи кратчайших путей]] | * ''[[Подход к составлению расписания при помощи кратчайших путей]] | ||
* ''[[Алгоритм поиска кратчайших путей с единственным источником]] | * ''[[Алгоритм поиска кратчайших путей с единственным источником]] | ||
== Литература == | == Литература == |
правок