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

Анотація

У статті розглянуто варіант підвищення ефективності вирішення задачі комівоя-жера з застосуванням розширеної оцінки гілок в методі гілок і меж. Алгоритм для оцінки «перспек-тивності» деякої аij гілки оперує вартістю гілок, що виходять з вузла i та гілок, що входять у вузол j. Алгоритм розглядає гілки нульової довжини, і вибирає гілку, при заміні якої на нескінченність, мож-на відняти найбільше число з рядка і стовпця, відповідних даної гілки. Оцінку гілки можна розшири-ти, з огляду на більшу кількість елементів матриці вартостей, а саме гілки що входять в вузол i, і гілки, що виходять з вузла j, тобто j-тий рядок і i-тий стовпець і збільшити, таким чином, в два рази число аналізованих елементів матриці. Запропонована розширена оцінка дозволяє збільшити ефективність алгоритму.
У роботі при дослідженні алгоритмів використовувалася мова програмування C#. Ефективність алгоритму зростає при збільшенні розмірності задачі. Наведено результати вирішення тестових завдань. Чисельний експеримент показав, що для задач з числом міст більше 300 кожне рішення при використанні розширеної оцінки виявляється краще, ніж при використанні класичного алгоритму, ймовірність отримання поліпшеного рішення наближається до 100 %. Можна припустити, що по-дальше розширення оцінки призведе до більшого підвищення ефективності алгоритму. Таким чином, програма, яка використовує алгоритм гілок і меж, помітно підвищує ймовірність отримання кращо-го рішення для випадкової завдання за рахунок використання розширеної оцінки.