Оптимальный путь в графе с весами узлов и ребер
Рассмотрим следующий ориентированный граф с весами узлов и ребер.
Существует ли не NP-жесткий алгоритм для нахождения пути с максимальным количеством очков, где
score = sum(node weights) - sum(edge weights)
Для графа примера путь с максимальным результатом проходит по пути A -> B -> C -> D. Максимальный результат равен 164 ((77 + 27 + 32 + 84) - (44 + 12 + 0)).
@ShridharRKulkarni, как это может работать в этом сценарии?
Хотя верно то, что сложность DFS во время выполнения составляет O (V + E), если вы хотите перебрать все возможные пути с использованием DFS, сложность является факториальной.
Просто для уточнения: цикл (B, C, D) имеет оценку (27 + 32 + 84) - (89 + 12 + 0) > 0, поэтому можно произвольно увеличивать оценку, проходя этот цикл. Вы ищете только простые пути?
Ответы 1
Я думаю, что не существует алгоритма, который может найти решение за полиномиальное время, я пытаюсь доказать, что эта задача является NP-сложной, потому что мы можем свести ее к задача о самом длинном пути, а задачу о самом длинном пути можно свести к вашей задаче.
Вот моя попытка (я предполагаю, что веса ребер и узлов положительны):
- Сведение от этой задачи к задаче о самом длинном пути:
Эту задачу можно свести к задаче о самом длинном пути, разделив каждый узел A на два узла A-IN и A-OUT, так что эти узлы не имеют весов, мы связываем входящие ребра к A в A-IN, а исходящие ребра от A до A-OUT и добавить ребро между A-IN и A-OUT с весом, равным -1, умноженному на исходный вес узла A. Теперь, чтобы найти решение задачи, вам нужно найти самый длинный путь в этом графе.
- Сведение от задачи о самом длинном пути к этой задаче (и тут я не уверен, что не сделал ошибок):
Задача о самом длинном пути может быть сведена к этой задаче, если взять каждое ребро с отрицательным весом E между двумя узлами A и B и создать в его середине виртуальный узел AB. Мы удалим E из графа, а затем добавим ребро от A к AB с вес 0 и ребро из AB в B с весом 0, и придать узлу AB вес, равный -1 умноженному на вес исходного E.
Так что, надеюсь, это было доказательством того, что вы можете решить задачу о самом длинном пути, сведя ее к вашей задаче, поэтому, если существует решение вашей задачи за полиномиальное время, то P = NP.
Это хороший ответ, но кажется, что его можно упростить. Чтобы показать, что проблема решения является NP-полной: во-первых, она находится в NP, потому что мы можем проверить вес решения-кандидата за линейное время. Чтобы сократить самый длинный путь (который обычно задается с использованием только весов ребер) к этой проблеме: инвертируйте все веса ребер, установите все веса узлов равными 0.
@ShridharRKulkarni Я думаю, что любая реализация DFS будет как минимум O (N!). Я ищу что-то полиномиальной сложности.