Appearance
搜索是人工智能求解问题的重要手段，通过系统地遍历状态空间来寻找问题的解。本笔记梳理搜索的基本概念、状态空间表示、盲目搜索与启发式搜索两大类策略，以及A*算法的核心思想。
搜索的基本概念
搜索的主要过程
- 从初始状态或目的状态出发，作为当前状态
- 扫描操作算子集，将适用当前状态的操作算子作用于当前状态，得到新状态，并建立指向父结点的指针
- 检查新状态是否满足结束状态：满足→得到解，沿指针反向给出解答路径；否则→新状态作为当前状态，继续搜索
搜索策略分类
| 类型 | 定义 | 特点 |
|---|---|---|
| 盲目搜索 | 不具有特定问题信息，按固定步骤搜索 | 效率低，穷举 |
| 启发式搜索 | 考虑领域知识，动态确定操作步骤，优先选择较适合的算子 | 效率高，减少不必要的搜索 |
启发信息
用来简化搜索过程的、有关具体问题领域特性的信息。
状态空间表示法
状态空间四元组
状态空间可以用四元组表示：(S, O, S₀, G)
| 符号 | 含义 |
|---|---|
| S | 状态集合 |
| O | 操作算子的集合 |
| S₀ | 初始状态（S的非空子集） |
| G | 目标状态（具体状态或路径信息描述） |
状态空间的图描述
状态空间可用有向图描述：结点=问题的状态，弧=状态间的关系（求解步骤），根结点=初始状态。
一般搜索过程
从初始状态出发，不停地、试探地寻找路径，直到到达目标或"死胡同"。遇到不可解结点时回溯到最近的父结点，查看是否有其他子结点未扩展，若有则继续搜索；找到目标则成功退出，返回解题路径。
盲目搜索
在不具有对特定问题的任何有关信息的条件下，按固定步骤（依次或随机调用操作算子）进行的搜索。
常见策略：
- 广度优先搜索（BFS）：逐层扩展，保证找到最短路径
- 深度优先搜索（DFS）：沿一条路径深入，空间效率高
- 回溯策略：DFS遇到死路时回溯
启发式搜索
考虑特定问题领域可应用的知识，动态地确定调用操作算子的步骤，优先选择较适合的操作算子，尽量减少不必要的搜索，以求尽快地到达结束状态。
A*算法
定义：利用评价函数 f(n) 对边界上的节点排序，每次选择 f(n) 最小的节点 n 去搜索。
评价函数：
f(n) = g(n) + h(n)- g(n)：从初始节点到节点 n 的实际代价
- h(n)：从节点 n 到目标节点的启发式估计代价
启发式函数可采纳性：假设 h*(n) 是从节点 n 到目标的最小真实代价，若 h(n) ≤ h*(n)，则启发式函数是可采纳的，A*算法保证找到最优解。
实践应用
- 八数码、迷宫求解等经典搜索问题
- 路径规划（导航）
- 游戏AI决策
- 自动规划
一句话总结
搜索的本质是遍历状态空间，四元组 (S, O, S₀, G) 是标准写法；盲目搜索穷举，启发式搜索靠 h(n)，A 用 f(n)=g(n)+h(n)，h(n) ≤ h(n) 才保证最优解。**