高级人工智能期末复习：搜索算法

传统基础搜索

这类算法只知道'初始状态、目标状态、能做什么动作'，不知道'当前状态离目标多远'，像瞎摸一样找路。

深度优先搜索 DFS

不具备完备性、最优性，但空间复杂度良好

• 优点：空间复杂度低。只需要记当前路径上的节点，不用记所有探索过的节点（比如迷宫里只记'现在在哪、走过哪些岔路'）。
• 缺点：① 不完备：如果迷宫有无限长的路，会一直走下去，永远找不到出口；② 不最优：可能找到一条绕远的路就停了，没机会找更短的。

广度优先搜索 BFS

具备完备性、最优性，但空间复杂度很高

• 优点：① 完备性：只要有出口，一定能找到（不会漏层）；② 最优性：如果每步代价相同（比如每段路距离一样），找到的一定是最短路径（步数最少）。
• 缺点：空间复杂度极高！要记所有已经探索过的'层'，节点多了会占满内存（比如迷宫大了，要记上百个岔路）。

改进搜索

迭代深入搜索

结合 DFS 的空间优势和 BFS 的时间优势，先做'深度限制为 1 的 DFS'（只走 1 步就回头），没找到就做'深度限制为 2 的 DFS'，依次增加深度，直到找到目标。

代价一致搜索（Dijkstra 算法）

找路时，不看走了多少步，只看从起点到当前节点的'总距离'，总距离最小的节点先探索。比 BFS 更通用，适合'每步代价不同'的情况，如果每步代价相同，代价一致就和 BFS 一样。

启发式搜索——A*算法

传统搜索没有考虑本身信息，不会用'当前节点离目标有多远'，就像没导航找路，瞎转悠。启发式搜索会用'导航'（启发式函数），效率大幅提升。

A*算法是启发式搜索的最优算法，核心目标是'在初始状态到目标状态的所有可能路径中，高效找到代价最小的最优路径'。它不像盲搜（BFS/DFS）那样'瞎转悠'，而是通过'已走的实际代价 + 到目标的估计代价'综合判断节点优先级，既保证最优性，又大幅提升搜索效率，相当于'带精准导航的找路算法'。

首先先由一个例子介绍一下 A*算法的执行过程，再证明其最优性。

A*算法涉及 3 个函数，其中，最终决定下一步走哪里的是 f(n)

• g(n)：从初始节点到当前节点 n的实际代价（固定值，路径确定则 g(n) 唯一）；
• h(n)：从当前节点 n到目标节点的估计代价（启发函数，决定 A*效率与最优性）；
• f(n)：从初始节点经 n 到目标的总代价估计，A*每次优先扩展 f(n) 最小的节点。

算法执行过程

目标：从城市 Arad 到 Bucharest 的最优路线。

为了实现这个目标，需要维护一个优先队列，该队列按节点的 f 值升序排列，当前对头即为下一步需要处理的节点。还需要维护一个关闭列表，记录已经遍历过的节点。

• 优先队列（fringe）：存储待扩展节点，按 f(n) 升序排列

  • 初始队列：[Arad（g=0，h=366，f=0+366=366）]

• 关闭列表（closed）：存储已扩展节点，初始为空

• 逻辑：初始节点 Arad 无前置路径，g=0，h=366（Arad 到 B 的直线距离），f=366 为当前唯一节点。

• 选中节点：队列中 f 最小的 Arad，将其加入关闭列表（closed={Arad}）

• 扩展 Arad 的 3 个邻居，计算每个邻居的 g、h、f：

  1. Zerind（Z）：g=Arad 的 g+75=0+75=75；h=374（Z 到 B 的直线距离）；f=75+374=449
  2. Sibiu（S）：g=0+140=140；h=253（S 到 B 的直线距离）；f=140+253=393
  3. Timisoara（T）：g=0+118=118；h=329（T 到 B 的直线距离）；f=118+329=447

• 更新队列（按 f 升序）：[Sibiu（393）、Timisoara（447）、Zerind（449）]

