启发式搜索

一、贪婪最佳优先搜索算法

1、引言

无信息搜索算法，如广度优先搜索（BFS）和深度优先搜索（DFS），这些算法在探索状态空间时，除了问题定义本身提供的状态转移规则外，没有任何额外的信息来判断一个非目标节点比另一个“更有希望”接近目标。因此，它们通常是盲目地进行搜索。

为了提高搜索效率，我们引入了启发式搜索算法，也称为有信息搜索。这类算法利用与问题相关的启发式信息来引导搜索方向，优先选择那些看起来最接近目标的节点进行扩展。

贪婪最佳优先搜索算法是启发式搜索中最简单、最直观的一种。它的核心思想非常朴素：在每一步选择中，都选择那个离目标估计最近的节点进行扩展，而完全忽略到达该节点已经付出的代价。这种只顾眼前最优（看起来离目标最近）而不考虑历史代价的策略，体现了其“贪婪”的本质。

2、核心思想与评估函数

为了能够评估一个节点距离目标的“远近”，我们引入一个启发式函数（Heuristic Function），记为 $h(n)$。对于状态空间中的任意节点 $n$，启发式函数 $h(n)$ 用于估计从节点 $n$ 到达目标节点所需付出的最小代价。

需要强调的是，$h(n)$ 是一个估计值，它并不一定是真实的最小代价。一个好的启发式函数应该在计算成本较低的同时，尽可能地接近真实代价。例如，在地图导航问题中，两个城市之间的直线距离（欧几里得距离）就是一个常用且有效的启发式函数，因为它总是小于或等于实际的道路距离。

贪婪最佳优先搜索算法使用一个评估函数 $f(n)$ 来对所有待扩展的节点进行排序，并总是选择 $f(n)$ 值最小的节点。对于贪婪最佳优先搜索，其评估函数被定义为：

$$ f(n) = h(n) $$

这个定义清晰地揭示了算法的贪婪特性：它唯一关心的就是启发函数 $h(n)$ 的值，即当前节点 $n$ 离目标的估计距离。它不关心从起始节点到节点 $n$ 已经走了多远。

3、算法流程

贪婪最佳优先搜索算法通常使用一个优先队列来管理待访问的节点集合（通常称为“开放列表”或 OPEN list），队列中的节点按照其 $h(n)$ 值升序排列。同时，为了避免重复访问和陷入无限循环，还需要一个集合来记录已经访问过的节点（通常称为“封闭列表”或 CLOSED list）。

算法伪代码：

初始化：
- 创建一个优先队列 OPEN，用于存放待扩展的节点。
- 创建一个集合 CLOSED，用于存放已访问的节点。
- 将起始节点 start 放入 OPEN 中。
循环搜索：
- WHILE OPEN 不为空 DO
  1. 从 OPEN 中取出 $h(n)$ 值最小的节点 $n$。
  2. IF $n$ 是目标节点 THEN
    - 搜索成功。从节点 $n$ 回溯其父节点，构造并返回路径。
  3. 将节点 $n$ 从 OPEN 移出，并放入 CLOSED 中。
  4. FOR 节点 $n$ 的每一个后继节点 $n'$ DO
    - IF $n'$ 不在 OPEN 中 AND $n'$ 不在 CLOSED 中 THEN
      - 设置 $n'$ 的父节点为 $n$。
      - 计算 $n'$ 的启发式评价值 $h(n')$。
      - 将 $n'$ 加入 OPEN。
搜索失败：
- IF OPEN 为空 AND 还没有找到目标节点 THEN
  - 搜索失败，返回 Failure。

4、应用

让我们通过一个经典的路径规划问题来具体演示贪婪最佳优先搜索的执行过程。

问题描述：
假设我们有一个如下图所示的地图，我们的任务是从城市 $S$（起始点）找到一条路径到达城市 $G$（目标点）。每个城市（节点）到目标城市 $G$ 的直线距离（作为启发式函数 $h(n)$）已经给出。

启发式函数值 $h(n)$（到 $G$ 的直线距离）：

