经典游戏"围绕猫"算法？

Question

我想知道什么算法让猫"聪明"？猫如何决定采取哪个方向？

我想到的一个解决方案是广度优先搜索并沿着最短的退出路径前进.

我在这里好奇.:-)

Answer 1

我相信它只是使用Djikstra 的算法（或等效算法），即~~未加权的~~单源最短路径算法非常擅长解决这个特定问题。

通过玩前面的几个位置，猫很容易被困住——“智能”很容易被愚弄:)猫似乎没有考虑到在潜在路径中在它前面玩的非阻塞瓷砖，这让我相信它是只是一个简单的未加权距离计算。

当猫被困时，它似乎会随机选择一个方向，这也可能发生在领带上。

通过给某些图块（例如那些与阻挡图块相邻的图块）添加重量，猫可能会变得“更聪明”。

快乐编码。

首先，Dijkstra 算法不是未加权的最短路径算法，它在您的链接中是这样说的。其次，您不需要 Dijkstra 或 A*，因为这个问题简化为未加权图问题。虽然不太相关，但很有趣：只要猫距离出口最多 4 步，如果你玩得对，你就永远无法困住它。再多一点（这是链接游戏的情况），无论猫做什么，你总是可以赢。这就是为什么你认为你打败了“智力”——事实上，它在前几次愚弄了你，因为你总是可以获胜。 (5认同)