我已经实现了一个用于解决15数码难题的A*算法。我进行了一些研究，寻找可行或可接受的启发式方法，以寻求快速解决方案，并发现使用4倍曼哈顿距离作为启发式方法总是可以在不到一秒钟内解决任何15数码难题。我尝试了这个方法，它确实有效。我试图找到答案，但我找不到。有人能解释一下吗？
为什么如果我将4倍曼哈顿距离用作15-Puzzle的启发式，A*算法会更快？
4
- Raúl Otaño
2
你也改变了成本函数吗？ - Fred Foo
我建议您命名您尝试过的其他启发式算法。 - Qnan
1个回答
3
4倍曼哈顿距离不是可接受的启发式算法，这使得算法的行为更接近贪婪最佳优先（其中算法仅基于启发式函数选择要开发的节点）。这使得算法有时会更喜欢探索深度解决方案而不是广度和最优性。
这个想法类似于A*-Epsilon中发生的情况，其中您允许A*开发某些非最优节点，直到一定限制以加速您的算法，实际上 - 我怀疑使用曼哈顿距离和
这个想法类似于A*-Epsilon中发生的情况，其中您允许A*开发某些非最优节点，直到一定限制以加速您的算法，实际上 - 我怀疑使用曼哈顿距离和
epsilon = 3运行A*-Epsilon将获得相同的（或类似的）结果。 （如果我是正确的，那么您在修改后的启发式中找到的解决方案将被4*OPTIMAL限制，其中OPTIMAL是最优路径的长度）- amit
2
是的，这不是一个可接受的启发式。我还有一个问题，我在其他的拼图游戏中尝试了这个启发式（4*MD）（如6x6或5x5），但效果并不相似，这意味着我需要为每个特定的拼图游戏找到一个ε值吗？是否还有一种更快的启发式也是可接受的？ - Raúl Otaño
1@RaulOtaño：最快的可接受启发式算法是
h*（v）-它可以准确地预测到达目标的成本，然而-如果您已经拥有了它-您就不需要A*算法，贪婪最佳优先搜索启发式算法也可以轻松地为您提供最短路径！ - amit网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接