人工智能 - A* 是否具有可接受但不一致的启发式最优？ - 吾爱随笔录

人工智能搜索启发式一个明星可接受的启发式一致启发式

2021-10-26 10:38:17

我知道，在树搜索中，可接受的启发式意味着 $A*$ 是最优的。我对此的直观看法如下：

让 $P$ 和 $Q$ 是来自任何相应节点的两个成本 $p$ 和 $q$ 到目标。认为 $P<Q$ . 让 $P'$ 是一个估计 $P$ . $P'\le P \Rightarrow P'<Q$ . 根据统一成本搜索，路径通过 $p$ 必须探索。

我不明白的是，为什么可接受启发式的想法不适用于“图形搜索”。如果启发式是可接受但不一致的，这是否意味着 $A*$ 不是最优的？您能否提供一个导致非最佳解决方案的可接受启发式示例？

1个回答

这取决于您所说的最佳。

只要启发式是可接受的，A* 总是会找到最优解（即算法是可接受的）。（请注意，admissible 的定义是重载的，并且对于算法和启发式算法的含义略有不同。）
如果您谈论由 A* 扩展的节点集，那么即使在启发式不一致的情况下，它也会将最小的节点集扩展到平局。
如果您谈论扩展次数，则 A* 不是最佳的。A* 最多可以执行 $2^N$ 的扩展 $N$ 具有不一致启发式的状态。这个结果来自Martelli, 1977。
算法 B 有最坏情况 $N^2$ 扩展和预算图搜索（BGS）有最坏的情况 $N \log C$ ，在哪里 $C$ 是最优解成本。

您可以在此处看到一个演示，该演示显示了 A* 的最坏情况性能以及 BGS 的性能：

其它你可能感兴趣的问题