• 选中节点：队列中 f 最小的 Sibiu，加入关闭列表（closed={Arad、Sibiu}）

• 扩展 Sibiu 的 4 个邻居（Arad 已在 closed，跳过）：

  1. Fagaras（F）：g=140+99=239；h=176（F 到 B 的直线距离）；f=239+176=415
  2. Oradea（O）：g=140+92=232；h=380（O 到 B 的直线距离）；f=232+380=612
  3. Rimnicu Vilcea（R）：g=140+80=220；h=193（R 到 B 的直线距离）；f=220+193=413

• 更新队列（按 f 升序）：[Rimnicu Vilcea（413）、Fagaras（415）、Timisoara（447）、Zerind（449）、Oradea（612）]

• 选中节点：队列中 f 最小的 Rimnicu Vilcea，加入关闭列表（closed={Arad、Sibiu、Rimnicu Vilcea}）

• 扩展 Rimnicu Vilcea 的 3 个邻居（Sibiu 已在 closed，跳过）：

  1. Pitesti（P）：g=220+97=317；h=100（P 到 B 的直线距离）；f=317+100=417
  2. Craiova（C）：g=220+146=366；h=160（C 到 B 的直线距离）；f=366+160=526

• 更新队列（按 f 升序）：[Fagaras（415）、Pitesti（417）、Timisoara（447）、Zerind（449）、Craiova（526）、Oradea（612）]

• 选中节点：队列中 f 最小的 Fagaras，加入关闭列表（closed={Arad、Sibiu、Rimnicu Vilcea、Fagaras}）

• 扩展 Fagaras 的 2 个邻居（Sibiu 已在 closed，跳过）：

  1. Bucharest（B）：g=239+211=450；h=0（目标节点 h=0）；f=450+0=450

• 更新队列（按 f 升序）：[Pitesti（417）、Timisoara（447）、Zerind（449）、Bucharest（450）、Craiova（526）、Oradea（612）]

• 关键：此时 Bucharest 已加入队列，但 f=450 并非当前最小，不选中。

• 选中节点：队列中 f 最小的 Pitesti，加入关闭列表（closed={Arad、Sibiu、Rimnicu Vilcea、Fagaras、Pitesti}）

• 扩展 Pitesti 的 2 个邻居（Rimnicu Vilcea 已在 closed，跳过）：

  1. Bucharest（B）：g=317+101=418；h=0；f=418+0=418

• 更新队列：此时 Bucharest 有两个路径记录（Fagaras→B：f=450；Pitesti→B：f=418），队列按 f 升序更新为 [Bucharest（418）、Timisoara（447）、Zerind（449）、Bucharest（450）、Craiova（526）、Oradea（612）]

此时继续执行选中节点：队列中 f 最小的 Bucharest（f=418），Bucharest 是目标节点，算法终止 最优路径：Arad→Sibiu→Rimnicu Vilcea→Pitesti→Bucharest，总实际代价 g=418。

为什么 A*算法得到的一定是最优解？

对于树搜索和图搜索来说，A*算法得到最优解的条件是不太一样的，树搜索的要求更低一些：

A*图搜索的最优性条件：启发函数 h(n) 满足'一致性'

从 A*涉及到的三个函数来说，很明显可以看到h(n)是其中最关键的（g(n)是已知条件，f(n)只是用来求和，因此如何设计一个合理的 h(n)是最重要的）低估或者高估 h(n)都会对算法的性能造成影响。

因此A*算法要保证找到最优解，核心条件是启发函数 h(n) 满足'一致性'，具体如下：

1. 一致性（Consistency）定义：通俗来说，就是当前节点到目标的估计代价，不能比'先到相邻节点的实际代价 + 相邻节点到目标的估计代价'还大。
2. 一致性的作用：
   • 保证f(n)沿路径单调不减（f(n') = g(n') + h(n') = g(n') = g(n) + （从 n 到 n'的实际一步代价） + h(n') ≥ g(n)+h(n) = f(n)）；
   • 节点首次被扩展时，g(n)已是初始到 n 的最小实际代价，无需重复更新；
   • 目标节点首次被扩展时，其f(n)=g(n)（h(目标)=0）必为最小总代价，即最优路径。

