摘要
给出了球面随机旅行商问题最优值的一个上界以及最优值期望的一个下界。猜想球面旅行商问题常数存在且与平面旅行商问题常数相等。所做两组数值实验支持该猜想,且显示球面比平面正方形更适宜作为二维旅行商问题常数的测试床。
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.
出处
《计算机应用研究》
CSCD
北大核心
2011年第12期4489-4491,共3页
Application Research of Computers
关键词
旅行商问题
哈密顿回路
随机组合优化
traveling salesman problem（TSP）
Hamiltonian tour
stochastic combinatorial optimization
