Please use this identifier to cite or link to this item:
http://eztuir.ztu.edu.ua/123456789/4302
Title: | ЕКСПЕРИМЕНТАЛЬНЕ ДОСЛІДЖЕННЯ НАБЛИЖЕНОГО МЕТОДУ РОЗВ’ЯЗАННЯ ЗАГАЛЬНОЇ ЗАДАЧІ КОМІВОЯЖЕРА |
Other Titles: | Experimental research of an approximate method of common problem solution of travelling salesman |
Authors: | Левченко, Антон Юрійович Levchenko, A.Yu. |
Keywords: | загальна задача комівояжера наближений метод сommon travelling salesman problem approximate method |
Issue Date: | 2015 |
Publisher: | ЖДТУ |
Series/Report no.: | Вісник ЖДТУ. Серія : Технічні науки;4(75) |
Abstract: | Проведено експериментальне дослідження властивостей наближеного методу розв’язання загальної задачі комівояжера (ЗЗК) на вхідних даних великого розміру та його порівняння із відомими евристичними й наближеними алгоритмами. Наближений метод виконується у дві стадії. На першій стадії ЗЗК поліноміально зводиться до симетричної задачі комівояжера (СЗК). На другій стадії виконується поліноміальний наближений алгоритм СЗК, результат роботи якого перетворюється у наближений розв’язок ЗЗК. Експериментальна оцінка вартості наближених розв’язків досить складна у зв’язку з експоненціальною природою задачі комівояжера: важко знайти оптимум для вхідних даних великого розміру. За еталонні розв’язки використовувались деякі екземпляри з бібліотеки TSPLIB. На всій множині використаних вхідних даних відхилення вартості від оптимуму наближеного методу ЗЗК краща, ніж доведена аналітична оцінка. Можлива оптимізація реалізації наближеного метода ЗЗК з використання пам’яті, що дозволить розв’язувати задачі більшої розмірності в умовах обмежених обчислювальних ресурсів. |
URI: | http://eztuir.ztu.edu.ua/123456789/4302 |
Appears in Collections: | Вісник ЖДТУ. Серія: Технічні науки |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.