如果启发式函数H不是单调的，那么A *算法是什么？

作者: 句号了
发布时间: 2024-07-21 04:57:06 (6天前)
转自：

3 条回复

0#
回复此人
喜欢一个人丶 | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”> <P> 假设启发式函数功能仍然存在 <a href="http://en.wikipedia.org/wiki/Admissible_heuristic" rel="nofollow"> 受理 </A> - A *算法可以正常工作。 </p> <P> 但是，对于非单调启发式函数，您可能需要更新已经“关闭”的节点，并且应该允许此行为。 </p> </DIV>

编辑
1#
回复此人
老夫的少女心吖 | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”> <P> 如果是的<strong> 树搜索 </强> 它不需要保持一致是最佳的。相反，如果它是一个的<strong> 图搜索 </强> 只有在启发式是可接受且一致的情况下，A *才是最佳的。 </p> <P> 在此图片中，您可以看到不一致启发式的示例：A *算法找不到正确的路径。 </p> <P> <img src =“https://i.stack.imgur.com/bhxmA.png”alt =“example”/> </p> <P> 也许你可以像@amit那样修改标准的A *算法，但在这种情况下你需要考虑一个已经关闭的状态，所以搜索不是最优的。它可能会找到最佳路径，但它会比具有一致启发式的解决方案扩展更多节点，因此它将是次优的。 </p> </DIV>

编辑

登录后才能参与评论