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

Question

3

我尝试找到如果启发式函数不满足单调性条件的情况下A *算法将是什么，其中

对于每个存在边缘连接的u和v，h(u) <= e(u,v)+h(v)

是单调性的条件，其中h是启发式函数，u和v是搜索图中的顶点，函数e给出u和v之间的边缘成本（搜索图是无向的）。然而维基百科(here)及其他来源如Norvig的人工智能书籍并没有给出这种情况下的算法。

有没有一个好的资源来学习这个？伪代码会很棒!

此外，我不希望通过将非单调启发式函数转换为单调函数来解决此问题。

- piedpiper

4

我不知道是谁提出了关闭投票，但这不是一个离题的问题。 - Bartek Banachewicz

我在理解所期望的答案类型方面遇到了问题。 "Slower" 看起来像是一个有效的答案。 - MSalters

我正在尝试理解适用于该情况的算法。目前，我不担心算法的时间复杂度。 - piedpiper

2个回答

1

在树搜索中，不需要保持一致性就能达到最优。但是，在图搜索中，只有当启发式函数是可接受且一致的情况下，A*算法才是最优的。在这张图片中，你可以看到一个不一致的启发式函数的例子：A*算法无法找到正确的路径。

example

也许你可以像@amit所说的那样修改标准的A*算法，但在这种情况下，你需要考虑已经关闭的状态，以便搜索不会是最优的。它可能会找到最优路径，但它将扩展比具有一致启发式的解决方案更多的节点，因此它将是次优的。

- drolando

我认为这取决于您认为什么是“标准A *算法”。个人认为，允许更新关闭节点的算法是标准算法，而依赖单调启发式的算法则是A *的特例（尽管是常见的特例）。维基百科文章总是小心地提到它是指一般的A *还是带有单调启发式假设的A *。 - NateW

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- amit · Accepted Answer

假设启发式函数仍然是可容忍的（admissible），A*算法会正常工作。

但是，对于非单调的启发式函数，您可能需要更新已经“关闭”的节点，并允许这种行为。