节点 $n$	$S$	$A$	$B$	$C$	$D$	$E$	$G$
$h(n)$	10	7	8	4	6	2	0

算法执行步骤：

步骤 0：初始化

OPEN = $\{ S(h=10) \}$
CLOSED = $\{ \}$

步骤 1：

OPEN 非空。从中取出 $h$ 值最小的节点，当前只有 $S$。
当前节点 $n=S$。$S$ 不是目标节点 $G$。
将 $S$ 从 OPEN 移至 CLOSED。
- OPEN = $\{ \}$
- CLOSED = $\{ S \}$
扩展 $S$ 的后继节点 $A$ 和 $B$。
- 节点 $A$：不在 OPEN 或 CLOSED 中。计算 $h(A)=7$。将其加入 OPEN。
- 节点 $B$：不在 OPEN 或 CLOSED 中。计算 $h(B)=8$。将其加入 OPEN。
状态更新：
- OPEN = $\{ A(h=7), B(h=8) \}$ （$A$ 的 $h$ 值更小，排在前面）
- CLOSED = $\{ S \}$

步骤 2：

OPEN 非空。从中取出 $h$ 值最小的节点 $A(h=7)$。
当前节点 $n=A$。$A$ 不是目标节点 $G$。
将 $A$ 从 OPEN 移至 CLOSED。
- OPEN = $\{ B(h=8) \}$
- CLOSED = $\{ S, A \}$
扩展 $A$ 的后继节点 $C$。
- 节点 $C$：不在 OPEN 或 CLOSED 中。计算 $h(C)=4$。将其加入 OPEN。
状态更新：
- OPEN = $\{ C(h=4), B(h=8) \}$ （$C$ 的 $h$ 值更小，排在前面）
- CLOSED = $\{ S, A \}$

步骤 3：

OPEN 非空。从中取出 $h$ 值最小的节点 $C(h=4)$。
当前节点 $n=C$。$C$ 不是目标节点 $G$。
将 $C$ 从 OPEN 移至 CLOSED。
- OPEN = $\{ B(h=8) \}$
- CLOSED = $\{ S, A, C \}$
扩展 $C$ 的后继节点 $E$ 和 $G$。
- 节点 $E$：不在 OPEN 或 CLOSED 中。计算 $h(E)=2$。将其加入 OPEN。
- 节点 $G$：不在 OPEN 或 CLOSED 中。计算 $h(G)=0$。将其加入 OPEN。
状态更新：
- OPEN = $\{ G(h=0), E(h=2), B(h=8) \}$ （$G$ 的 $h$ 值最小）
- CLOSED = $\{ S, A, C \}$

步骤 4：

OPEN 非空。从中取出 $h$ 值最小的节点 $G(h=0)$。
当前节点 $n=G$。$G$ 是目标节点！
搜索成功！

路径回溯：

$G$ 的父节点是 $C$。
$C$ 的父节点是 $A$。
$A$ 的父节点是 $S$。
最终找到的路径为：$S \rightarrow A \rightarrow C \rightarrow G$。

二、A* 搜索算法

1、引言

贪婪最佳优先搜索算法完全依赖于启发式信息 $h(n)$ 来引导搜索，虽然速度快，但既不完备也不最优。另一方面， Dijkstra 算法等则只考虑从起点到当前节点的实际代价 $g(n)$，它能够保证找到最优路径，但其搜索过程是盲目的，因为它没有利用任何关于目标位置的信息，导致搜索效率较低。

一个自然而然的问题是：我们能否将这两种方法的优点结合起来？即，既利用启发式信息来加速搜索，又考虑已经付出的代价来保证最优性？

答案是肯定的。A* 搜索算法正是为此而生。它通过一个精巧的评估函数，完美地平衡了“已付出的代价”和“对未来的估计”，成为路径搜索中最著名、最广泛应用的算法之一。A* 算法可以被看作是 Dijkstra 算法的扩展，增加了启发式引导；也可以看作是贪婪最佳优先搜索的改进，增加了对历史代价的考量。

2、核心思想与评估函数

