| 基于分治法和分支限界法的大规模TSP算法 |
| |
| 引用本文： | 马杨,戴锡笠,牟廉明.基于分治法和分支限界法的大规模TSP算法[J].内江师范学院学报,2012,27(10):20-23,32. |
| |
| 作者姓名： | 马杨 戴锡笠 牟廉明 |
| |
| 作者单位： | 内江师范学院数学与信息科学学院,四川 内江,641100 |
| |
| 基金项目： | 四川科技厅应用基础研究基金(07JY029-125);内江师范学院自然科学重点项目基金(12NJZ03);大学生创新性实验计划项目(X201205) |
| |
| 摘 要： | 利用分治法能够处理大规模问题但精度较低,分支限界法能够得到精确解但时间复杂度很高的优点,设计一种有效的基于分治法和分支限界法的大规模TSP求解方法.该算法利用聚类和凸包技术将大规模问题逐层进行有效划分,直到适合分支限界法求解的最佳规模；然后用分支限界法求出每个子问题和每层子问题间的最优解,合并而得到整个问题的解.比较实验表明:该算法在求解质量、稳定性和时间效率上有明显优势.
|
| 关 键 词： | 旅行商问题 分治法 分支限界法 |
A Large-scale TSP Algorithm Based on Divide-and-Conquer Method and Branch-bounding Method |
| |
| MA Yang
,
DAI Xi-li
,
MOU Lian-ming.A Large-scale TSP Algorithm Based on Divide-and-Conquer Method and Branch-bounding Method[J].Journal of Neijiang Teachers College,2012,27(10):20-23,32. |
| |
| Authors: | MA Yang DAI Xi-li MOU Lian-ming |
| |
| Institution: | *(College of Mathematics and Information Science,Neijiang Normal University,Neijiang,Sichuan 641100,China) |
| |
| Abstract: | The determination of large scale TSP problem has long become a headache in the field of mathematics.The divide-and-conquer method,though capable of handling large-scale problems,yet is criticized for its poor accuracy;branch-bounding method,although reliable in obtaining exact solution,yet is blamed for its high time complexity.By integrating the advantages of the two,a new effective method for solving large-scale TSP is designed through combination of the two methods.The newly designed algorithm,using clustering and convex hull technology to divide the large-scale problem layer by layer effectively,can eventually work out the optimal size fitting for the determination of solution through branch-bounding method and then obtain the optimal solution of each sub-problem and each layer’s sub-problems by branch-bounding method,and by merging these results,thus to get the solution of the whole problem.A comparative experiment reveals that: the new algorithm boasts its quality,stability and time efficiency in the determination of solutions. |
| |
| Keywords: | traveling salesman problem divide-and-conquer branch-bounding method |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
