我已经实现了一个 A* 算法来解决 15 字谜题。我进行了一项研究，以寻找一些可行或可接受的启发式方法，寻找快速解决方案，我发现使用 4*Manhattan 距离作为启发式方法总能在不到一秒的时间内解决任何 15 个难题。我试过了，效果很好。我试图为此找到答案，但找不到。
谁能解释一下？
最佳答案
4* 曼哈顿距离不是可接受的启发式算法，这使得算法首先表现得“更接近”贪婪(算法仅根据启发式函数选择要开发的节点)。这使得算法有时更喜欢解决方案和探索的深度，而不是广度和最优性。
这个想法类似于 A*-Epsilon 中发生的事情，您允许 A* 在一定范围内开发非最佳节点以加速您的算法，实际上 - 我怀疑您会得到相同(或相似的结果)如果您使用曼哈顿距离和 epsilon = 3 运行 A*-Epsilon。 (如果我是正确的，这使得您在修改后的启发式中找到的解决方案受 4*OPTIMAL 限制，其中 OPTIMAL 是最佳路径的长度)
关于algorithm - 如果我使用 4xManhattan 距离作为 15-Puzzle 的启发式算法，为什么 A* 更快，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/13075199/