To address the issue of multiple closed circuits arising from applying the traditional Hungarian algorithm to the travelling salesman problem(TSP),a breaking mechanism was proposed,leading to the development of the Break-Cycle Hungarian Algorithm.By adopting the description method of the assignment problem for modeling the TSP and establishing the conversion relationship between them,it is demonstrated that a sufficient and necessary condition for a feasible solution to the TSP is that the feasible solution of the corresponding assignment problem,combined with auxiliary edges,contains only one cycle.The effectiveness of the algorithm was veri-fied through testing and comparative analysis on six standard travelling salesmen,showing that the improved Hungarian algorithm can effectively solve the TSP across various datasets.
维普
万方数据