Задача коммивояжера.

[sng1]

Относится ли частный случай задачи коммивояжера, когда матрица расстояний является (0;1)-матрицей и удовлетворяет аксиомам метрики, к классу NP-сложных задач.

[worm2]

Мысли вслух.

Рассмотрим произвольный неориентированный взвешенный граф, где все веса --- натуральные числа, удовлетворяющие аксиомам метрики. Известно, что задача для такого графа остаётся NP-трудной.

Теперь заменим в нём каждое ребро
A --------(вес=n)-------- B
на последовательность рёбер
A --(вес=0)-- X1 --(вес=1)-- X2 --(вес=0)-- X3 --(вес=1)-- X4 ............ X{2N-1} --(вес=1)-- X{2N} --(вес=0)-- B

Вроде бы, новый граф удовлетворяет аксиомам метрики.

Сначала думал, что задачи на исходном графе и на новом эквивалентны. Однако фигушки

К тому же, вторая задача размерностью поболе будет Скажется ли это на NP-трудности?

[sng1]

Может надо переместить сообщение в раздел математика?

[worm2]

Да нет, здесь, вроде, самое то...

[sng1]

worm2 в сообщении #240106 писал(а):

Рассмотрим произвольный неориентированный взвешенный граф, где все веса --- натуральные числа, удовлетворяющие аксиомам метрики. Известно, что задача для такого графа остаётся NP-трудной.

В этой NP-трудной задаче веса - натуральные числа, ограничены или растут с ростом размера матрицы?

[worm2]

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

[sng1]

А если веса (натуральные числа) ограничены, задача остается NP- трудной?

[worm2]

Не знаю. Эта задача ещё сложнее, чем исходная