ЕКСПЕРИМЕНТАЛЬНЕ ДОСЛІДЖЕННЯ ТОЧНОГО МЕТОДУ ЗАГАЛЬНОЙ ЗАДАЧІ КОМІВОЯЖЕРА ІЗ ДЕКОМПОЗИЦІЄЮ

Abstract

Проведено експериментальне дослідження точного методу розв’язання загальної задачі комівояжера (ЗЗК) із декомпозицією вхідного графа на блоки. Показано зменшення часу роботи методу залежно від кількості блоків. ЗЗК великої розмірності можуть бути розбиті на підзадачі меншої розмірності, що відповідають блокам у графах. Цій підхід дозволяє знизити вимоги до обчислювальних засобів, виконувати підзадачи паралельно, що призведе до виграшу в часі виконання. Вартості обходів комівояжера для мостів та лісу дерев є константами. Знайдені у блоках маршрути об’єднуються в єдиний маршрут за поліноміальний час. Декомпозиція ЗЗК суттєво стримує зріст часу розв’язання, залежно від розмірності вхідного графа, та кількості блоків у ньому, але складність ЗЗК залишається експоненціальною. Якщо граф не містить блоків, час роботи методу не відрізняється від класичного варіанта алгоритму Літла, за виключенням поліноміального часу, що витрачено на пошук можливостей декомпозиції. Досліджено частоту з’явлення блоків, суттєвих для декомпозиції ЗЗК, тобто: ліса, мостів, точок зчленування. Той факт, що існують випадки, коли сам граф є блоком, не враховувався.