Русская Википедия:Задача о самом длинном пути

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Задача о самом длинном пути — это задача поиска простого пути максимальной длины в заданном графе. Путь называется простым, если в нём нет повторных вершин. Длина пути может быть измерена либо числом рёбер, либо (в случае взвешенных графов) суммой весов его рёбер. В отличие от задачи кратчайшего пути, которая может быть решена за полиномиальное время на графах без циклов с отрицательным весом, задача нахождения самого длинного пути является NP-трудной и не может быть решена за полиномиальное время для произвольных графов, если только не P = NP. Принадлежность более тяжелому классу сложности также означает, что задачу трудно аппроксимировать. Однако задача решается за линейное время на ориентированных ациклических графах, которые имеют важное применение в задачах нахождения критического пути в задачах планирования.

NP-трудность

NP-трудность невзвешенной задачи поиска самого длинного пути можно показать, сведя задачу к поиску Шаблон:Не переведено 5 — граф G имеет гамильтонов путь тогда и только тогда, когда самый длинный путь в нём имеет длину n − 1, где n — число вершин графа G. Поскольку задача поиска гамильтонова пути является NP-полной, это сведение показывает, что задачи поиска самого длинного пути в варианте разрешимости также NP-полна. В этой задаче разрешимости входом является граф G и число k. Ожидается выход "да", если G содержит путь с k и больше дугами, или нет в противном случаеШаблон:Sfn.

Если бы задача поиска самого длинного пути могла быть решена за полиномиальное время, она могла бы быть использована для решения этой задачи разрешимости путём нахождения самого длинного пути и сравнения длины полученного пути с числом k. Таким образом, задача поиска самого длинного пути является NP-трудной. Она не является NP-полной, поскольку она не является задачей разрешимостиШаблон:Sfn.

Во взвешенных полных графах с неотрицательными весами рёбер задача поиска взвешенного самого длинного пути является той же самой задачей, что и задача коммивояжёра, поскольку самый длинный путь всегда включает все вершины этой задачиШаблон:Sfn.

Ацикличные графы и критические пути

Самый длинный путь A между двумя заданными вершинами s и t во взвешенном графе G — это то же самое, что и кратчайший путь в графе −G, полученном из G путём замены всех весов на веса с обратным знаком. Таким образом, если кратчайший путь можно найти в −G, то можно найти и самый длинный путь в GШаблон:Sfn.

Для большинства графов такое преобразование бесполезно, поскольку создаёт циклы отрицательной длины в −G. Но если G является ориентированным ациклическим графом, невозможно создать отрицательный цикл и самый длинный путь в G может быть найден за линейное время, применив алгоритм поиска кратчайшего пути в −G (тоже ориентированный ациклический граф), который работает за линейное времяШаблон:Sfn. Например, для любой вершины v в ориентированном ациклическом графе длина самого длинного пути, заканчивающегося в v, может быть получена выполнением следующих шагов:

  1. Осуществляем топологическую сортировку заданного ориентированного ациклического графа (ОАГ).
  2. Для каждой вершины v ОАГ в топологической сортировке вычисляем длину самого длинного пути, завершающегося в вершине v путём просмотра входящих дуг от соседей и добавления единички к максимальной длине в записях этих соседей. Если v не имеет входящих дуг, присваиваем длину самого длинного пути, кончающегося в v, нулю.

Когда это будет сделано, самый длинный путь во всём графе можно получить, начав с вершины v с самым большим записанным значением и проходя в обратном порядке, выбирая входящую дугу, у которой запись в начальной вершине имеет наибольшее значение.

Метод критического пути для планирования набора работ использует построение ориентированного ацикличного графа, в котором вершины представляют узловые события проекта, а дуги представляют работы, которые должны быть выполнены до узлового события и после него. Каждой дуге присваивается вес, равный оценочному времени выполнения работы. В таком графе самый длинный путь от первого узлового события до последнего является критическим путём, который определяет полное время завершения проектаШаблон:Sfn.

Самый длинный путь ориентированных ацикличных графов можно применить также для послойного рисования графов — располагаем каждую вершину v ориентированного ацикличного графа G на уровне, номер которого соответствует длине самого длинного пути, заканчивающегося в v. В результате получим расположение вершин по уровням, при котором число уровней будет минимальнымШаблон:Sfn.

Приближение

