РОЗДІЛ 2
ЕФЕКТИВНІ МЕТОДИ РОЗВ'ЯЗАННЯ ЗК ЗА СХЕМОЮ ПОБУДОВИ ЛОКАЛЬНИХ ОБХОДІВ
В розділі викладено метод побудови локальних послідовностей, адресований задачі комівояжера (ЗК) та її обмеженим версіям у вигляді поліноміальних алгоритмів знаходження задовільних за точністю розв'язків, а також його модифікацію. В запропонованих методах враховуються особливості ефективно розв'язуваних узагальнень задачі про призначення.
2.1. Метод локальних послідовностей
Нехай - матриця перестановки : , , ; у всіх інших випадках. Кожному елементу поставимо у взаємооднозначну відповідність елемент , визначивши тим самим підстановку
.
Всі підстановки даного ступеня розіб'ємо на два класи. До першого класу віднесемо всі циклічні підстановки
,
тобто такі, в цикловому розкладі яких є лише один цикл довжини , до другого - всі інші [55]. Перестановку, що відповідає циклічній підстановці, позначимо і назвемо циклічною перестановкою.
Нехай - квадратна матриця порядку , в якій
(2.1), - множина цілих невід'ємних чисел.
В матриці розглянемо діагональ , що відповідає довільній перестановці . Так як є перестановкою номерів стовпців матриці , то позначимо елемент діагоналі через .
По матриці побудуємо повний орієнтований мультиграф з вершинами, в якому кожна пара вершин , , з'єднана парою дуг і з вагами або вартостями і .
Зформулюємо ЗК.
В повному орієнтованому мультиграфі потрібно знайти контур з найменшою сумою ваг дуг, що входять до нього, такий що проходить через кожну вершину точно один раз.
Послідовність , що відповідає циклічній перестановці , назвемо обходом.
Допустимим розв'язком ЗК, очевидно, є обхід , що визначає в мультиграфі замкнений маршрут , в якому всі номери із множини є різними. Визначимо вартість обходу в :
.
По аналогії з постановкою задачі про призначення зформулюємо ЗК.
Потрібно знайти в матриці , елементи якої задовольняють умові (2.1), циклічну перестановку номерів стовпців з мінімальною сумарною вагою відповідного їй обходу
.
Якщо обмежити значення матриці умовою , то отримаємо симетричну ЗК. В цьому випадку матриці відповідає повний неорієнтований граф з вершинами, де ребро , , , має вагу .
Представляючи елементи матриці як відстані, слід вважати, що вони задовольняють нерівності трикутника:
(2.2)В цьому випадку кажуть, що ЗК обмежена на матриці, що задовольняє нерівності трикутника.
Таким чином, звуження області розв'язків задачі про призначення до підмножини всіх циклічних перестановок призводить до формулювання ЗК і до ключової відмінності цих задач, вираженій в непорівнянності оцінок складності побудови оптимальних розв'язків. Множина, в якій шукається оптимальний розв'язок задачі про призначення, складається з перестановок . Потужність множини , що містить шукану перестановку несиметричної ЗК, дорівнює , а потужність області розв'язків в симетричній задачі вдвічі менше, ніж . Разом з тим відомо, що задача про призначення ефективно розв'язувана за час , тоді як ЗК з нерівністю трикутника або без нього є NP-трудною в сильному розумінні.
Викладемо міркування, які є основою для розробки алгоритмів розв'язання ЗК методом побудови локальних оптимальних послідовностей.
Розглянемо дві строго зростаючі послідовності і , , одна з яких містить номери рядків , а інша - номери стовпців матриці . Якщо , , будемо говорити, що всі елементи , , , утворюють квадратну підматрицю порядку на головній діагоналі матриці . Надалі обмежимось тим, що розглянемо підматриці , в яких номери рядків та стовпців представлені послідовністю .
Розглянемо підматрицю на головній діагоналі матриці . Підматриця визначає єдину циклічну перестановку . Кількість всіх перестановок, що утворюються з підматриці , дорівнює 6, з яких дві перестановки та є циклічними. Перераховані перестановки формують множину всіх обходів в ЗК з матрицею вартостей : , .
Співставимо перестановці дводольний орієнтований граф , , . Нескладно побачити, що обидві перестановки та можна отримати із перестановки . Перестановка утворюється видаленням в графі дуги та доданням дуг , , і , , а перестановка - видаленням дуги та додаванням дуг , і , (рис. 2.1).
Рис. 2.1. Перехід до 2 перестановок розміру 3 від перестановки розміру 1
Це зауваження викликає наступне узагальнення.
Нехай підстановка ступеня
містить один цикл довжини та один цикл довжини 1, тобто представлена цикловим розкладенням , де
,
.
Тоді будь-яка з підстановок ступеня
, ,
, ,
складається з одного циклу довжини .
Дійсно, контур довжини , що відповідає підстановці , можна отримати із єдиним способом, а саме, видаленням в контурі, що відповідає підстановці , дуги та доданням дуг і , . Аналогічно, контур довжини , що відповідає підстановці , утворюється видаленням з контуру, що відповідає підстановці , дуги та доданням дуг і , .
Таким чином, ми маємо простий спосіб побудови підмножини циклічних перестановок довжини для матриці , який полягає у виконанні наступних дій. Із формуємо підматриць на головній діагоналі матриці . В кожній підматриці номери рядків та стовпців задаються однією послідовністю , . Далі для кожної циклічної перестановки довжини , отриманої з матриці , утворюються циклічних перестановок довжини за допомогою викладених дій по видаленню та доданню елементів матриці .
Такий спосіб формування множини допустимих розв'язків в підматрицях заданої матриці вартостей , , добре вбудовується в схему утворення локальних послідовностей, за допомогою якої виявилось можливим ефективно розв'язати декілька узагальнень задачі про призначення [49, 51]. Покажемо, як застосувати схему для побудови за поліноміальний час обходу , що є прийнятним за точністю, для реальних вхідних д