Найти максимальное вершинно-непересекающееся покрытие пути

Question

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

Мы хотим найти покрытие вершин, не связанное с вершиной, которое имеет максимальную сумму весов всех путей в этом покрытии.

Я знаю, что это проблема NP. Есть ли алгоритм, который решает эту проблему? Или есть проблемы, которые сводятся к этой проблеме?

Answer 1

Есть O(3^n poly(n))- алгоритм времени. Шаги

1. Найти все наборы вершин, которые могут быть расположены в пути.
2. Решите полученную проблему упаковки набора.

Шаг 1 выполняется динамической программой, таблица которой индексируется парами, состоящими из (a) набора вершин в пути (b) первой вершины в пути. Шаг 2 также выполняется динамической программой с таблицей, отображающей наборы вершин в максимальное значение, достижимое непересекающимися путями на этом подграфе.

Повторение шага 1

IsPath({v}, v) = true (for all vertices v)
IsPath(S, v) = exists w in S - {v} such that v->w is an arc and IsPath(S - {v}, w) (for all sets of vertices S, for all v in S).

Теперь соберите все множества P, для которых существует v в P, такое что IsPath(P, v). Вычислить оценку для каждого из этих путей.

BestCover({}) = 0
BestCover(S) = max Score(P) + BestCover(S - P) over all P subset of S such that P is a path (for all nonempty S).