你跳过了游戏，所以这里是最优路径。这是你所愿做的事情吗？一个最优路径。几周前，30,954 人在同一个草坪上割草。他们的路径是这样的。玩家 ID：（移动次数）许多人接近最优路径。52%的人在最佳路径上偏差不超过五步，16%的人做到了完美。许多不同的方法，但结果相似，表现相当不错。只需覆盖49个方格，但人们找到了14,589种不同的方法来完成它。尽管有如此多的变化，中位数的人仍然达到了91%的效率（在5步以内）。对于这个小草坪，有12种不同的完美解决方案，人们找到了所有这些解决方案。但你实际上在解决什么？找出最佳路径是一个经典的计算机科学问题。不要离开！我们保证这不会变得太复杂。路径规划问题。解决割草问题的正式名称是覆盖路径规划，它与计算机科学中最著名的路径规划问题之一有关：旅行商问题。前提很简单：一个销售员必须访问一组城市，每个城市恰好访问一次，然后返回起点，同时采取最短路径。一个计划停靠点的披萨外卖员或一个最大化糖果收获的万圣节讨糖者正在解决这个问题的一个版本。00000路径长度：0在阅读了一项研究后，我们想创建这个割草实验，该研究发现，人类的解决方案与计算机计算的最佳解决方案非常接近，并在70个以上停靠点的情况下效率仅比最佳低11%。我们在下方重现了他们的图表。随着停靠点的增加，人类的能力下降。割草的结果会类似吗？请稍作迂回。解决此类问题有两种主要方法。简化一下，有一些算法能保证最优路径，还有一些启发式方法，它们利用捷径快速找到“足够好”的路径。为什么人们需要启发式方法？如果一个销售人员必须访问10个城市，并且必须检查每一条可能的路径，我们惊讶地发现需要测试360万个路径。随着更多城市的增加，这个数字呈指数级增长。15个城市时，我们有1.3万亿条可能路径。😱20个城市膨胀到2.4万亿条可能路径。🤯当问题较小时，方法不太重要，几乎所有方法都有效。但随着复杂性的增加，最优变得不可能，启发式变得必要。这对于人和计算机都是如此。当完美不切实际时，人们同样会依靠“足够好”的策略。一次导览。让我们以导导演切的风格重播一次割草会话，并在此过程中进行一些评论。对于这个演示，我们将使用一个自称为Bones的人的完美平均表现。他们用了54步——比最优多了5步。我们记录了每一步的时间戳，因此每一次犹豫或转向都留下了数据足迹。我们将回放到起点并逐步跟进。在Bones甚至还没有移动之前，他们就暂停了2.9秒。在这里，他们也表现得非常平均。当看到草坪显现出来时，他们自然暂停了片刻，以观察草坪，可能也制定了一个计划。然后Bones出发了！在开头的几步中没有什么可决定的，直到第五个方格。继续向右，还是向下？这是路径首次分歧的地方。Bones几乎没有犹豫（0.7秒），决定向下走，就像20%的其他人一样。这是一个关键时刻，我们稍后会再回到这里。Bones继续沿着边缘走，直到到达底部。当他们意识到遇到死胡同时，第一次显著的停顿（2.4秒）来临，他们不得不退回。认识到错误后，Bones调头重新割了他们的第一个方格以完成这一部分。为了到达另一个开放的区域，他们不得不再退回两个方格。然后，他们大多数时间都顺利进行，先绕过边缘，再填补中间剩余的方格。区分最佳割草机和其他人的关键在于一个决定。我们可以将草坪分为两个主要区域：左边和右边。Bones先完成了左侧区域。由于这是死胡同，唯一的出口就是退回，形成了不可避免的回溯。如果我们看看每个人的结束位置，可以看到这一点的结果。与最佳结果相隔三步或更多的人在草坪各处散布。而那些在最佳结果两步之内的人，包括17%完美的人，则选择先割右侧，以便在左侧结束他们的运行，提前预测到死胡同陷阱。其中之一是一个真实名字叫Sarah的人。我们与她联系，并了解到她故意在左边结束。“我看到最后的死胡同，我心想，好的，我也要在那儿结束，所以不要先往那里走。”Sarah知道死胡同意味着左侧必须留到最后以避免回溯。停顿数据支撑了她的观点。