我已经实现了一个 A* 算法来解决 15 谜题。我进行了一项研究，以寻找一些可行或可接受的启发式方法，寻找一个快速的解决方案，我发现使用 4*Manhattan 距离作为启发式方法总是可以在不到一秒的时间内解决任何 15 个难题。我试过这个并且有效地工作。我试图找到答案，但我找不到。
任何人都可以解释这一点？
问问题
970 次
1 回答
3
4* 曼哈顿距离是不可接受的启发式算法，这使得算法首先表现得“更接近”贪婪的最佳算法（算法仅根据启发式函数选择要开发的节点）。这使得算法有时更喜欢解决方案的深度和探索而不是广度和最优性。
这个想法类似于A*-Epsilon中发生的情况，您允许 A* 在一定范围内开发非最优节点以加速您的算法，实际上 - 我怀疑您会得到相同（或类似的结果）如果您以曼哈顿距离和epsilon = 3. （如果我是正确的，这将使您在修改后的启发式中找到解决方案4*OPTIMAL，其中 OPTIMAL 是最佳路径的长度）
于 2012-10-25T19:07:35.203 回答