Управляющие системы и машины, №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
