启发式搜索

启发式搜索（Heuristic Search）是一种在搜索问题中使用启发信息来引导搜索过程的技术，旨在更快地找到问题的解或一个接近最佳的解。启发式搜索依赖于启发函数（heuristic function），该函数估计当前状态与目标状态之间的距离或成本，从而帮助算法在复杂的搜索空间中更有效地探索路径。

**A* 算法**

特点：A* 算法使用综合代价函数 f(n)=g(n)+h(n)，其中 g(n)是从起点到节点 n的实际代价，h(n) 是从节点 n到目标的估计代价。
优点：如果启发函数 h(n)是一致的或可接受的（即从不高估实际代价），A* 算法保证找到最优解。
缺点：在较大的搜索空间中，可能会消耗大量的内存。

启发式搜索的流程

因具体算法不同而有所差异，但总体上，启发式搜索算法遵循以下的一般步骤：

1. 初始化

定义搜索问题：明确问题的初始状态、目标状态、可能的操作（状态转换函数），以及启发函数 h(n)。
初始化开放列表（Open List）：开放列表用于存储待扩展的节点，通常以优先队列的形式实现，节点按其综合代价（例如在 A* 中为 f(n)=g(n)+h(n)排序。
初始化关闭列表（Closed List）：关闭列表用于存储已经扩展过的节点，防止重复扩展。

2. 将初始节点加入开放列表

计算初始节点 n₀ 的启发值 h(n₀)，并将其加入开放列表。

3. 循环搜索

从开放列表中取出代价最小的节点：
- 通常，取出开放列表中具有最小 f(n) 值的节点（在贪心最佳优先搜索中取 h(n)最小的节点）。
检查是否为目标节点：
- 如果该节点是目标状态，搜索结束，算法返回路径或解。
- 如果不是目标状态，将该节点加入关闭列表。
扩展当前节点：
- 生成当前节点的所有可能子节点（即所有可能的状态转换）。
评估子节点：
- 对每个子节点，计算其代价值（例如 f(n)=g(n)+h(n)。
- 检查子节点是否在关闭列表中：
  - 如果在，并且新的代价更低，更新关闭列表中的该节点。
  - 如果不在，将其加入开放列表。
更新开放列表：
- 将所有未在关闭列表中的子节点加入开放列表，或者更新已有节点的代价信息。

4. 重复步骤 3，直到找到目标节点或开放列表为空

如果找到目标节点，则返回成功路径。
如果开放列表为空，表示搜索空间已被探索完，目标不可达，搜索失败。

5. 返回结果

如果找到目标节点，算法返回从初始节点到目标节点的路径或解的构成过程。
如果未找到目标节点，返回“未找到解”的信息。

图示化流程

初始化：
    初始状态 -> 开放列表（初始节点） -> 关闭列表（空）

循环搜索：
    取出开放列表中代价最小的节点 -> 检查是否为目标节点
    |
    是目标节点 -> 结束，返回路径
    |
    否 -> 扩展当前节点 -> 生成子节点
              |
              |-- 计算子节点代价
              |-- 检查是否在关闭列表
                      |
                      |-- 是且代价较低 -> 更新关闭列表
                      |-- 否 -> 加入开放列表

重复循环直到找到解或开放列表为空

注意事项

启发函数的选择：启发函数的好坏直接影响搜索的效率和结果的最优性。合理的启发函数可以显著减少搜索空间。
开放列表和关闭列表的管理：对于大规模问题，开放列表和关闭列表的管理可能需要高效的数据结构（如堆、散列表）以提高算法效率。
循环检测：避免扩展已经访问过的节点是关键，尤其在存在环的状态空间中，这通常通过关闭列表来实现。

这个流程可以根据具体的启发式搜索算法进行调整。例如，A* 算法特别强调结合 g(n)和 h(n)来指导搜索，而贪心最佳优先搜索只关注 h(n)。你可以根据实际需要选择合适的算法。

B3625

Previous Topic

Back to Lesson

Next Topic

数据结构与算法