如何精通旅行商问题游戏
TLDR：旅行商问题游戏要求你恰好访问每座城市一次并返回起点，使用最短的环路。依次点击城市，路线完成后按”检查”，只有当你的距离与真正最优解相同时才算胜利。输掉时游戏会显示最优路线，仔细研究它·路线自我交叉几乎总是问题所在，消除交叉就能缩短行程。
你真正在解决什么问题
旅行商问题是计算机科学史上最著名难题的简化版本。你从一张散布着城市的地图上的起始标记出发，任务描述简单却真正难以解决：恰好访问每座城市一次，然后返回起点，使用最短的总距离。没有公式，没有捷径·你必须直接对几何关系进行推理，逐一比较完整路线，直到找到无法被超越的那条。
游戏会在你点击时实时显示当前路线的距离。一旦所有城市都已访问，按下”检查”。如果你的环路与真正的最优解相符，你就赢得胜利并进入下一关。如果更长，你会看到最优路线叠加在你的路线上·这是游戏中最有价值的时刻。这种即时的视觉对比会准确地告诉你哪里出了问题。
保持游戏新鲜感的关键是成长性。每隔几关，地图就会增加一座城市。五座变六座，六座变七座。每次新增看起来很小，但可能的排列顺序数量急剧增加。第一关能一眼看穿的答案，到第十关就成了真正的优化挑战。
完整规则说明
首先研究地图。你会看到起始标记（你的出发和返回点）以及散布其中的其他城市。你的路线始终从起点开始并回到起点·你只需点击非起始城市，它们构成环路。
按你希望访问的顺序点击城市。路线会自动绘制为连接每次点击的线段，距离计数器实时更新累计总距离。如果出错，可以使用”撤销”从路线中删去最后一座城市，或使用”清除”清空整条路线重新开始。
所有城市都点击后，按”检查”。游戏通过检查所有可能的排列来计算真正的最优解，并将你的环路与之比较。如果相符，你就赢了。如果你的路线更长，游戏会同时显示两条路线，让你诊断问题所在。
规则严格：每座城市恰好经过一次，环路必须回到起点，你的距离必须与最优解相符才能获胜。没有部分得分或”接近就好”的说法。
最重要的规律：自我交叉路线
最重要的一件事是学会发现并避免自我交叉的路线。大多数非最优路线失败的原因是路径自我交叉。当路线的两段相交时，你就在浪费距离·消除交叉几乎总能缩短行程。
原因如下：想象四座城市构成一个粗略的正方形。如果你以创造 X 形的顺序访问它们·路线从左上到右下，再从右上到左下·这两段就会交叉。最优路线沿周长行进：左上、右上、右下、左下。城市相同，无交叉，总距离更短。
游戏在你失败后显示最优路线时，首先要查找你的路线在哪里自我交叉。最优解会消除这些交叉。通常，只需交换排列中两座城市的位置，就能完全消除一处交叉，使你的距离达到最优。
每次失败后，在查看最优路线之前先数一数自己路线中的交叉点。你能看到多少个交叉？最优路线会消除所有交叉。然后找出哪次城市交换能消除最严重的交叉。这种对比是学习最多的时刻·不是来自胜利，而是来自经过分析的失败。
周长行走法。在新地图上，先在脑海中描绘外部边界·构成凸包（最外层形状）的城市。最优路线通常沿着这条周长，按顺时针或逆时针顺序访问外围城市，再插入内部城市。先围绕边缘构建路线，然后将内部城市插入额外距离最小的缺口处。
系统性路线构建
不要随机点击城市寄希望于运气，要一步步构建路线，做出减少回头路的局部决策。
从起点出发，问：我应该先访问哪座城市？通常是最近的那座，或位于某个方向上能让你扫过地图而不回头的那座。点击它。
从每座城市出发，问同样的问题·哪座未访问的城市能使我从这里出发的额外距离最小？这种贪心方法（始终前往最近或最合理的下一站）并不总能得到最优解，但能构建出一条合理的初始路线，然后你可以进行优化。
有了初步路线后，在脑海中走一遍。哪里感觉距离被浪费了？路线中是否有一段横跨地图的长线段，两座相距较远的城市在路线中相邻？交换两座城市在排列中的位置能否消除交叉或消除那次长跳跃？这些小的局部改进通常能将一条好路线转变为最优路线。
最近邻法后再优化。用贪心方式点击城市，始终前往最近的未访问站点。记录你的距离。然后在脑海中行走路线，找出一处交叉、一次回头路或一处低效之处。交换涉及该低效之处的两座城市，用这个交换重新点击路线，检查是否有所改善。重复直到达到最优或找不到明显的改进为止。
贪心法并不等于最优。最近邻法感觉很自然，但往往会留下可以减少的距离。早期关卡可能对此宽容，但随着城市数量增加，贪心路线会持续落后于最优解。将最近邻法作为快速起点，然后进行优化·不要将其作为最终答案。
常见错误及避免方法
**随意点击城市寄希望于运气。**地图几何结构很重要。距离相近的城市应该在路线中相邻出现。同一组城市应该作为一组访问，再移动到下一组。随机排序几乎总会包含代价高昂的长跳跃，而有意识的几何排序可以避免这些。
**失败后固执于第一条路线。**失败时，不要只是撤销一座城市再重新点击。研究游戏显示给你的最优路线。它与你的路线根本区别在哪里？它遵循了什么排列原则而你的没有？这种宏观视角·比较整体策略而非单个城市·才是真正进步发生的地方。
一段非常长的线段是提示，不是巧合。如果你的路线有一段横跨大部分地图的线段，这几乎总是说明排列顺序不佳。在最优路线中，没有任何一段会比其他段长得多·距离应该感觉均衡。一次孤立的长跳跃通常意味着两座相距较远的城市在路线中相邻，而它们不应如此。
**点击几次后感到被锁住了。**自由使用撤销和清除。如果走了五座城市后感觉路线不对，清除它，尝试不同的起始方向。反复尝试比苦苦修复根本性错误的方法快得多。
**寻找可记忆的公式。**每张地图都是独特的。“始终顺时针”或”始终先访问顶部”不会在不同地图上奏效。最优策略取决于这张地图的具体几何结构。训练自己以全新的眼光看待每张新地图，而不是套用记住的规则。
在点击任何城市之前花 10 秒研究地图。城市聚集在哪里？哪座城市最孤立？地图的大致形状是什么·是分散的还是紧凑的？是否有一座城市远离所有其他城市，需要代价高昂的绕路？这些观察会引导你最初的几次点击，并常常在你确定任何距离之前就将你引向最优路线。
随难度提升
早期关卡有四或五座城市，可能排列的数量少到一眼就能看出答案。在这个阶段，你通常在点击之前就能看到答案·只需扫描地图，找出最自然的环路，然后执行。
第六七关时，第六座城市出现。可能路线的数量急剧增加，靠眼睛估算不再可靠。这时战略技能变得必要。你必须对几何结构进行推理，发现交叉点，比较策略，而不仅仅是猜测。
每隔几关就会增加一座城市。到十二至十五关时，你需要管理七或八座城市，可能路线的数量达到数十万。你无法在脑海中全部检查。你必须从结构上思考·使用规律，相信空间直觉，将每张地图当作需要解决的几何问题，而非需要记忆的序列。
大地图上的分治法。在脑海中将城市分成若干组或区域。在每个区域内构建高效的子路线，然后以最小化区域间距离的顺序连接各区域。一旦城市数量超过六七座，解决较小的子问题再组合是一种可靠的方法。
练习常规
每周三次有针对性的练习，每次约 10 分钟，足以快速进步。
**练习一 · 几何观察。**进行三局，不要急于求成。在点击任何城市之前，花 15 秒向自己描述地图形状：“城市构成一个粗略的椭圆，左边有一个离群点。“让这个形状引导你的路线。在确定距离之前练习读懂地图结构。
**练习二 · 消除交叉。**进行三局。每次失败后，花整整一分钟将你的路线与最优路线进行比较。数一数你路线中的每处交叉。问：哪次交换能消除最严重的交叉？这种刻意的分析是建立长期直觉的地方。
**练习三 · 速度与稳定性。**进行五局，尝试连赢三局。到第三局时，你应该能感受到进步·构建路线更快，识别交叉更本能，你的距离更频繁地接近最优。
进步标志。当你第一次尝试就赢得一局时，你在进步·当你能从地图几何中预测最优路线并无需反馈就执行时。早期玩家频繁失败；中级玩家赢得大多数局但在较多城市数时仍会失败；高级玩家在第十关及以后都能稳定获胜。
建立心理规律日志。每局结束后，记下哪些方法奏效：“这里周长优先法成功了”或”左上角的孤立城市需要最后访问。“随着时间推移，这些观察积累成空间直觉，适用于所有未来的地图，即使是你从未见过的地图。
最后的思考
旅行商问题训练了一种远超游戏范畴的技能：在没有公式的情况下对空间排列和优化进行推理的能力。你在练习的思维方式与工程师设计配送路线、外科医生安排手术步骤、建筑师高效布置空间所用的思维方式相同。
游戏旨在随你一起成长。早期关卡教授基础·点击城市、发现交叉、检查距离。后期关卡需要更深入的推理·平衡多个约束，看清全局，在可能性数量爆炸时相信空间直觉。
从你现在的水平开始。进行处于你能力边缘的关卡。花时间从每次失败中学习。最优路线始终存在，等待被发现。你的任务是训练自己更快地看到它。
