A*算法解决8瓦块滑动拼图的时间到了

Question

只是想知道有没有人能帮我解决一些我目前正在为uni工作的代码。这是一个我正在编写的滑动瓦片拼图，我已经实现了一个带有曼哈顿距离启发式的A*算法。目前，对于某些配置，它解决难题的时间可以从几毫秒到大约12秒不等。我想知道的是，这个时间范围是否是我应该期待的？

我以前从来没有真正做过任何人工智能，我必须在飞行中学习这一点，所以任何帮助都将不胜感激。

Answer 1

我想知道的是，这个时间范围是不是我应该期待的？

仅从您提供的信息就很难理解这一点。如果你能描述你是如何实现A*的，或者如果你对你的应用程序进行了概要分析，并且在特定的缓慢领域需要帮助，那将会很有帮助。

有一件事需要注意，这可能会加快你的平均求解时间:任何n块拼图的起始位置的一半永远不会导致解，所以你可以立即非常快速地排除某些配置。例如，，你不能解决像这样的8块拼图：

1 2 3 
4 5 6
8 7 .

要了解原因，请注意，因为空格必须回到它开始的位置，所以“向上”/“向下”移动的总数必须相等，“左”/“右”移动的总数也是如此。这意味着移动的总数量必须是偶数。

但是这里的7/8转置离起始拼图只有一步之遥，没有改变空白位置！所以这个难题是无法解决的。(但是，如果我们进行了两次换位，那么它将再次可解。)

Answer 2

就像你应该知道，你不能期望任何一般的时间。这取决于代码本身，特别是在deap中，你的实现会遍历树，而且你的代码是否可以利用处理器特性的优势。

为了调试，我会保存或打印出来(但这需要时间！)你在你的树的哪个层次。

还要记住权重是非常重要的。例如：

123
4 6 <- your final state
789

           213                               1 3
To change  4 6  is much more expensive than  426
           789                               789

我希望这能有所帮助。

Answer 3

显然，这不仅取决于您的硬件，还取决于您的实现。然而，这不是一个很好的性能衡量标准:您想要做的是确定启发式方法的有效分支因子，而不是其他非启发式方法的实际分支因子。

我不想说太多，因为这是一个家庭作业问题，但如果没有记错的话，Russel和Norvig在滑动拼图本身的上下文中转换了这一点……也许是第三章？(我的R+N不在手边。)