Как я могу проверить решение проблемы коммивояжера за полиномиальное время?

31

Таким образом, TSP (задача коммивояжера) проблема решения является NP полной .

Но я не понимаю, как я могу проверить, что данное решение TSP на самом деле является оптимальным за полиномиальное время, учитывая, что нет способа найти оптимальное решение за полиномиальное время (потому что проблема не в P)?

Что-нибудь, что могло бы помочь мне понять, что проверка на самом деле может быть сделана за полиномиальное время?

Lazer
источник

Ответы:

20

Чтобы быть более точным, мы не знаем, находится ли TSP в . Вполне возможно, что это можно решить за полиномиальное время, хотя, возможно, распространено мнение, что . Теперь вспомните, что значит для проблемы быть -hard и -complete, см., Например, мой ответ здесь . Я полагаю, что ваш источник путаницы проистекает из определений: проблема -hard не обязательно находится в .PN P N P N PPPNPNPNPН ПNPNP

Как и на странице Википедии вы связываете государства, то проблема решения является -полное: учитывая затраты и целое число , решить , есть ли тур дешевле , чем . Один из способов увидеть проблему в - увидеть, что при заданном решении легко за полиномиальное время проверить, дешевле ли решение, чем . Как ты можешь это сделать? Просто следуйте приведенному туру, запишите его общую стоимость и, наконец, сравните общую стоимость с .х х Н П х хNPxxNPxx

Юхо
источник
«Просто следуйте приведенному туру, запишите его общую стоимость и, наконец, сравните общую стоимость с x». -> Да, но есть экспоненциальное количество туров, чтобы проверить!
Лазер
2
Кажется, я был слишком медленным. ;-)
Ниль де Боудрап,
3
@ Лазер Нет, есть только один тур, чтобы проверить. Вам дают тур, и вы записываете его продолжительность. Если оно меньше , выведите yes , в противном случае no . x
Юхо
«решить, есть ли тур», это определенно означает, что нам не дают тур. Что мне не хватает?
Лазер
3
@Lazer Нет, в задаче вы получили взвешенный график и целевую стоимость. Сертификат тур. Для альтернативного объяснения см. Ответ Ниль. Как и в примере с Wiki в случае SUBSET-SUM, нам не дают ноль, а вместо этого нам дают конкретное подмножество в качестве сертификата.
Юхо
34

Суть в том, что нужно учитывать решение проблемы:

Задача коммивояжера (вариант решения). Учитывая взвешенный граф G и целевую стоимость C , существует ли гамильтонов цикл в G , вес которого не больше C ?

Для экземпляра «да», сертификат лишь некоторые гамильтонов цикл, вес которого составляет не более C . Если бы вы могли эффективно решить эту проблему, вы могли бы найти стоимость минимального тура с помощью бинарного поиска, начиная с веса всей сети в качестве верхней границы.

Ниль де Бодрап
источник
3

Вы, вероятно, думаете о проблеме определения того, является ли данное решение TSP лучшим решением. Однако для этого не существует известного полиномиального решения, что означает, что эта проблема находится в NP-трудной, но не обязательно NP-полной.

Задача принятия решения TSP на самом деле заключается в определении того, является ли вес любого решения на графике Gмаксимально затратным C(как лучше объяснено в ответе Нила), что, безусловно, можно проверить за полиномиальное время.

Кейси Кубалл
источник
5
O(n!)n!
n0<=n1<=...
4
Нет, вы можете получить оптимальный результат, даже не вычисляя длительность всех других туров. И да, можно доказать, что это на самом деле оптимально, не вычисляя все остальные туры. Для примера рассмотрим ветку & границ.
Юхо
7
O(n22n)
@ Хорошо, хорошо. Я обновил ответ, чтобы больше не указывать грубую силу в качестве единственного варианта (только то, что полиномиальных решений нет).
Кейси Кубалл