遗传算法与分枝定界法求解TSP研究  

Research on Solving TSP with Genetic Algorithm or Branch and Bound Method

作　　者：杨思明[1] 王凤军[1] 

机构地区：[1]无锡商业职业技术学院,江苏 无锡

出　　处：《计算机科学与应用》2020年第9期1609-1617,共9页Computer Science and Application

摘　　要：在解决旅行商问题时,有两种常用的方法,即遗传算法与分枝定界法。本文使用K均值聚类改进分枝定界法,求解给定的旅行商问题。通过运用这两种算法求解TSP进行比较,相比之下K均值聚类优化的分枝定界法在解决旅行商问题中表现得更好。When solving the traveling salesman problem, there are two commonly used methods, namely genetic algorithm method, and branch and bound method. To solve the given traveling salesman problem, this paper uses K-means clustering to improve the branch and bound method. By comparing the performance of these two algorithms in solving the TSP problem, the branch and bound method with K-means clustering performs better in solving the traveling salesman problem.

关 键 词：旅行商问题 遗传算法 分枝定界法 

分 类 号：TP3[自动化与计算机技术—计算机科学与技术]