注意：仅满足**'可采纳性'（h(n)≤h*(n)，h*(n) 为 n 到目标的实际最小代价）**不足以保证图搜索最优，因可能重复扩展节点导致错过最优路径；但'一致性'是更强的约束——一致的 h(n) 必可采纳，可同时满足图搜索的最优性与效率。

*一致性证明

即证明：保证f(n)沿路径单调不减：f(n') >= f(n)

符号定义与推导如下，不再过多赘述:

f(n') = g(n') + h(n') = g(n') = g(n) + （从 n 到 n'的实际一步代价） + h(n') ≥ g(n)+h(n) = f(n)

证明：树搜索 A*算法在 h(n) 可采纳时最优

证明该问题前，需要由如下概念引入：

• 可采纳性：启发函数h(n) ≤ h*(n)，其中h*(n)是节点 n 到目标节点的实际最小代价（即 n 到目标的最短路径代价）。
• 最优路径代价：设C*为初始节点到目标节点的实际最小总代价，G*为最优目标节点（即沿最优路径到达的目标节点，其g(G*)=C*）。
• 子最优目标节点：设G2为任意非最优的目标节点，（**即沿非最优路径到达的目标节点)**其g(G2) > C*（即路径代价大于最优值）。
• f(n) 的定义：f(n) = g(n) + h(n)，其中g(n)是初始节点到 n 的实际路径代价。

A算法会根据 f(n) 的值来选择下一个节点，我们需要证明：**当 h(n) 可采纳时，树搜索的 A会优先扩展最优路径上的节点，最终找到最优目标节点 G*，而非次最优节点 G2**。即 f(n) < f(G2) 恒成立。

步骤 1：最优路径上始终存在未扩展节点

• 初始时，初始节点在最优路径上，且是未扩展节点。
• 假设某一时刻，最优路径上的节点n被 A*扩展：由于树搜索的后继函数会生成n的相邻节点，其中必有一个节点n'仍在最优路径上（否则该路径不是最优），因此n'会被加入待扩展队列，成为新的未扩展节点。
• 结论：在 A*终止前，最优路径上必然存在至少一个未扩展节点。

步骤 2：最优路径上未扩展节点的 f(n) ≤ C*

设n是最优路径上的任意未扩展节点，需证明f(n) ≤ C*：

• 由于n在最优路径上，g(n)是初始节点到 n 的实际代价，而g*(n)是初始到 n 的实际最小代价（因 n 在最优路径上，故g(n)=g*(n)）。
• 由 h(n) 的可采纳性（h(n) ≤ h*(n)），h*(n)是n到 G*的实际最小代价。
• 因此：f(n)=g(n)+h(n)=g∗(n)+h(n)≤g∗(n)+h∗(n)
• 而g*(n) + h*(n)正是初始节点经 n 到 G*的实际最小总代价，即C*（最优路径代价）。
• 结论：f(n) ≤ C*。

步骤 3：次最优目标节点的 f(G2) > C*

设G2是任意次最优目标节点（g(G2) > C*），需证明f(G2) > C*：

• 目标节点的h(G2)=0（已到达目标，无需再估计代价），因此：f(G2)=g(G2)+h(G2)=g(G2)
• 由于G2是次最优节点，g(G2) > C*，因此：f(G2)=g(G2)>C∗

步骤 4：A会优先扩展最优路径的节点，最终找到 G

A*的扩展规则是：每次选择待扩展队列中 f(n) 最小的节点。结合步骤 2 和步骤 3 的结论：

• 最优路径上未扩展节点的f(n) ≤ C*；
• 子最优目标节点的f(G2) > C*。

因此，次最优目标节点 G2 的 f 值，必然大于最优路径上未扩展节点的 f 值。这意味着：A*会优先扩展最优路径上的节点，而不会先扩展子最优节点 G2。

