球面旅行商问题常数及其实验分析  

Spherical traveling salesman problem constant and its experimental analysis

作　　者：王刚[1] 骆志刚[1] 

机构地区：[1]国防科学技术大学计算机学院,长沙410073

出　　处：《计算机应用研究》2011年第12期4489-4491,共3页Application Research of Computers

摘　　要：给出了球面随机旅行商问题最优值的一个上界以及最优值期望的一个下界。猜想球面旅行商问题常数存在且与平面旅行商问题常数相等。所做两组数值实验支持该猜想,且显示球面比平面正方形更适宜作为二维旅行商问题常数的测试床。This paper gave an upper bound of the optimal value to the random spherical traveling salesman problem, and also a lower bound of the expectation of the optimal value. Conjectured that there exists a spherical traveling salesman problem constant whose value is the same as the plane traveling salesman problem constant. Two numerical experiments support the conjecture. And they also show that the sphere surface is a better test bed than the plane square for the 2-dimensional traveling salesman problem constant.

关 键 词：旅行商问题 哈密顿回路 随机组合优化 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]