A* search & Heuristics

Week 2 A* Search & Heuristic¶

1.4 Informed Search | Introduction to Artificial Intelligence

1.5 Local Search | Introduction to Artificial Intelligence

Heuristic：似乎翻译成"启发式的".

Heuristic function: 启发式函数$h(n)$，用于给出当前到达目标的预测成本.

回忆一下UCS，这是一种基于当前累计成本的搜索方法。优先选择使累积成本函数$g(n)$最小的路径；而Greedy Search是基于Heuristic function给出的搜索方法，优先选择使启发函数$h$下降最快的路径.

这里引入的A* Search的定性是a combination of greedy search and UCS，定义了综合函数$f(n) = g(n)+h(n)$，每次优先选择其中$f(n)$最小的那条路径进行搜索.
A* isn't optimal，即非最优化的失效情形：如果heuristic远高于实际所需最低成本，那么不可能成功.

相对地，if A is optimal, then $h(n)$ is admissible, fulfilling the rule that: $$0 \leq h(n) \leq h^*(n)$$，其中$h^(n)$是当前位置离目标实际上的最短路线距离.

找到合适的heuristics是A*算法应用的核心.

最优性定理及证明：A* Search is optimal when $h(n)$ is admissible.

首先假设有两个目标$A, B$，其中$A$是主要的目标，$B$是次要目标，即$f(A)<f(B) \Longrightarrow g(A) < g(B)$.

现在假设fringe上有一个元素$n$，则由$$\begin{cases} f(A) = g(A) + h(A) = g(A) \\ f(n) = g(n) + h(n) \leq g(n)+h^*(n) = f(A)\end{cases} \Longrightarrow f(n) \leq f(A) < f(B)$$

于是可以知道$A$一定在$B$之前被遍历到，所以是optimal的.

A*搜索的伪代码：

function A*-GRAPH-SEARCH(problem, frontier)
    reached ← an empty dict mapping nodes to the cost to each one
    frontier ← INSERT((MAKE-NODE(INITIAL-STATE[problem]),0), frontier)
    while not IS-EMPTY(frontier):
        node, node.CostToNode ← POP(frontier)
        if problem.IS-GOAL(node.STATE): return node
        if node.STATE not in reached or reached[node.STATE]  node.CostToNode:
            reached[node.STATE] = node.CostToNode
            for child-node in EXPAND(problem, node):
                frontier ← INSERT((child-node, child-node.COST + CostToNode), frontier)
    return False

Dominance定义： If heuristic $a$ is dominant over heuristic $b$, then the estimated goal distance for a is greater than the estimated goal distance for b for every node in the state space graph. Mathematically,

\[\forall n, h_a(n) \geq h_b(n)\]

这里$a$对$b$形成了dominant的关系，因为$a$是接近$h^*$的一种刻画.

平凡启发式函数：The trivial heuristic is defined as $h(n)=0$, and using it reduces A* search to UCS.

半格结构：
```
exact (精确启发式)
        |
    max(h_a, h_b) (最大值组合)
        /     \
    h_a      h_b (具体的启发式函数)
    |        /
    h_c      /    
    \      /
        zero (平凡启发式)
```
这里给我们指出了一个方法，对于某一问题的多个方案所构建的$h_1,h_2,\cdots,h_n$，取其中的max，仍然是heuristic的，我们可以通过这样的方法去逐步趋近exact。
A* Search的失效和consistent heuristic的引入：

现在的约束条件仍然存在不足，比如下面的情形中，A* Search就失效了。所以我们还需要引入新的概念consistent heuristic function：

如果对某个graph，其中所有的节点$n$都满足：$$h(n) \leq c(n,n_{child})+h(n_{child})$$，则称这是一个consistent heuristic function.

证明：略. easy

让Claude 4.0 Sonnet来总结一下这四种搜索：

Tips

DFS（深度优先搜索）

DFS采用"一条路走到黑"的策略。从起始节点开始，沿着一个分支尽可能深入，直到无法继续为止，然后回溯到上一个节点，探索其他分支。

实现方式：通常使用栈（或递归调用栈）来记录路径

时间复杂度：$O(V+E)$，其中$V$是顶点数，$E$是边数

特点：内存占用相对较少，但不保证找到最短路径
BFS（广度优先搜索）

BFS采用"逐层扩展"的策略。从起始节点开始，先访问所有相邻的节点，然后再访问这些节点的相邻节点，形成一圈一圈向外扩展的模式。

实现方式：使用队列来存储待访问的节点

时间复杂度：$O(V+E)$

特点：在无权图中能保证找到最短路径，但内存占用较大
Greedy（贪心算法）

贪心算法在每一步都选择当前看起来最好的选项，基于某种启发式函数做出局部最优决策。在路径搜索中，通常选择距离目标最近的节点作为下一步。

实现方式：通常使用优先队列，按照启发式函数值排序

时间复杂度：取决于具体实现，一般为$O(V \log V)$

特点：速度快，但不保证找到最优解
A*算法

A*结合了Dijkstra算法的准确性和贪心算法的效率。它使用评估函数$f(n) = g(n) + h(n)$，其中$g(n)$是从起点到当前节点的实际代价，$h(n)$是从当前节点到目标的启发式估计代价。

实现方式：使用优先队列，按$f(n)$值排序，维护开放列表和关闭列表

时间复杂度：取决于启发式函数的质量，最坏情况为$O(b^d)$

特点：当启发式函数满足可接受性条件时，能保证找到最优解
应用场景对比
- DFS：适合深层搜索、拓扑排序、强连通分量查找
- BFS：适合最短路径问题、层序遍历
- Greedy：适合对速度要求高、对最优性要求不严格的场景
- A*：适合游戏AI、路径规划等需要在效率和最优性之间平衡的应用

这四种算法各有优势，选择哪种取决于具体的问题需求和约束条件。