Вплив рандомізації жадібного пошуку на ефективність розв’язання задач комівояжера

Abstract

Проведено порівняльний аналіз ефективності класичного жадібного алгоритму з мультистартами та рандомізованого жадібного алгоритму для розв’язання задачі комівояжера. Рандомізація реалізована простим випадковим вибором з двох кандидатів. На основі класичних тестових наборів даних (burma14, bayg29, att48, eil51) продемонстровано, що завдяки поєднанню випадковості та цілеспрямованої «жадібної» стратегії навіть такий базовий рандомізований алгоритм здатний знаходити коротші маршрути, успішно обходячи локальні пастки.

A comparative analysis was conducted to evaluate the performance of the classic greedy algorithm with multiple starts and the randomized greedy algorithm in solving the travelling salesman problem. Randomization was implemented using simple random selection from two candidates. Using classic test datasets (Burma14, Bayg29, Att48 and Eil51), it was demonstrated that combining randomness with a targeted greedy search enables even a basic randomized algorithm to find shorter routes while successfully avoiding local traps.