AO* 算法是如何工作的？

1. 简介

最佳优先搜索（Best-First Search）是一类用于在图中寻找从起点到目标节点最短路径的算法，它利用启发式信息进行指导。AO 算法就是这类算法的一个代表。*

这类算法不能与广度优先搜索混淆，后者只是一个具体算法，而不是一个算法类别。此外，最佳优先搜索是有信息的（informed），意味着它事先知道节点间的启发式距离。而广度优先搜索则是无信息的（uninformed）。

2. AO* 算法概述

AO 算法基于 AND-OR 图结构，将复杂问题分解为更小的子问题逐一解决。*

AND 分支表示多个子任务必须同时完成才能达成目标；
OR 分支则表示只需完成其中一个子任务即可达成目标。

如下图所示：

AO* Algorithm

在这个例子中，AND 分支下的两个任务通过 AND-ARCS 连接，必须都完成才能拥有孩子；而 OR 分支则只需通过“收养”一个任务即可实现目标。

通常，图中每个节点都可能有多个 OR 和 AND 分支，其中每个 AND 分支可能连接多个子节点。

3. AO* 的工作原理

AO* 的核心公式是：
$$ F(n) = G(n) + H(n) $$
其中：

**G(n)**：从起点到当前节点的实际代价；
**H(n)**：从当前节点到目标节点的启发式估计代价；
**F(n)**：从起点到目标节点的总估计代价。

我们通过一个例子来逐步说明 AO* 是如何工作的：

lowest cost path

图中每条边的代价为 1，节点旁边的数字是该节点到目标节点的启发式代价（目标节点未画出）。

3.1. 正向传播

我们从节点 A 出发，计算 OR 和 AND 分支的代价：

OR 分支 A→B：
$ P(A-B) = G(B) + H(B) = 1 + 5 = 6 $
AND 分支 A→C→D：
$ P(A-C-D) = G(C) + H(C) + G(D) + H(D) = 1 + 3 + 1 + 4 = 9 $

由于 A→B 路径代价更低，我们选择继续探索该路径。

⚠️ 注意：此时不能直接认为找到了最优路径，因为启发式仅计算了一层，图中还存在更深的结构可能改变最终结果。

3.2. 到达最底层并反向传播

继续从 B 探索其子节点 E 和 F：

B→E：$ P(B-E) = 1 + 10 = 11 $
B→F：$ P(B-F) = 1 + 11 = 12 $

选择代价更低的 B→E 路径。

此时已到达图的最底层，没有更深节点可供探索，于是开始反向传播（backpropagation），更新上层节点的启发值：

更新 H(B) 为 11，因此 A→B 的代价变为 $ 1 + 11 = 12 $

此时比较发现 A→C→D（代价 9）比更新后的 A→B（代价 12）更低，因此应继续探索该路径。

✅ 小结：AO* 会不断进行前向探索和反向更新，直到路径代价不再变化。

3.3. 修正从起点出发的路径

继续探索 A→C→D 路径：

C 的 OR 分支：P(C-G) = 1 + 3 = 4
C 的 AND 分支：P(C-H-I) = 1 + 0 + 1 + 0 = 2
所以更新 H(C) = 2
D 的路径：P(D-J) = 1 + 1 = 2
所以更新 H(D) = 2

最终更新后的 A→C→D 总代价为：
$ P(A-C-D) = 1 + 2 + 1 + 2 = 6 $

此时 A→C→D 的代价（6）仍低于 A→B 的代价（12），因此最优路径为 A→C→D。

4. 伪代码

下面是 AO* 算法的伪代码，展示了其核心流程：

algorithm AOStar(Graph, StartNode):
    // INPUT
    //    Graph = the graph to search
    //    StartNode = the starting node
    // OUTPUT
    //    The minimum cost path from StartNode to GoalNode

    CurrentNode <- StartNode

    while there is a new path with lower cost from StartNode to GoalNode:
        calculate the cost of path from the current node to the goal node
          through each of its successor nodes

        if the successor node is connected to other successor nodes by AND-ARCS:
            sum up the cost of all paths in the AND-ARC
            return the total cost
        else:
            calculate the cost of the single path in the OR side
            return the single cost

        find the minimum cost path

        CurrentNode <- Successor Node Of Minimum Cost Path

        if CurrentNode has no successor node:
            do the backpropagation and correct the estimated costs
            CurrentNode <- StartNode
            return CurrentNode, New estimated costs
        else:
            return null

    return The minimum cost path

5. 算法性能分析

AO 不是最优的*：一旦找到一个解就停止，不会继续探索其他可能更优的路径。
但它是完备的：只要存在解，就能找到；不会陷入无限循环。
AND 分支有助于节省内存：将多个子任务合并处理，减少了重复搜索的开销。

时间复杂度：$ O(b^m) $，其中 b 是分支因子，m 是搜索树的最大深度。
空间复杂度：多项式级别。

6. 总结

AO* 是一种基于 AND-OR 图结构的最佳优先搜索算法，擅长将复杂问题分解为多个子问题并行处理。这种“分而治之”的策略有效降低了复杂度，但也牺牲了最优性。

虽然 AO* 不能保证找到全局最优解，但在实际应用中（如路径规划、游戏 AI、任务调度）仍具有很高的实用价值。

Persistence

REST

Security