Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия, Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки
Народ, кто знает: найдено ли решение задачи коммивояжера (объезд N городов с по одному разу с минимизацией длины пути) за время лучше N- факториал ? Или доказано отсутствие такого алгоритма ? Или проблема остается нерешенной ?
Xaositect
Re: Задача комивояжера
28.11.2010, 20:13
лучше . Эта сложность достигается с помощью динамического программирования. См. напр. обзор M. Bellmore and G. L. Nemhauser, The Traveling Salesman Problem: A Survey.
zinka
Re: Задача комивояжера
29.11.2010, 11:09
Спасибо. Но это тоже очень много. Я надеялась на полином. А доказано, что полинома нет ?
Нет, коммивояжер - это NPO-полная задача. Для метрического случая (выполняется неравенство треугольника) есть приближенные алгоритмы, ошибающиеся не более чем в константу раз (алгоритм Кристофидеса).
iig
Re: Задача комивояжера
10.12.2010, 23:13
Спасибо модеру. направил меня именно по теме, только не знаю, может для самолюбия завести свою близкую тему, чтобы отличаться?