旅行推销员问题凸包方法的性能比分析

• 作者: 刘剑平
• 来源期刊: 华东理工大学学报（自然科学版）
• 学科: 工学
• 关键词: 旅行推销员问题 性能比 凸包 增量最小插入法 最近插入法 最近加入法
• 年，卷（期）: 2004,（6）
• 所属期刊栏目: 研究论文
• 页码范围: 712-715
• 页数: 4页
• 分类号: TP301
• 字数: 3135字
• 语种: 中文
• DOI: 10.3969/j.issn.1006-3080.2004.06.024

摘要

在欧几里德平面上证明了旅行推销员问题的凸包方法的性能比上界为n/2,同时给出了凸包随意插入算法的性能比可以接近n/2的例子.另外,对凸包增量最小插入法、凸包最近插入法及凸包最近加入法给出了性能比不超过3的证明.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	刘剑平	华东理工大学数学系	7	19	2.0	4.0