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

摘要：

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

关键词：旅行推销员问题、性能比、凸包、增量最小插入法、最近插入法、最近加入法

所属期刊栏目：30

分类号：TP301(计算技术、计算机技术)

资助基金：华东理工大学校科研和教改项目

在线出版日期：2005-01-20（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：712-715