10.2 寻找路线的策略

人类或许没有发现最优路线的天分，不过在其他方面还是相当优秀的。美国国家航空航天博物馆有一件展品，向参观者提出挑战，让他们试着寻找周游美国部分机场所在地的路线。展品如图10-2所示，在触控面板上，参观者可以一个接一个地选取各座机场，逐步构造出一条路线。在这样的挑战面前，对于中等大小的例子，人类参与者总是能够得到质量好的路线。尽管许多数学方法也能轻易得出质量相当的结果，但是很明显，人工求解过程中用到的直接计算步骤少得多。已有心理学研究团队对这一现象进行探究，旨在理解人类的解题能力。¹

^{1. 在此项研究的帮助下，《解题学报》（Journal of Problem Solving）创刊，其主编为人工求解TSP领域的领军人物Zygmunt Pizlo。}

图10-2　美国国家航空航天博物馆的TSP展品，Bärbel Klaaßen供图

10.2.1 路线之格式塔

心理学专家发现，如果对比不同质量的路线的几何形状，高质量的路线比低质量的路线“感觉对”，这或许能表明追求最小结构的人类本性。在澳大利亚阿德雷德大学，Douglas Vickers主持开展了一项实验，将这一论题表现得淋漓尽致。¹研究中，主持人向两组参与者展示一组相同的TSP题目，规模分别为10座、25座及40座城市（每种规模有两道题目），但给出不同的实验指导：最优化组得到的指令是找出每道题目的最短路线，格式塔组则是找出“整体看起来最自然、最迷人、最优美的路线”。实验结果表明，两组得到的路线质量竟然相差无几。事实上，寻找路线水平最高的实验参与者来自格式塔组，她是一名时装设计师，在6道题中找出了5道的最短路线。

^{1. Vickers, D., et al. 2001. Psychol. Res. 65, 34–45.}

10.2.2 儿童找到的路线

加拿大维多利亚大学的Iris van Rooij领导了一项实验，探究在面对相同题目时，儿童的寻找路线能力与成人的差别有多大。¹借助这类实验，研究者可以对比考察知觉（感知）能力与认知能力。这是因为人们认为，低龄童在寻找路线时，将主要依赖他们对好结构的知觉能力。

^{1. van Rooij, I., et al. 2006. J. Prob. Solv. 1, 44–73.}

实验参与者是7岁和12岁的小学生及一组大学生，小学生将得到贴纸作为奖励。TSP测试集由随机生成的题目组成，规模为5座城市、10座城市和15座城市，每种规模有5道题目，以参与者找到的路线长度超出最优解的百分数作为其表现分数。实验结果如表10-1所示，由此可见，从儿童到成人，表现有所提高，但是就连低龄童也能找出相当短的路线。

表10-1　儿童与成人找到路线长度的平均最优性差距

10.2.3 凸包假说

英国兰卡斯特大学的James MacGregor和Thomas Ormerod有不同的研究重点，即点集的整体形状对寻找路线的指导程度如何。¹为衡量点集的整体形状，可以考虑橡皮筋围住这一组城市的样子，如图10-3所示。

^{1. MacGregor, J. N., T. Ormerod. 1996. Percept. Pyschophys. 58, 527–539.}

图10-3　一个点集的凸包

橡皮筋所在的曲线就是这组城市的凸包边界。边界本身通常并非路线，但容易验证凸包规则：最优路线需要避免自交，所以路线经过边界各点的顺序必须和凸包边界经过边界各点的顺序相同。如图10-4所示，在33座城市的宝洁公司TSP题目中，凸包边界上共有12个点，它们在边界上的顺序与在最优路线上的顺序相同，其余城市的顺序则是由边界向内侧拐入短的子路径而得。这里把不在边界上的城市称为内部点。

图10-4　沿凸包顺序的最优路线

仔细分析10座和20座城市TSP题目的人工解题实验结果之后，MacGregor和Ormerod得出结论：寻找TSP题目近似解的难度是由内部点的个数决定的。另外，他们还写道：“这里给出的证据表明，人类实验者求解的依据是感知TSP题目的全局空间特性，尤其是凸包边界的空间特性。”这种假说的真实度几何？人工解题领域争议不休。多数专业讨论的焦点都落在实验研究使用的数据集类型，但是同样存在一般性的疑问，即人类利用的解题策略究竟是从整体到局部还是从局部到整体。如果是从整体到局部，人类会首先感知整体结构，然后做出局部选择，将各座城市填入整体结构的合适位置；反之，如果是从局部到整体，则人类会首先做出局部分析（比如聚类分组），然后才尽力将局部信息以最好的形式组合成整体路线。

10.2.4 实地TSP题目

在上面这些人类参与的实验中，TSP题目都是视觉呈现的，即出题形式或为在纸上描绘路线，或为在计算机屏幕上找出路线。Jan Wiener和德国图宾根大学的一个研究小组反其道而行之，针对实地TSP研究人类表现。他们的实验要求参与者在一间长8.4米、宽6.0米的房间里访问一系列目的地。¹实验中，25个长方形柱体摆在地上，每个柱体上有一枚彩色符号。参与者得到的指示包括一个出发点和若干符号（最多为9种），他们需要到达所有符号所在柱体并最后返回出发点。结果再次支持了人类擅长求解小规模TSP的结论，该实验的报酬是每小时8欧元（约合64元人民币）。

^{1. Wiener, J. M., N. N. Ehbauer, H. A. Mallot. 2009. Psychol. Res. 77, 644–658.}

图10-5　人力求解TSP的实验，Jan Wiener供图