Euclidean TSP известен как NP-полный.Путешественник со специальной метрикой
В моей специальной метрике, расстояние между А и В, определяется как:
max(x coordinate of A , y coordinate of B);max(x coordinate of B , y coordinate of A).Это еще NP-полный?
Да. Расчет функции затрат не является тем, что делает TSP NP-полным.
Разница между вашей формулировкой и стандартным TSP заключается в том, что стоимость отличается в зависимости от направления, в котором вы путешествуете. Это стоимость (i, j)! = Cost (j, i). Затраты обычно представляются в виде матрицы для легкого поиска, а симметрия позволяет вдвое уменьшить размер матрицы затрат. Ваша формулировка требует, чтобы матрица была полностью заполнена. Генерация стоимостной матрицы все еще только O (n^2).
Для получения точного ответа вам все равно придется направить свой ответ (с количеством возможностей == количество перестановок «городов» O (n!)) Или использовать фантастический алгоритм, как SAT-решатель.
Спасибо! Но, чтобы доказать свою np-полноту, нам нужно уменьшить из другой np-полной задачи. Я думаю, что «стоимость отличается в зависимости от направления» не единственная разница. – Cong
Предположим, у вас есть алгоритм для решения асимметричного TSP. Во-первых, обратите внимание, что он находится в NP. Ясно, что он также решает любой экземпляр евклидова TSP. Так как Euclidan TSP NP-полный (и, следовательно, NP жесткий), асимметричный TSP тоже NP-жесткий. Таким образом, асимметричный TSP является NP-полным. – Reinhard
У вас есть дополнительная информация об использовании SAT-решателя для метрики TSP? – Inuart
Это домашнее задание? – raoulcousins
Нет, просто интересная проблема. – Cong