对于优化问题例如旅行推销员的问题的解，有许多实际用途。与其相关的问题会对人们认识动物的觅食行为提供一种理解方式吗？

推销员旅行的问题对数学与物理工作者有很强的吸引力，而且有许多实用价值。初看起来，与之相关的旅行者旅行的问题则几乎对任何人都没有吸引力，除了那些爱吵架的旅行伙伴们。

这两个问题描述的是什么呢？推销员旅行的问题是，一位推销员准备去拜访一大片地区内的N个客户，如何走才是最近的路呢？这个经典问题属于全局优化问题。由于推销员的下一个目标取决于他对尚未拜访过的每个客户位置的了解，对于推销员旅行问题的解答远不是无关紧要的，它吸引了一大批最优秀的头脑。

在《物理评论快报》上，利马（Lima）等人从局部优化问题中引入了一个新的例子，并把它叫作做“旅行者问题”。这个问题是一位旅行者不限于每个城市只去一次，而是由于经济预算或其他原因，限于只去最近的城市。注意，旅行者只想使到达下一个城市的路最近——一个局部优化问题——而不是像推销员那样去通盘考虑整个旅途的总距离。所以乍一看，旅行者问题似乎是无关紧要的。

然而旅行者问题也显示出一些令人惊讶的行为。例如在访问过一些城市后旅行者到了A城，而距离A城最近的城市B没有比A城更近的邻近城市了。这样只要旅行者到达A城或B城，他就将在它们中间振荡，成为“二城循环”。这样的“二城循环”就如一个“旅行者陷阱”，旅行者如西西弗斯一般游走，直至永远。

利马等人通过假定理想的旅行者更像一个真实的旅行者，他不喜欢去自己刚刚去过的城市，于是引入了一条法则来避免这种情况发生从而丰富了旅行者的问题。以前的逻辑同样适用，只是现在旅行者可以陷入三城循环中（三个城市组成三角形A-B-C，旅行者先走到A，然后到B，然后到C后又返回A。）令人吃惊的是，除了三城循环，同样存在p城循环，p可以大到任意数值。

这一简单的规则可进一步推广为旅行者不能访问他先前去过V次的地方（在上述两例中V分别等于0和1）。值得注意的是，在游览了几个城市之后，旅行者总是陷入重复访问它们的一个子集的陷阱之中。事实上，N个城市的总集合可以被分成许多个旅行者进得去出得来的“自由城市”，以及若干个他被迫去重复游览同一个由p个城市组成的集合的旅行陷阱。

因此初看起来，旅行者面临的前景与会遇到陷阱的随机步行问题没有什么大的区别。但在随机步行问题中，陷阱的大小总是被假定为是依据以特定大小为中心的对称的归一化分布的。在旅行者问题中，p圈陷阱可以有一系列的p值，所以特定大小的陷阱的数量估计会呈归一化分布。但利马等人发现，p圈的数目是遵循p函数的指数单调递减律的，指数值约为2.7。这个结果非常出人意料，因为指数律一般用在随机性决定的事件中，但这里的每一步却是确定的。指数律一定是由城市的初始随机分布而引起的。因此可以得出一个很有吸引力的想法：这一问题与典型的幂指数律系统有很大的相似性。

许多人再过一段时间后会陷入一种常规——在他们旅行时去重游同样的城市系列，在他们的社交生活中去重上同样的饭馆系列，甚至一些科学家会重新考虑一些自己研究过的想法——所有的行为的发生看似神秘莫测，而事实上可能是基于一个简单的原因的。确实，这些行为更像旅行者旅行的问题而不是推销员旅行的问题。通常我们都认为自己的行为是有自由意志决定的，很可能有些行为方式是决定性法则应用于随机变化的环境的结果，也许与决定旅行者旅行路线的法则并不完全相同。

[Nature，2001年9月27日]