V.V. писал(а):
Имеется орграф, целочисленная матрица весов ребер. Требуется найти гамильтонов путь минимального веса.
Есть ли относительно быстрый алгоритм (например, быстрее метода ветвей и границ) для задач, в которых каждый элемент матрицы не больше числа M, равного O(n^2), где n - число вершин?
Задача коммивояжёра NP-полная даже в частном случае, когда рёбра имеют веса 1 или 2.
Таким образом, задача коммивояжёра является NP-полной в сильном смысле
(это можно прочитать у
Гэри и Джонсона).
Насколько я понял, с приближёнными алгоритмами решения ситуация тоже печальная.
С удовольствием бы почитал краткий отчёт о современных достижениях в этой области.
А. и Б. Стругацкие писал(а):
-- Г-голубчики, -- сказал Федор Симеонович озадаченно, разобравшись
в почерках. -- Это же п-проблема Бен Б-бецалеля. К-калиостро же доказал,
что она н-не имеет р-решения.
-- Мы сами знаем, что она не имеет решения, -- сказал Хунта,
немедленно ощетиниваясь. -- Мы хотим знать, как ее решать.
Главное - найти начальную и конечную точки этого пути. А остальное решит гамильтониан.