寻求中国货郎担问题最短回路的多项式时间算法

摘要：

研究求解中国货郎担问题最短回路的多项式时间算法.首先利用计算几何中凸壳与中轴的结构将点集划分成若干个子点集,然后反复采用求子点集凸壳及划分剩余子点集的方法,求得通过子点集的子路径,最后将各子路径连接成一条回路.中国货郎担问题存在多项式时间算法求得最短回路.所设计的算法的时间复杂性为O(n2lbn),将它用于中国货郎担问题,得到一条长度为15404km的最短回路.与陈沐天等人采用几何分块方法所得的最短回路相一致.

关键词：中国货郎担问题、最短回路、多项式时间算法

所属期刊栏目：20

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

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

页数：共4页

页码：201-204