Находит ли простой путь в взвешенном неориентированном графе с максимальной стоимостью за полиномиальное время?Это NP?

Question

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

Я имею в виду найти НАИБОЛЕЕ дорогой путь из всех для любой пары вершин.

Вход: график G = (V, E)

Выход: стоимостьСамый дорогой путь в графе G.

Является ли эта проблема NP-Complete? Я думаю, что это так.Не могли бы вы дать ссылку на статью, где я могу ее просмотреть.

Answer 1

Вы не первый, кто задумывается об этой проблеме. Фактически это была первая ссылка в результатах поиска Google.

редактировать
Ребята, невзвешенный граф является частным случаем взвешенного графа: все ребра имеют вес 1:)

Answer 2

Да, это проблема NP, потому что вы запрашиваете максимум , что означает, что вам нужно пройти все возможные пути.Версия решения этой проблемы («есть ли длина длины n ?») Известна как NP-полная (как отмечено выше).

Answer 3

Это похоже на коммивояжера, за исключением того, что ваш эвристик - Макс, а не Мин. Читайте о коммивояжере.

Проблема в том, что NP завершена, поскольку она может быть получена из задачи, которая уже доказала, что она NP-Complete (коммивояжер). Ответ проверяется за полиномиальное время, но ответ не может быть найден за полиномиальное время.

Чтение http://en.wikipedia.org/wiki/Travelling_salesman_problem