Гамильтонов путь

[V.V.]

Имеется орграф, целочисленная матрица весов ребер. Требуется найти гамильтонов путь минимального веса.

Есть ли относительно быстрый алгоритм (например, быстрее метода ветвей и границ) для задач, в которых каждый элемент матрицы не больше числа M, равного O(n^2), где n - число вершин?

Вообще, интересует ссылка на литературу про алгоритмы решения задачи коммивояжера с дополнительными ограничениями.

[Vinni-Pooh]

Быстрее только принцип Мопертюи Главное - найти начальную и конечную точки этого пути. А остальное решит гамильтониан.

Цитата:

Требуется найти гамильтонов путь минимального веса.

Хотелось бы спросить, допускаете ли вы что гамильтонов путь имеет какой-нибудь вес? Это что-то намекает на теорию тяготения.

[Егор]

V.V. писал(а):

Имеется орграф, целочисленная матрица весов ребер. Требуется найти гамильтонов путь минимального веса.

Есть ли относительно быстрый алгоритм (например, быстрее метода ветвей и границ) для задач, в которых каждый элемент матрицы не больше числа M, равного O(n^2), где n - число вершин?

Задача коммивояжёра NP-полная даже в частном случае, когда рёбра имеют веса 1 или 2.
Таким образом, задача коммивояжёра является NP-полной в сильном смысле
(это можно прочитать у Гэри и Джонсона).
Насколько я понял, с приближёнными алгоритмами решения ситуация тоже печальная.
С удовольствием бы почитал краткий отчёт о современных достижениях в этой области.

А. и Б. Стругацкие писал(а):

-- Г-голубчики, -- сказал Федор Симеонович озадаченно, разобравшись
в почерках. -- Это же п-проблема Бен Б-бецалеля. К-калиостро же доказал,
что она н-не имеет р-решения.
-- Мы сами знаем, что она не имеет решения, -- сказал Хунта,
немедленно ощетиниваясь. -- Мы хотим знать, как ее решать.