围住一只猫猫需要几步？【多猫预警】( 三 )
文章图片
文章图片
文章图片
文章图片
图6是一个包围圈的雏形 ， 可以看到1 ， 2 ， 11 ， 4 ， 5号点都有障碍物 ， 他们对应的顶点都已完成 。但它并不是一个完整的包围圈 ， 因为顶点6是未完成的 。如果猫猫从右上往左上逃 ， 我们堵住8号点后猫猫会逃至16号点 ， 此时6 ， 7两点均空 ， 猫猫逃脱 。顶点5虽然有障碍物 ， 但它本身也是一个顶点 ， 不能算作顶点6的相邻点 。所以这个包围圈的完成度是5 。
文章图片
文章图片
从棋盘深度为8的情形我们可以知道 ， 在包围圈完成 ， 即完成度为6时 ， 如果猫猫距离包围圈至少有2格 ， 我们根据猫猫的位置放障碍物来围堵就可以必胜 。也就是说 ， 必胜条件是包围圈深度+包围圈完成度至少为8 。所幸 ， 上图中的猫猫距离包围圈有3格 ， 也就是说包围圈的深度是3 ， 如下图所示 ， 我们只需补上包围圈里缺失的点 ， 就可以保证必胜 。这就是看过本文的我们 ， 第一步落在看似不需要优先围堵的6号点的原因 。下面图7展示了图6例子中围猫的必胜方法 。
文章图片
文章图片
需要注意的是 ， 画包围圈也是有技巧的 。比如下面这个图8就有AB两种画圈的方式 ， 且包围圈的完成度均为5 。如果按照红色的A方案规划4 ， 5号点之间的包围圈 ， 则包围圈的深度为2 ， 5+2
文章图片
文章图片
然而 ， 由于游戏条件的限制 ， 初始只有6-8个障碍物 ， 棋盘深度也只有5 ， 所以大多数情况下都是无法必胜的 ， 如果想围住小猫 ， 就多多地刷新吧！
不过 ， 实际上游戏里的这只小猫并不太聪明 ， 它的逃脱逻辑只是一个单层的贪心算法：只考虑当前看来是最好的逃脱路线 。所以我们可以利用这点设下陷阱 ， 诱导猫猫走出多余的步数 ， 从而赢下无法必胜的棋盘 ， 有兴趣的读者朋友一定要去试一试哦 。
文章图片
文章图片
最后 ， 让我们总结一下围住猫猫的秘诀吧！只需要简单的三步哦 。第一步：根据已有的初始障碍物划定包围圈 ， 在保证有尽可能多顶点被完成的前提下 ， 让包围圈的深度尽可能地大 。第二步：判断包围圈完成度+包围圈的深度是否≥8？如果小于则无法保证围住猫猫 ， 直接重置 。第三步：先将包围圈完成 ， 然后对应猫猫所在位置进行围堵即可获胜 。还记得开头说的天使问题吗？这个问题其实并没有被完全解决 。目前在天使的阶数k比较小 ， 比如k=2的时候 ， 数学家已经证明天使在无限大棋盘上是必败的 ， 但是对于比较大 ， 以至于任意有限阶的天使 ， 哪方能必胜这个问题尚无答案 。也许 ， 能够解决这个问题的就是聪明的你 。解决不了也没关系 ， 至少 ， 你学会如何抓住猫猫了 ， 对吧？[2]John H. Conway, The angel problem, in: Richard Nowakowski (editor) Games of No Chance, volume 29 of MSRI Publications, pages 3–12, 1996.[3]曾加的回答 - 知乎编辑：fiufa
推荐阅读
- 年假里，一只被遗忘了的小狗
- 转走学起来 如何拥有一只专属冰墩墩？
- 刘烨晒对比照送新年祝福真老虎变小猫猫
- 生龙活虎闹新春：萌虎帅虎威风虎，你pick哪一只？
- 临近过年，病房里的她收到了一只老虎仔……
- “吃鸡”新年氪金活动来袭！机械兔988一只
- 咋这么可爱！一只狗狗“享受”治疗 另一只冻得直跳jio
- 拜登家庭喜迎一只绿眼虎斑猫！盘点历任美国总统养过的宠物
- MMO怀旧盛宴搞的如何？玩家：百万人抢一只兔子
- 男友养了一只吉娃娃，我忍无可忍提出了分手