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

Question

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

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

Answer 1

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

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

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

Answer 2

альтернативный текст http://dl.getdropbox.com/u/317805/path2.jpg

График, приведенный выше, преобразуется в нижний с использованием вашего алгоритма.

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

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

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