2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Задача комивояжера
Сообщение28.11.2010, 19:55 
Аватара пользователя


11/07/09
112
Народ, кто знает: найдено ли решение задачи коммивояжера (объезд N городов с по одному разу с минимизацией длины пути) за время лучше N- факториал ?
Или доказано отсутствие такого алгоритма ?
Или проблема остается нерешенной ?

 Профиль  
                  
 
 Re: Задача комивояжера
Сообщение28.11.2010, 20:13 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Задача комивояжера
Сообщение29.11.2010, 11:09 
Аватара пользователя


11/07/09
112
Спасибо.
Но это тоже очень много.
Я надеялась на полином.
А доказано, что полинома нет ?

 Профиль  
                  
 
 Re: Задача комивояжера
Сообщение29.11.2010, 12:05 
Заслуженный участник
Аватара пользователя


06/10/08
6422
А доказано, что полинома нет ?
Нет, коммивояжер - это NPO-полная задача.
Для метрического случая (выполняется неравенство треугольника) есть приближенные алгоритмы, ошибающиеся не более чем в константу раз (алгоритм Кристофидеса).

 Профиль  
                  
 
 Re: Задача комивояжера
Сообщение10.12.2010, 23:13 
Заблокирован
Аватара пользователя


03/05/09

288
Gomel BY
Спасибо модеру. направил меня именно по теме, только не знаю, может для самолюбия завести свою близкую тему, чтобы отличаться?

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 5 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group