Improvd Hungarian Algorithm for Solving Problem of Travel Providers
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.
万方数据
维普
