在超级马里奥银河 2 中寻找最短路径的算法

Question

在超级马里奥银河2中，游戏的最后一关有一个部分，你必须踩下开关，踩下开关会改变颜色。为了在关卡中取得进步，必须更改每个开关。当你踩到它时，颜色只会改变一次。澄清一下，如果你踩到它，颜色就会改变。要再次更改颜色，您必须踩下不同的开关并返回原来的开关。

这是我正在谈论的视频：https://www.youtube.com/watch?v=dpGjKEt8wmw#t=34

我想知道我可以应用什么路径查找算法来找到通过这部分的最快方法。我马上想到了 A*，但我不认为它适用，因为我需要击中每个节点并且目标节点与源节点相同。

Answer 1

如果我没理解错的话，你想每个方块都踩一遍，然后所有的方块都踩一遍。

因此，如果您将其视为一个图，每个块都由一个顶点表示（并且每对相邻块 - 水平、垂直或对角线 - 由边组成），您需要访问每个顶点一次并且return 到源顶点（即形成一个循环）。 但那是一个 NP 完全的哈密顿循环（你需要动态规划来解决它）。