Про один алгоритм розв’язання задачі комівояжера на основі методу оптимізації потоків даних

Abstract

У статті розглянуто методику послідовного застосування потокових схем розподілу однорідного ресурсу для розв’язання задачі комівояжера, яка формулюється як задача пошуку маршруту відвідування заданої кількості міст без повторень з мінімальною відстанню руху або тривалістю пересування. Ставиться завдання формалізації алгоритму розв’язання задачі комівояжера за допомогою методу потокового розподілу ресурсу і використання схеми backtracking (повернення). Запропоновано використання методу Орліна оптимізації розподілу потоку на графі.

The article discusses the method of sequential application of flow schemes for the distribution of a homogeneous resource to solve the traveling salesman problem, which is formulated as the problem of finding a route to visit a given number of cities without repetitions with a minimum distance of movement or duration of movement. The task is posed to formalize the algorithm for solving the traveling salesman problem using the method of streaming resource distribution and using the backtracking scheme. It is proposed to use the Orlin method to optimize the flow distribution on the graph.