现实实例

• 地图导航
• 迷宫问题
• NPC 寻路
• ……

定义

从解空间中 搜索到与问题相对应 满足一定约束条件的 最佳答案，寻找从初始到结束的一条最优路径。

搜索的要素

• 从起点到终点的 状态（State） 序列
  • 如果搜索可完成，那么 状态 个数应当是有穷的（有穷状态机）
  • 如果状态过多，也可以算作无解
• 每一时刻可以执行的 动作（Action）
• 执行的动作使得 状态转移（State transition）
• 需要计算经过的 路径（Path） 的 代价（Cost），评估是否最优
• 判断是否到达终点的 目标测试（Gaol test）*

搜索问题的统一建模

需要把搜索问题建模为统一的、计算机可以理解的类型，使得搜索算法普适应用

搜索问题同常被抽相乘 搜索树（Search Tree） 或者 状态圈（State Graph）

搜索树

数据结构参考：

interface Node {
    index: number,
    data: string,
    parent: number
}

let tree: Node[] = [];

剪枝

构建搜索树的时候，删除路径中已经存在的状态。

常用搜索策略：

• 可行性剪枝
• 最优性剪枝
• 排除等效冗余
• 记忆化搜索（？）

搜索策略

深搜

优先检索分支下的子节点

特点：可以边搜索边剪枝，消耗资源比较少

缺点：有可能在剪枝的时候把最优解剪掉了，导致搜索结果不是最优。

广搜

优先检索同级节点

动态规划

通过利用最优子结构和重叠子问题的性质，将指数级复杂度的搜索算法优化为多项式时间复杂度

• 最优子结构

问题最优解包含其子问题的最优解（就是说，需要找子结构的最优解）

• 重叠子问题

在递归地求解问题时，相同的子问题会被重复计算很多次。

最典型的：斐波那契数列递归计算。

在迷宫问题下的子问题

任意位置到终点（S9）的最短路径。

每一个子问题都是相似的，且可递归。

所以从终点出发，反向递归搜索最短路径。

一致代价搜索

启发式搜索

问题复杂度很高时适用。

更新日志

2025/10/16 23:11

查看所有更新日志

• ef372-docs: 添加人工智能导论于 2025/10/16