Анотація:
Проведено експериментальне дослідження властивостей наближеного методу розв’язання
загальної задачі комівояжера (ЗЗК) на вхідних даних великого розміру та його порівняння із
відомими евристичними й наближеними алгоритмами. Наближений метод виконується у дві
стадії. На першій стадії ЗЗК поліноміально зводиться до симетричної задачі комівояжера
(СЗК). На другій стадії виконується поліноміальний наближений алгоритм СЗК, результат
роботи якого перетворюється у наближений розв’язок ЗЗК. Експериментальна оцінка вартості
наближених розв’язків досить складна у зв’язку з експоненціальною природою задачі
комівояжера: важко знайти оптимум для вхідних даних великого розміру. За еталонні розв’язки
використовувались деякі екземпляри з бібліотеки TSPLIB. На всій множині використаних вхідних
даних відхилення вартості від оптимуму наближеного методу ЗЗК краща, ніж доведена
аналітична оцінка. Можлива оптимізація реалізації наближеного метода ЗЗК з використання
пам’яті, що дозволить розв’язувати задачі більшої розмірності в умовах обмежених
обчислювальних ресурсів.
Анотація (англ.):
Experimental research of approximate Common Travelling Salesman Problem (CTSP) solution method with input data of big size is conducted. Also the comparison of the method with well-known approximate and heuristic algorithms is performed. Approximate method is executing in two stages. On the first stage CTSP is transformed to Symmetric TSP (STSP) in polynomial time. On the second stage polynomial approximate algorithm of STSP is executed, and its results are transformed to approximate solution of CTSP. Experimental estimations of approximate solution cost are difficult enough because of exponential nature of TSP: it is hard to find optimum for input data of large size. Selected samples from the TSPLIB library were used as etalon solutions. Optimization of the implementation of the CTSP approximate method is possible, which allows solving of tasks of larger size in limited computational resources conditions.
Keywords: сommon travelling salesman problem; approximate method.
