Lipowski Adam, Lipowska Dorota
Faculty of Physics, Adam Mickiewicz University, Poznań, Poland.
Phys Rev E Stat Nonlin Soft Matter Phys. 2011 Jun;83(6 Pt 1):061115. doi: 10.1103/PhysRevE.83.061115. Epub 2011 Jun 13.
Using Monte Carlo simulations we examine the diffusive properties of the greedy algorithm in the d-dimensional traveling salesman problem. Our results show that for d=3 and 4 the average squared distance from the origin (r(2)) is proportional to the number of steps t. In the d=2 case such a scaling is modified with some logarithmic corrections, which might suggest that d=2 is the critical dimension of the problem. The distribution of lengths also shows marked differences between d=2 and d>2 versions. A simple strategy adopted by the salesman might resemble strategies chosen by some foraging and hunting animals, for which anomalous diffusive behavior has recently been reported and interpreted in terms of Lévy flights. Our results suggest that broad and Lévy-like distributions in such systems might appear due to dimension-dependent properties of a search space.
我们使用蒙特卡罗模拟来研究贪婪算法在d维旅行商问题中的扩散特性。我们的结果表明，对于d = 3和4，到原点的平均平方距离(r²)与步数t成正比。在d = 2的情况下，这种标度会有一些对数修正，这可能表明d = 2是该问题的临界维度。长度分布在d = 2和d>2的版本之间也显示出明显差异。旅行商采用的一种简单策略可能类似于一些觅食和狩猎动物所选择的策略，最近有报道称这些动物存在反常扩散行为，并根据 Lévy 飞行进行了解释。我们的结果表明，此类系统中广泛的、类似 Lévy 的分布可能是由于搜索空间的维度相关特性而出现的。
