Перспективи використання графових нейромереж для вирішення задачі комівояжера

Abstract

Розглянуто задачу комівояжера як класичну проблему комбінаторної оптимізації. Проаналізовано традиційні методи її розв’язання, зокрема метод перебору та метод найближчих сусідів, їхні переваги та обмеження. Описано можливості використання графових нейронних мереж для знаходження якісних рішень у великих графах.

Considered the traveling salesman problem as a classical combinatorial optimisation problem. Analyzed traditional methods of its solution, in particular, the brute-force method and the nearest neighbours method, their advantages and limitations. The possibilities of using graph neural networks to find high-quality solutions in large graphs are described.