Управляющие системы и машины, №5, 2018, статья 1
DOI: https://doi.org/10.15407/usim.2018.05.003
Тимофієва Н.К. Про деякі властивості множини розв’язків задачі комівояжера. Управляющие системы и машины. 2018. № 5. C. 3-12.
УДК 519.816
Тимофеева Надежда Константиновна, д.т.н., вед.н.с., Международный научно-учебный центр информационных технологий и систем НАН и МОН Украины, просп. Глушкова, 40, Киев 03187, Украина, E-mail: tymnad@gmail.com
О некоторых свойствах множества решений задачи коммивояжера
Введение. Для задачи коммивояжера описывается способ упорядочения маршрутов (соответственно и перестановок) подмножествами, который не зависит от структуры входных данных определенной задачи. Для полученного упорядочения разработана стратегия определения тех подмножеств, которые содержат глобальное решение.
Постановка задачи. Известные методы нахождения оптимального решения в задачах комбинаторной оптимизации заключаются в разработке стратегии отсечения неэффективных решений и в установлении зависимости значения целевой функции от входных данных, которые носят случайный характер. Как показывает их анализ, в процессе работы этих подходов возникает одна и та же проблема, а именно: разработка стратегии разбиения множества значений целевой функции на подмножества с последующим исключением тех подмножеств, которые не содержат оптимального решения.
Предлагаемый подход. В данной статье разработана стратегия отсечения неэффективных решений, которая заключается не в разбиении множества значений целевой функции на подмножества, а в разбиении множества маршрутов задачи коммивояжера независимо от входной информации. Показано, что в зависимости от различных комбинаций элементов матрицы, которой задаются входные данные, множество маршрутов в задачи коммивояжера разделяется на одни и те же подмножества для различных индивидуальных задач с различной структурой входных данных. Соответственно, аналогичными подмножествами упорядочивается и множество перестановок. Маршруты, для которых целевая функция принимает или наибольшее или наименьшее значения могут находиться в разных таких подмножествах. Они могут содержать элементы матрицы, выбранные из разных ее ячеек, то есть не пересекаться. Приведен ряд теорем, которые доказывают, что использование этого свойства позволяет сужать область поиска оптимального решения. На подклассах разрешимых задач показано, как меняется нахождение глобального результата в зависимости от структуры входной информации. В зависимости от входных данных глобальные минимум и максимум могут принадлежать разным подмножествам. Доказано что для подобных структур глобальные минимум и максимум для задачи коммивояжера находятся в одних и тех же подмножествах.
Заключение. Изучение закономерности изменения значений целевой функции от различных структур входных данных позволяет разрабатывать стратегии поиска одних и тех же подмножеств, содержащих глобальное решение для подобных структур. При разработке алгоритмов на основе метода «ближайшего города» (или «жадным алгоритмом») необходимо проводить поиск оптимальных решений по всем подмножествах, поскольку этими подходами можно найти результат, который далек от оптимального.
Загрузить полный текст в PDF (на украинском).
Ключевые слова: Комбинаторная оптимизация, комбинаторная конфигурация, целевая функция, задача коммивояжера, упорядочение комбинаторных конфигураций подмножествами.
Поступила 12.11.18
