随机算法重启策略的构造及其在TSP中的应用

• 作者: 徐云 谢幸 陈国良 顾钧
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 重启策略 TSP 随机算法 组合优化
• 年，卷（期）: 2002,（5）
• 所属期刊栏目: 研究论文与技术报告
• 页码范围: 514-519
• 页数: 6页
• 分类号: TP301
• 字数: 5704字
• 语种: 中文
• DOI: 10.3321/j.issn:0254-4164.2002.05.010

摘要

NP难解问题是计算机算法和理论界长期研究的课题.在求解NP难解问题时,随机算法的性能往往很不稳定.在以往的实验中,人们发现基于重启的优化方法可以提高Las Vegas算法的性能和稳定性.尽管它的思想比较直观,但对它的性能进行理论分析却并不容易,这在很大程度上限制了其应用.该文使用连续概率分布对算法性能分布建模,针对Las Vegas算法提出了一种高效的重启策略构造方法.该文从平均性能和稳定性两个角度分析了该方法的效率,同时通过将其应用于求解大规模旅行商问题(TSP)显示了其应用价值.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	陈国良	中国科学技术大学计算机科学与技术系	123	2142	20.0	43.0
2	徐云	中国科学技术大学计算机科学与技术系	79	411	13.0	16.0
3	顾钧	香港科技大学计算机科学系	19	289	7.0	17.0
4	谢幸	中国科学技术大学计算机科学与技术系	4	18	3.0	4.0