“Скупой” метод решения задачи коммивояжера

[CherkasovMY]

Цитата:

«Коммивояжер — наиболее знаменитая задача комбинаторной оптимизации, которая долгое время притягивала внимание, стимулировала исследования и вызывала некие «глубинные ощущения». Так или иначе казалось, что ее решение обеспечит фундаментальный прорыв в широком диапазоне дискретного анализа» [Босс В. Лекции по математике. Т. 10: Перебор и эффективные алгоритмы. 2008, с. 21].

В качестве основы поиска решения можно использовать “скупой” метод: если для $n$ городов известен оптимальный путь, то $(n+1)$-й город добавлять так, чтобы прирост пути был наименьшим. Тогда, взяв в качестве “затравки” несколько городов, остальные добавлять таким способом. Но не любой набор городов годится для “затравки”, необходимо соблюдать одно обязательное условие: их последовательность должна быть той же, что в оптимальном пути. Таким образом, получается замкнутый круг: для выбора городов необходимо знать их расположение в оптимальном пути, для нахождения которого уже надо знать их последовательность.
В некоторых случаях такого порочного круга нет. В задаче коммивояжера с евклидовой метрикой (в качестве городов выступают точки на плоскости) таким свойством однозначно обладают точки, являющиеся вершинами выпуклой оболочки, т.к. оптимальный путь не может иметь самопересечений.
Следует отметить и тот факт, что подобным свойством обладают любые три города. Но и на их выбор накладываются определенные ограничения: одним из необходимых условий является то, что любые два из них не должны быть соседними в оптимальном варианте. Хотя, это условие можно использовать в качестве критерия проверки какого-либо варианта. Например, для решения задачи в общем виде, можно, в качестве "затравки", перебрать все варианты "троек"-городов. Таких вариантов будет порядка $O(n^3)$ (число сочетаний из $n$ по $3$). Сложность решения одного варианта равна $O(n^2)$. Значит, общая сложность решения задачи коммивояжера в общем виде будет $O(n^5)$. Таким образом, этот полиномиальный алгоритм решения задачи коммивояжера ставит под сомнение гипотезу Кука.

[Mikhail_K]

А в чём вопрос-то?

[Deggial]

Тема перемещена из форума «Дискуссионные темы (М)» в форум «Карантин»
Причина переноса: тема не оформлена в соответствии с правилами дискуссионного раздела

CherkasovMY, капслок в заголовках тем запрещён.
Наберите все формулы и термы $\TeX$ом. Инструкции по оформлению формул здесь или здесь (или в этом видеоролике).
Изложите всё, что нужно для обсуждения в теме, ссылки (даже на книги) должны быть необязательны для понимания существа темы. В частности, если Вы приводите примеры или опираетесь на них - выпишите их прямо в теме. Не должен каждый читатель лазить в книгу для прочтения примера, который автор может один раз выписать в тексте.
Сформулируйте явно предмет обсуждения. Помните, что все понятия и должны быть строго определены, а утверждения - доказаны.

CherkasovMY в сообщении #1235377 писал(а):

Существенным недостатком, является то, что в некоторых случаях “скупой” метод дает сбой.

И сразу вердикт: если Вы придумали ещё один жадный алгоритм решения ЗК, то в принципе здесь ничего сильно интересного нет.

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