2014 dxdy logo

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

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




 
 Задача комивояжера
Сообщение28.11.2010, 19:55 
Аватара пользователя
Народ, кто знает: найдено ли решение задачи коммивояжера (объезд N городов с по одному разу с минимизацией длины пути) за время лучше N- факториал ?
Или доказано отсутствие такого алгоритма ?
Или проблема остается нерешенной ?

 
 
 
 Re: Задача комивояжера
Сообщение28.11.2010, 20:13 
Аватара пользователя
$O(n^2 2^n)$ лучше $n!$.
Эта сложность достигается с помощью динамического программирования. См. напр. обзор M. Bellmore and G. L. Nemhauser, The Traveling Salesman Problem: A Survey.

 
 
 
 Re: Задача комивояжера
Сообщение29.11.2010, 11:09 
Аватара пользователя
Спасибо.
Но это тоже очень много.
Я надеялась на полином.
А доказано, что полинома нет ?

 
 
 
 Re: Задача комивояжера
Сообщение29.11.2010, 12:05 
Аватара пользователя
А доказано, что полинома нет ?
Нет, коммивояжер - это NPO-полная задача.
Для метрического случая (выполняется неравенство треугольника) есть приближенные алгоритмы, ошибающиеся не более чем в константу раз (алгоритм Кристофидеса).

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

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


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