A* 算法的核心在于其独特的评估函数 $f(n)$。对于状态空间中的任意节点 $n$，A* 算法的评估函数定义为：

$$ f(n) = g(n) + h(n) $$

其中：

$g(n)$: 是从起始节点到节点 $n$ 的实际最小代价。这与 Dijkstra 算法中的考量完全一致。
$h(n)$: 是从节点 $n$ 到目标节点的估计代价，即我们已经熟悉的启发式函数。

因此，评估函数 $f(n)$ 的含义可以理解为：从起始节点出发，经过节点 $n$，最终到达目标节点的估计总代价。

A* 算法在每一步选择中，都会优先扩展 OPEN 列表中 $f(n)$ 值最小的节点。这个选择策略非常高明：

如果只看 $g(n)$，算法退化为 Dijkstra 算法。
如果只看 $h(n)$（即令 $g(n)=0$），算法退化为贪婪最佳优先搜索。

通过同时考虑 $g(n)$ 和 $h(n)$，A* 算法能够在多个看似有希望的路径之间做出更明智的权衡。它不会像贪婪算法那样，被一个初始 $h(n)$ 值很小但实际路径成本 $g(n)$ 迅速增加的“陷阱”所迷惑；也不会像 Dijkstra 算法那样，漫无目的地向所有方向扩展，而是会优先探索那些预估总成本最低的方向。

3、算法流程

A* 算法的流程与贪婪最佳优先搜索非常相似，同样使用优先队列 OPEN 和集合 CLOSED。关键区别在于优先队列的排序依据从 $h(n)$ 变成了 $f(n) = g(n) + h(n)$。此外，A* 算法还需要处理一个重要细节：当发现一条到达某个节点的新路径比旧路径更优时，需要更新该节点的 $g(n)$ 值和父节点信息。

算法伪代码：

初始化：
- 创建一个优先队列 OPEN，用于存放待扩展的节点，按 $f(n)$ 值升序排列。
- 创建一个集合 CLOSED，用于存放已访问的节点。
- 创建起始节点 start，设置其 g(start) = 0，计算 f(start) = g(start) + h(start) = h(start)。
  - 将起始节点 start 放入 OPEN 中。
循环搜索：
- WHILE OPEN 不为空 DO
  1. 从 OPEN 中取出 $f(n)$ 值最小的节点 $n$。
  2. IF $n$ 是目标节点 THEN
    - 搜索成功。从节点 $n$ 回溯其父节点，构造并返回路径。
  3. 将节点 $n$ 从 OPEN 移出，并放入 CLOSED 中。
  4. FOR 节点 $n$ 的每一个后继节点 $n'$ DO
    - IF $n'$ 在 CLOSED 中 THEN
      - 跳过，因为已经找到了从起点到 $n'$ 的最优路径。
    - 计算从起点经过 $n$ 到达 $n'$ 的新路径代价：
      $$ \text{new\_g} = g(n) + \mathrm{cost}(n, n') $$
      其中 $\mathrm{cost}(n, n')$ 是从 $n$ 到 $n'$ 的边代价。
    - IF $n'$ 不在 OPEN 中 OR $\text{new\_g} < g(n')$ THEN
      - 设置 $n'$ 的父节点为 $n$。
      - 更新 $n'$ 的代价：$g(n') = \text{new\_g}$。
      - 计算 $n'$ 的评估值：$f(n') = g(n') + h(n')$。
      - IF $n'$ 不在 OPEN 中 THEN
        将 $n'$ 加入 OPEN。
      - ELSE
        （在 OPEN 中）更新 $n'$ 的优先级。
搜索失败：
- IF OPEN 为空 AND 还没有找到目标节点 THEN
  - 搜索失败，返回 Failure。

老官童鞋gogo @ laoguanTX

最新文章

标签云

归档

分类

最近回复

一、贪婪最佳优先搜索算法

1、引言

2、核心思想与评估函数

3、算法流程

4、应用

二、A* 搜索算法

1、引言

2、核心思想与评估函数

3、算法流程

添加新评论

目录

目录