[1]宋海洲.TSP问题的一种快速近似算法及应用[J].华侨大学学报(自然科学版),2005,26(3):231-234.[doi:10.3969/j.issn.1000-5013.2005.03.002]
　Song Haizhou.A Fast and Approximate Algorithm For Solving Travelling Salesman Problem and Its Applicalion[J].Journal of Huaqiao University(Natural Science),2005,26(3):231-234.[doi:10.3969/j.issn.1000-5013.2005.03.002]
点击复制

TSP问题的一种快速近似算法及应用()
分享到：

《华侨大学学报（自然科学版）》[ISSN:1000-5013/CN:35-1079/N]

卷:
第26卷
期数:
2005年第3期
页码:
231-234
栏目:
出版日期:
2005-07-20

文章信息/Info

Title:
A Fast and Approximate Algorithm For Solving Travelling Salesman Problem and Its Applicalion
文章编号:
1000-5013(2005)03-0231-04
作者:
宋海洲
华侨大学数学系 福建泉州362021
Author(s):
Song Haizhou
Department of Mathematics, Huaqiao University, 362021, Quanzhou, China
关键词:
TSP;  近似算法;  遗传算法;  初始种群
Keywords:
travelling salesman problem;  approximate algorithm;  generate algorithm;  initial population
分类号:
TP301.6
DOI:
10.3969/j.issn.1000-5013.2005.03.002
文献标志码:
A
摘要:
给出求解度约束最小生成树(DCMST)问题的一种快速近似算法.在此基础上,又给出求解TSP问题的一种快速近似算法,并在微机上实现且其数值试验的效果良好.最后,将求解TSP问题的近似快速算法作一些改进,应用于遗传算法的初始种群生成并进行数值实验.结果表明,用文中算法生成的初始种群,比起一般方法产生的初始种群性能有很大改进.该算法可以加速遗传算法的寻优速度.
Abstract:
A fast and approximate algorithm is given at first for solving the problem of minimum spanning tree with constraint of degree. On this basis, a fast and approximate algorithm is then given for solving travelling salesman problem (TSP); and is implemented on a micro-computer, with a good effect as shown by enormous numerical tests. This fast and approximate algorithm for solving TSP is applied finally to generating initial population of genetic algorith after a little modification; and the improved algorithm is tested numerically. As indicated by experimental results, the initial population generated by this algorithm inproved greatly as compared with the performance of the initial population generated by the conventional method; and furthermore, this algorithm will accelerate the optimum search of genetic algorithm.

参考文献/References:

[1] 康立山, 谢云, 尤矢勇. 非数值并行算法-模拟退火算法 [M]. 北京:科学出版社, 2000.149-153.
[2] 宋海洲. 生产函数中参数方法的进一步改进 [J]. 华侨大学学报(自然科学版), 2005(1):23-26.doi:10.3969/j.issn.1000-5013.2005.01.006.
[3] 顾立尧. 带有度约束的最小耗费生成树的分支限界算法 [J]. 计算机应用与软件, 1989(6):49-54.
[4] 马良, 蒋馥. 度约束最小生成树的快速算法 [J]. 运筹与管理, 1998(1):1-5.

更新日期/Last Update: 2014-03-23