共 3 条
一个基于填充函数变换的对称TSP问题的局部搜索算法
被引：16
作者：
朱文兴
傅清祥
机构：
[1] 福州大学计算机科学与技术系
[2] 福州大学计算机科学与技术系 福州
[3] 中国科学院软件研究所计算机科学重点研究实验室
[4] 北京
来源：
关键词：
对称TSP问题;
局部搜索算法;
填充函数变换;
近似最优解;
D O I：
暂无
中图分类号：
TP301.6 [算法理论];
学科分类号：
081202 ;
摘要：
该文提出了求对称 TSP问题近优解的填充函数算法 .首先 ,在用局部搜索算法求得对称 TSP问题的一个局部极小解后 ,对该问题作填充函数变换得到一新的组合优化问题 ,新问题的局部极小解和最优解分别是原问题的局部极小解和最优解 ,而且在对称 TSP问题的目标函数值大于或等于其目标函数当前极小值的区域中 ,新问题只有一个已知的局部极小解 .随后用局部搜索算法求新问题的一个局部极小解 ,它或者是已知的局部极小解 ,或者是对称 TSP问题的更好的局部极小解 .对多个标准实例的计算试验表明 ,该文所构造的算法优于直接求解对称 TSP问题的局部搜索算法 .
引用
收藏
页码：701 / 707
页数：7
相关论文