搜索算法#

• 定义：用计算机的高性能来有目的的穷举一个问题解空间部分或者所有可能情况，从而求出问题的解的一种计算机算法。

• 分类：

  • 算法角度：
    • 一般图搜索 （无信息搜索）
    • 启发式搜索（A 算法、A* 算法）
    • 不确定性搜索
  • 问题角度：
    • 博弈搜索
    • 约束满足

一般图搜索#

• 基本思想：借助图结构呈现搜索过程，将初始状态作为起点，目标状态作为终点，通过规定方式从初始状态开始不断扩展，直到扩展完所有节点或到达目标状态，最后给出一条从初始状态到目标状态的路径。
• 基本要素：初始状态、目标状态、扩展规则、耗散函数及排序规则
• 数据结构：
  • Open 表：还未扩展的节点
  • Closed 表：已经扩展的节点
  • 状态度 G：已经扩展的节点构成的当前状态

解答要点：

1. 定义状态： 状态空间 $\{S\}$ （状态编码）；初始状态 $S$；目标状态 $T$
2. 定义操作： 状态的转移规则，转移规则算子条件
3. 定义状态限制： 题目中要求不能出现的状态
4. 绘制状态空间图 按照某种搜索原则（比如BFS）遍历，每一个节点的展开都要使用操作中规定的每一个算子，对于状态限制中限制的状态要剪掉，对于重复状态要标明重复并剪掉。

启发式搜索#

• 思想：利用启发式信息（评价函数 $f$）引导算法搜索，减少搜索范围，降低问题复杂度

  • 启发信息强：降低搜索工作量，但可能找不到最优解
  • 启发信息弱：导致工作量加大，极端情况变成盲目搜索，但可能可以找到最优解

• 评价函数

  • 定义：

    $$f(n)=g(n)+h(n)$$
    • $f^*(n)$：$S-n-T$ 最短路径耗散值
    • $g^*(n)$：$S-n$ 最短路径耗散值
    • $h^*(n)$：$n-T$​ 最短路径耗散值
    • 带 $*$ 实际值，不带 $*$ 估计值

• 对比

  • A 算法：同时考虑 $g(n)$ 和 $h(n)$