我已经实现了 A* 算法来解决 15 个难题。我进行了一项研究，寻找一些可行或可接受的启发法，寻找快速解决方案，我发现使用 4*曼哈顿距离作为启发法总是可以在不到一秒的时间内解决任何 15 个谜题。我尝试过这个并且有效。我试图找到答案，但找不到。
任何人都可以解释这一点吗？
4* 曼哈顿距离不是可接受的启发式，这使得算法首先“更接近”贪婪最佳（算法仅根据启发式函数选择要开发的节点）。这使得算法有时更喜欢解决方案的深度和探索而不是广度和最优性。
这个想法类似于发生的事情A*-埃普西隆 http://en.wikipedia.org/wiki/A%2a_search_algorithm#Bounded_relaxation，您允许 A* 在一定范围内开发非最佳节点，以加速您的算法，实际上 - 我怀疑如果您使用曼哈顿距离运行 A*-Epsilon ，您会得到相同（或类似的结果）epsilon = 3。 （如果我是正确的，这使得您在修改后的启发式中找到的解决方案由4*OPTIMAL，其中 OPTIMAL 是最佳路径的长度）
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
