«КОММИВОЯЖЕР – наиболее знаменитая задача комбинаторной оптимизации, которая долгое время притягивала внимание, стимулировала исследования и вызывала некие «глубинные ощущения». Так или иначе казалось, что ее решение обеспечит фундаментальный прорыв в широком диапазоне дискретного анализа» [1, с. 21].
В качестве основы поиска решения можно использовать «скупой» метод: если для n городов известен оптимальный путь, то (n + 1)-й город добавлять так, чтобы прирост пути был наименьшим. Тогда, взяв в качестве «затравки» несколько городов, остальные добавлять таким методом. Но не любой набор городов годится для «затравки», необходимо соблюдать одно обязательное условие: их последовательность должна быть той же, что в оптимальном пути. Таким образом, получается замкнутый круг: для выбора городов необходимо знать их расположение в оптимальном пути, для нахождения которого уже надо знать их последовательность.
В некоторых случаях такого порочного круга нет. В задаче КОММИВОЯЖЕР с евклидовой метрикой (в качестве городов выступают точки на плоскости) таким свойством однозначно обладают точки, являющиеся вершинами выпуклой оболочки, т.к. оптимальный путь не может иметь самопересечений.
Эффективность предлагаемой методики можно проверить на уже решенных примерах. Например, достаточно пары минут для обнаружения ошибки в решении примера для 10 точек, рассмотренного в работе [2, с. 427]. Чтобы убедиться в правильности решения примера, приведенного в работе [3, с. 281], достаточно иметь линейку с делениями, ручку и два-три часа свободного времени.
Следует отметить и тот факт, что подобным свойством обладают любые три города. Но и на их выбор накладываются определенные ограничения: одним из необходимых условий является то, что любые два из них не должны быть соседними в оптимальном варианте.
Существенным недостатком, является то, что в некоторых случаях «скупой» метод дает сбой.
Библиографическая ссылка
Черкасов М.Ю. «СКУПОЙ» МЕТОД РЕШЕНИЯ ЗАДАЧИ КОММИВОЯЖЕР // Международный журнал прикладных и фундаментальных исследований. – 2016. – № 7-1. – С. 131-132;URL: https://applied-research.ru/ru/article/view?id=9781 (дата обращения: 19.04.2024).