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

[zinka]

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

[Xaositect]

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

[zinka]

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

[Xaositect]

zinka в сообщCMU Tech. Report CS-93-13ении #381631 писал(а):

А доказано, что полинома нет ?

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

[iig]

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