Я знаю, что для неориентированного графа эта проблема является NP-полной, поэтому мы должны использовать грубую силу, чтобы проверить все возможные пути. Как мы можем это сделать? Пожалуйста, предложите псевдокод и расскажите мне о сложности этого алгоритма.
Если есть оптимизации, то это было бы здорово!
Наивный подход мог бы перебрать все возможные перестановки вершин.
Для каждой перестановки {v1, ..., vN} вы проверяете, можете ли вы перейти от v1 к v2, затем от v2 к v3 и т. Д. Если можете, добавьте соответствующую длину ребра к текущей длине пути. Если нет, переходите к следующей перестановке.
Самый длинный из таких путей - ваш ответ.
Или вы можете сделать то же самое, используя рекурсию.
path = 0
bestPath = 0
used = new bool[N] // initialize with falses
for(u = 0; u < N; u++)
Path(u); // build paths starting from u
print bestPath
где
Path(u)
used[u] = true
foreach v in neighborhood(u)
if(!used[v])
path += distance(u, v)
bestPath = max(bestPath, path)
Path(v)
path -= distance(u, v)
used[u] = false
Сложность времени ужасна O(N * N^N).
R мы можем построить дерево, где R - корень, а количество уровней в дереве (меньше или) равно количеству вершин в нашем графе. Тогда каждому листу соответствует свой путь, и нам нужно найти самый дальний.
- person AlexD; 19.02.2014
Если ваш график является особым случаем, когда он направлен и ацикличен, вы можете применить подход динамического программирования, такой как описанный здесь. Вы в основном сортируете свой граф топологически, затем в топологическом порядке для каждого узла V вы проверяете всех его соседей и обновляете их значение «расстояния», если оно больше, чем «расстояние», уже запомненное (инициализированное с помощью -infinity или что-то в этом роде).
В противном случае в общем случае задача действительно NP-полная, поскольку сводится к гамильтонову циклу. Единственное, что вы могли бы сделать, - это свести на нет все грани и попробовать алгоритм Беллмана-Форда. Однако помните, что это не хорошо для отрицательных циклов.
