2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

 
 
 
 Re: Задача коммивояжера.
Сообщение03.09.2009, 13:23 
Аватара пользователя
Мысли вслух.

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

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

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

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

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

 
 
 
 Re: Задача коммивояжера.
Сообщение11.09.2009, 15:10 
Может надо переместить сообщение в раздел математика?

 
 
 
 Re: Задача коммивояжера.
Сообщение11.09.2009, 17:02 
Аватара пользователя
Да нет, здесь, вроде, самое то...

 
 
 
 Re: Задача коммивояжера.
Сообщение11.09.2009, 17:56 
worm2 в сообщении #240106 писал(а):

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



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

 
 
 
 Re: Задача коммивояжера.
Сообщение11.09.2009, 18:32 
Аватара пользователя
В этой конкретно задаче я подразумевал, что веса совершенно произвольные.

 
 
 
 Re: Задача коммивояжера.
Сообщение11.09.2009, 19:01 
А если веса (натуральные числа) ограничены, задача остается NP- трудной?

 
 
 
 Re: Задача коммивояжера.
Сообщение12.09.2009, 17:13 
Аватара пользователя
Не знаю. Эта задача ещё сложнее, чем исходная :D

 
 
 [ Сообщений: 8 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group