search - 15 道益智游戏的非最优解

Question

我正在应用曼哈顿启发式的 A*（和 IDA*）搜索来寻找 15 谜题的解决方案。

利用我不想要问题的最佳解决方案这一事实，由于当前例程太慢，我如何加快搜索速度。

Answer 1

好吧，这并不完全是一个解决方案，但它可能会有所帮助。一旦我一直在为一个与迷你游戏具有相同谜题的 HOG 游戏工作，它变得更容易产生问题，而不是找到解决方案。

我的意思是，我们可以通过根据规则随机移动“窗口”来将已解决的难题变成未解决的难题。并记录每个字段位置以供将来使用。然后我们让用户玩一会儿，如果她放弃了，我们可以通过在用户和我们的日志中找到共同的位置来轻松地为她解决一个难题。我们只是通过用户日志回放到共同位置，然后通过我们的日志从它回到解决的位置。

当然，这是一个 hack 而不是真正的解决方案，但它在 gamedev 中运行良好。而且不仅适用于这个特定的游戏。大多数重新定位难题都可以通过这种方式“解决”。