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

作     者：周培德 周忠平 张欢 ZHOU Pei-de;ZHOU Zhong-ping;ZHANG Huan

作者机构：北京理工大学计算机科学与工程系北京100081 

出 版 物：《北京理工大学学报》 (Transactions of Beijing Institute of Technology)

年 卷 期：2000年第20卷第2期

页      码：201-204页

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

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

学科分类：0810[工学-土木类] 12[管理学] 1201[管理学-管理科学与工程类] 07[理学] 070104[070104] 0805[工学-能源动力学] 070105[070105] 0701[理学-数学类] 0812[工学-测绘类] 

核心收录：

D　O　I：10.3969/j.issn.1001-0645.2000.02.015

馆 藏 号：203365473...