Самый длинный простой путь

Question

Итак, я понимаю, что проблема поиска самого длинного простого пути на графике NP-hard, так как тогда вы могли бы легко решить проблему с гамильтоновой схемой, установив весы на 1 и посмотрев, если длина самого длинного простой путь равен числу ребер.

Мой вопрос: Какой путь вы получите, если вы взяли график, нашел максимальный вес края, m, заменить каждый вес края w с m - w и побежал стандартный алгоритм кратчайшего пути по этому поводу? Это явно не самый длинный простой путь, так как если бы это было так, то NP = P, и я думаю, что доказательство чего-то подобного было бы немного сложнее = P.

Answer 1

alt text http://dl.getdropbox.com/u/317805/path2.jpg

Диаграмма выше преобразуется ниже с помощью алгоритма.

Самый длинный путь - это красная линия на приведенном выше графике. И в зависимости от того, как связь сломана и используется алгоритм, кратчайшим путем в преобразованном графе может быть синяя линия или красная линия. Поэтому преобразование весов граней графа с использованием константы, о которой вы говорили, не дает значимых результатов. Вот почему вы не можете найти самый длинный путь, используя алгоритмы кратчайшего пути, какими бы умными вы ни были. Более простым преобразованием могло бы быть отрицание всех весов ребер и запуск алгоритма. Я не знаю, ответил ли я на ваш вопрос, но поскольку свойство path переходит в преобразованный граф, у него нет никакой полезной информации относительно расстояния.

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

• Редактировать: Мне сказали добавить это утверждение: приведенный выше график касается не только физического расстояния. Им не нужно придерживаться неравенства треугольника. Благодарю.

Answer 2

Если бы вы могли решить проблемы кратчайших путей с отрицательными весами вы найдете самый длинный путь, два эквивалентны, это можно сделать, поставив вес -w вместо ш

Стандартный алгоритм для отрицательных весов является алгоритмом Bellman-Ford. Однако алгоритм не будет работать, если на графике есть цикл, так что сумма ребер отрицательна. На графике, который вы создаете, все такие циклы имеют отрицательные весовые коэффициенты и поэтому алгоритм не будет работать. Если, конечно, у вас нет циклов, в этом случае у вас есть дерево (или лес), и проблема разрешима с помощью динамического программирования.

Если мы заменим вес w на m-w, что гарантирует, что все веса будут положительными, то кратчайший путь можно найти по стандартным алгоритмам. Если кратчайший путь P на этом графе имеет k ребер, то длина k * m-w (P), где w (P) - длина пути с исходными весами. Однако этот путь не обязательно является самым длинным из всех путей с k ребрами, P является самым длинным.