随着最优路径上的节点不断被扩展，最终会扩展到最优目标节点 G*，此时f(G*) = g(G*) + h(G*) = C* + 0 = C*（是当前最小的 f 值），算法终止。

例如 PPT 中的例子

最优目标节点 G 指'通过最优路径到达的 Bucharest'，次最优节点 G2 指'通过非最优路径到达的同一个 Bucharest'：

• 最优路径：Arad→Sibiu→Rimnicu Vilcea→Pitesti→Bucharest，C*=418。
• 最优路径上的节点Sibiu：g(Sibiu)=140，h(Sibiu)=253（可采纳，因253 ≤ 实际到 Bucharest 的代价），故f(Sibiu)=140+253=393 ≤ 418。
• 子最优路径（如Arad→Timisoara→Lugoj→Mehadia→Drobeta→Craiova→Pitesti→Bucharest）：其目标节点的g(G2) > 418，故f(G2) > 418。

A*会优先扩展f=393的Sibiu，而非f>418的子最优节点，最终找到最优路径。

最优化搜索

局部搜索不关心从初始状态到目标的'路径'，只关心'找到最好的状态'

1. 爬山搜索：'贪心爬楼梯'

• 通俗理解：从当前状态出发，选'最好的邻居状态'（比如 8 拼图中，离目标布局更近的），一直往上爬，直到'没有更好的邻居'（到顶了）。
• 优点：简单、省内存。
• 缺点：容易困在'局部最高点'（比如爬了个小土坡，以为是山顶，其实旁边有更高的山），不完备、不最优。

2. 模拟退火：'允许偶尔下坡的爬山法'

• 通俗理解：像金属退火时'先高温软化，再低温定型'，搜索初期允许'选差一点的邻居'（下坡），避免困在局部最高点；后期慢慢不允许下坡，专注找全局最优。
• 优点：比爬山法更容易找到全局最优。
• 例子：找函数最大值，爬山法可能卡在小山峰，模拟退火会偶尔'往下走一步'，再找到更高的山峰。

3. 遗传算法：'模拟生物进化'

• 通俗理解：把每个'状态'看成'生物个体'（比如 8 皇后的布局是一个个体），多个个体组成'种群'。通过'繁殖（交叉）、变异'产生新一代个体，再留下'适应度高'（比如不冲突的皇后对多）的个体，逐代进化，直到找到最优个体。
• 核心步骤：
  1. 编码：把状态变成'染色体'（比如 8 皇后用 8 位数字表示每列皇后的行号）。
  2. 适应度函数：判断个体好不好（比如 8 皇后中，不冲突的皇后对数量）。
  3. 遗传操作：
     • 交叉：两个优秀个体交换部分'基因'（比如两个布局交换后 4 列的皇后位置）。
     • 变异：偶尔改变一个'基因'（比如随机改一列皇后的行号）。
• 优点：适合复杂的优化问题（比如卫星天线设计、高铁车头形状优化），能找到全局最优。

所有搜索算法核心对比表

例题

w = 0，f(n) = 2 * g(n)，此时相当于只关注当下；w = 2，f(n) = 2 * h(n)，此时相当于只关注目标。

1. 可采纳（admissible）：小于等于即 B 到 G 的最短路程

• 路径 B→C→D→F→G：1+3+3+5=12
• 路径 B→C→D→G：1+3+9=13
• 路径 B→D→F→G：5+3+5=13
• 路径 B→D→G：5+9=14

因此，0≤h(B)≤12

2. 一致（consistent）：当前节点到目标的估计代价，不能比'先到相邻节点的实际代价 + 相邻节点到目标的估计代价'还大。

因此，0≤h(B)≤10

3. 验证启发函数的性质：在实际应用中，通常优先选择满足一致性条件的启发函数，以确保图搜索下的最优性和效率。若仅满足可采纳性，树搜索仍能保证最优，但图搜索可能需要重新开放节点。