ЕКСПЕРИМЕНТАЛЬНЕ ДОСЛІДЖЕННЯ НАБЛИЖЕНОГО МЕТОДУ РОЗВ’ЯЗАННЯ ЗАГАЛЬНОЇ ЗАДАЧІ КОМІВОЯЖЕРА

Автор(и)

  • Антон Юрійович Левченко Житомирський державний технологічний університет, Україна

DOI:

https://doi.org/10.26642/tn-2015-4(75)-101-105

Ключові слова:

загальна задача комівояжера, наближений метод

Анотація

Проведено експериментальне дослідження властивостей наближеного методу розв’язання загальної задачі комівояжера (ЗЗК) на вхідних даних великого розміру та його порівняння із відомими евристичними й наближеними алгоритмами. Наближений метод виконується у дві стадії. На першій стадії ЗЗК поліноміально зводиться до симетричної задачі комівояжера (СЗК). На другій стадії виконується поліноміальний наближений алгоритм СЗК, результат роботи якого перетворюється у наближений розв’язок ЗЗК. Експериментальна оцінка вартості наближених розв’язків досить складна у зв’язку з експоненціальною природою задачі комівояжера: важко знайти оптимум для вхідних даних великого розміру. За еталонні розв’язки використовувались деякі екземпляри з бібліотеки TSPLIB. На всій множині використаних вхідних даних відхилення вартості від оптимуму наближеного методу ЗЗК краща, ніж доведена аналітична оцінка. Можлива оптимізація реалізації наближеного метода ЗЗК з використання пам’яті, що дозволить розв’язувати задачі більшої розмірності в умовах обмежених обчислювальних ресурсів.

##submission.downloads##

Опубліковано

2016-06-01

Як цитувати

Левченко, А. Ю. (2016). ЕКСПЕРИМЕНТАЛЬНЕ ДОСЛІДЖЕННЯ НАБЛИЖЕНОГО МЕТОДУ РОЗВ’ЯЗАННЯ ЗАГАЛЬНОЇ ЗАДАЧІ КОМІВОЯЖЕРА. Вісник ЖДТУ. Серія "Технічні науки", (4(75), 101–105. https://doi.org/10.26642/tn-2015-4(75)-101-105

Номер

Розділ

Інформатика