Бьёрклунд, Хасфелдт и Канна писали, что задача поиска самого длинного пути в невзвешенном неориентированном графе является «печально известной по сложности понимания её трудности аппроксимации»Шаблон:Sfn. Лучший известный алгоритм аппроксимации полиномиального времени выполнения даёт лишь очень слабую аппроксимацию, <math> n/\exp(\Omega(\sqrt{\log n}))</math> [1]. Для любого <math>\epsilon>0</math> невозможно аппроксимировать самый длинный путь со множителем, меньшим <math>2^{(\log n)^{1-\epsilon}}</math>, если только NP не принадлежит задачам квазиполиномиального детерминированного времени. Однако существует большой разрыв между этим результатом аппроксимируемости и известными алгоритмами аппроксимации для этой задачиШаблон:Sfn.

В случае невзвешенных, но ориентированных графов известные сильные результаты аппроксимируемости. Для любого <math>\epsilon>0</math> задача не может быть аппроксимирована в пределах <math>n^{1-\epsilon}</math>, если только не P = NP, и, при сильных теоретических предположениях, задачу нельзя аппроксимировать в пределах <math>n/\log^{2+\epsilon} n</math>Шаблон:Sfn. Можно использовать технику Шаблон:Не переведено 5 для поиска пути логарифмической длины, если он существует, но эта техника даёт аппроксимационный коэффициент лишь <math>O(n/\log n)</math>Шаблон:Sfn.

Параметризованная сложность

Задача поиска самого длинного пути является Шаблон:Не переведено 5, если параметризовать её по длине пути. Например, задача может быть решена за время, линейно зависящее от размера входного графа (но за экспоненциальное время по длине пути), с помощью алгоритма, делающего следующие шаги:

  1. Осуществляем поиск в глубину по графу. Пусть <math>d</math> — глубина результирующего дерева поиска вглубь.
  2. Используем пути от корня к листам поиска дерева вглубь в порядке, в котором они просматриваются при поиске, в отличие от путевой декомпозиции графа с путевой шириной <math>d</math>.
  3. Используем динамическое программирование к этому разложению на пути для нахождения самого длинного пути за время <math>O(d!2^dn)</math>, где <math>n</math> — число вершин графа.

Поскольку выходной путь имеет длину по меньшей мере <math>d</math>, время работы также будет ограничено значением <math>O(\ell!2^\ell n)</math>, где <math>\ell</math> — длина самого длинного пути[2]. Используя цветовую кодировку, зависимость от длины пути может быть сведена к одиночно экспоненциальнойШаблон:SfnШаблон:SfnШаблон:Sfn. Похожая техника динамического программирования показывает, что задача нахождения самого длинного пути является также фиксированно-параметрически разрешимой по древесной ширине графа.

Для графов с ограниченной кликовой шириной задачу о самом длинном пути можно решить за полиномиальное время с помощью алгоритма динамического программирования. Однако степень полинома зависит от кликовой ширины графа, так что эти алгоритмы не являются фиксированно-параметрически разрешимыми. Задача нахождения самого длинного пути, параметризованная по ширине клик, является трудной для класса Шаблон:Не переведено 5 <math>W[1]</math>, что говорит о том, что вряд ли существует фиксированно-параметрически разрешимый алгоритмШаблон:Sfn.

Специальные случаи графов

Задачу о самом длинном пути можно решить за полиномиальное время на дополнениях графов сравнимости[3]. Её можно решить также за полиномиальное время на любом классе графов с ограниченной древесной шириной или ограниченной кликовой шириной, таком как дистанционно-наследуемые графы. Однако задача является NP-трудной, даже если ограничимся расщепляемыми графами, круговыми графами или планарными графамиШаблон:Sfn.

См. также

Примечания

Шаблон:Примечания

Литература

Шаблон:Refbegin

Шаблон:Refend

Ссылки

Шаблон:Rq

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ Шаблон:Harv. Для более ранних работ даже с более слабой аппроксимацией см. статьи Габова Шаблон:Harv и Бьёрклунда и Хасфелдта Шаблон:Harv.
  2. ↑ Шаблон:Harv. Для более раннего фиксированно-параметрически разрешимого алгоритма с чуть лучшей зависимостью от длины пути, но с худшей зависимостью от длины графа, см. статью Шаблон:Harv.
  3. ↑ Шаблон:Harv. Для более ранних работ на более ограниченных классах см. статьи Шаблон:Harv и Шаблон:Harv.
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Задача_о_самом_длинном_пути&oldid=9894478