Andrecut M, Ali M K
Department of Physics, University of Lethbridge, 4401 University Drive, Lethbridge, Alberta, Canada T1K 3M4.
Phys Rev E Stat Nonlin Soft Matter Phys. 2001 Apr;63(4 Pt 2):047103. doi: 10.1103/PhysRevE.63.047103. Epub 2001 Mar 27.
We investigate the finite size scaling of the mean optimal tour length as a function of density of obstacles in a constrained variant of the traveling salesman problem (TSP). The computational experience pointed out a critical transition (at rho(c) approximately 85%) in the dependence between the excess of the mean optimal tour length over the Held-Karp lower bound and the density of obstacles.
我们研究了旅行商问题（TSP）的一个受限变体中，平均最优路径长度作为障碍物密度函数的有限尺寸缩放。计算经验指出，平均最优路径长度超过Held-Karp下界的余量与障碍物密度之间的依赖关系存在一个临界转变（在rho(c)约为85%时）。
