货郎担问题的几何分块算法及China TSP问题的最终解决  

The Geometric Region Divided Method for Solving the China TSP Problem

作　　者：陈沐天[1] 蔡和熙[1] 

机构地区：[1]汕头大学计算机系

出　　处：《计算机工程与科学》1998年第1期22-27,共6页Computer Engineering & Science

摘　　要：本文提出了货郎担问题的一种新的求解方法，即几何分块算法，用该方法找到了ＣｈｉｎａＴＳＰ问题的最短路径，并分析了求解中的一些策略问题。In this paper,a geometric region divided method for solving TSP problem is presented.Use this method,we found the shortest path for China TSP Problem.Then we analyses some important strategies for this method.

关 键 词：NP问题 货郎问题 ChianTSP问题 

分 类 号：O22[理学—运筹学与控制论]