先看老师画的重点
状态搜索
状态搜索是搜索最基本的类型。它通过在状态空间中的初始状态出发，按照一定的顺序和条件对空间中的状态进行遍历，最终找到目标状态。
编程语言AI算法
高级人工智能期末复习：搜索算法
本文涵盖状态空间搜索基础，对比树搜索与图搜索差异，介绍 DFS、BFS 及改进策略。重点解析 A*算法原理，包括 f(n)=g(n)+h(n) 机制，证明启发函数可采纳性与一致性对最优解的影响。最后简述局部搜索方法如爬山法、模拟退火及遗传算法，并提供核心算法对比总结。
本文涵盖状态空间搜索基础，对比树搜索与图搜索差异，介绍 DFS、BFS 及改进策略。重点解析 A*算法原理，包括 f(n)=g(n)+h(n) 机制，证明启发函数可采纳性与一致性对最优解的影响。最后简述局部搜索方法如爬山法、模拟退火及遗传算法，并提供核心算法对比总结。
先看老师画的重点
状态搜索是搜索最基本的类型。它通过在状态空间中的初始状态出发，按照一定的顺序和条件对空间中的状态进行遍历，最终找到目标状态。
将状态搜索问题抽象为树状层级结构：
function Tree-Search(problem, fringe) returns 解/失败
fringe ← 加入初始状态节点
loop do
若前沿为空则返回失败
取出前沿首节点
若该节点是目标状态则返回
扩展该节点的所有后继节点，加入前沿
无状态去重机制，同一状态可能重复进入前沿，导致冗余扩展（如迷宫中同一位置被多次探索）
是树搜索的改进版，新增封闭集（closed）—— 存储已扩展的状态，避免重复探索同一状态。
function Graph-Search(problem, fringe) returns 解/失败
closed ← 空集合
fringe ← 加入初始状态节点
loop do
若前沿为空则返回失败
取出前沿首节点
若该节点是目标状态则返回
若该节点状态不在 closed 中：
将状态加入 closed
扩展该节点的所有后继节点，加入前沿
可能错过最优解（因为每个节点只搜索一次）
| 维度 | 树搜索 | 图搜索 |
|---|---|---|
| 状态去重机制 | 无封闭集，可能重复扩展同一状态 | 有 closed 集合，避免重复扩展 |
| 空间复杂度 | 较低（无额外存储） | 较高（需存储 closed 集合） |
| 适用场景 | 状态无重复的问题 | 存在重复状态的问题（如路径规划） |
| 搜索效率 | 可能因冗余扩展降低效率 | 因去重机制效率更高 |
评价一个搜索算法，从四个维度进行——完备性、最优性、空间复杂度、时间复杂度
这类算法只知道'初始状态、目标状态、能做什么动作'，不知道'当前状态离目标多远'，像瞎摸一样找路。
不具备完备性、最优性，但空间复杂度良好
具备完备性、最优性，但空间复杂度很高
结合 DFS 的空间优势和 BFS 的时间优势，先做'深度限制为 1 的 DFS'（只走 1 步就回头），没找到就做'深度限制为 2 的 DFS'，依次增加深度，直到找到目标。
找路时，不看走了多少步，只看从起点到当前节点的'总距离'，总距离最小的节点先探索。比 BFS 更通用，适合'每步代价不同'的情况，如果每步代价相同，代价一致就和 BFS 一样。
传统搜索没有考虑本身信息，不会用'当前节点离目标有多远'，就像没导航找路，瞎转悠。启发式搜索会用'导航'（启发式函数），效率大幅提升。
A*算法是启发式搜索的最优算法，核心目标是'在初始状态到目标状态的所有可能路径中，高效找到代价最小的最优路径'。它不像盲搜（BFS/DFS）那样'瞎转悠'，而是通过'已走的实际代价 + 到目标的估计代价'综合判断节点优先级，既保证最优性，又大幅提升搜索效率，相当于'带精准导航的找路算法'。
首先先由一个例子介绍一下 A*算法的执行过程，再证明其最优性。
A*算法涉及 3 个函数，其中，最终决定下一步走哪里的是 f(n)
目标：从城市 Arad 到 Bucharest 的最优路线。
为了实现这个目标，需要维护一个优先队列，该队列按节点的 f 值升序排列，当前对头即为下一步需要处理的节点。还需要维护一个关闭列表，记录已经遍历过的节点。
优先队列（fringe）：存储待扩展节点，按 f(n) 升序排列
关闭列表（closed）：存储已扩展节点，初始为空
逻辑：初始节点 Arad 无前置路径，g=0，h=366（Arad 到 B 的直线距离），f=366 为当前唯一节点。
选中节点：队列中 f 最小的 Arad，将其加入关闭列表（closed={Arad}）
扩展 Arad 的 3 个邻居，计算每个邻居的 g、h、f：
更新队列（按 f 升序）：[Sibiu（393）、Timisoara（447）、Zerind（449）]
选中节点：队列中 f 最小的 Sibiu，加入关闭列表（closed={Arad、Sibiu}）
扩展 Sibiu 的 4 个邻居（Arad 已在 closed，跳过）：
更新队列（按 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，跳过）：
更新队列（按 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，跳过）：
更新队列（按 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，跳过）：
更新队列：此时 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*涉及到的三个函数来说，很明显可以看到h(n)是其中最关键的（g(n)是已知条件，f(n)只是用来求和，因此如何设计一个合理的 h(n)是最重要的）低估或者高估 h(n)都会对算法的性能造成影响。
因此A*算法要保证找到最优解，核心条件是启发函数 h(n) 满足'一致性'，具体如下：
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)
证明该问题前，需要由如下概念引入：
h(n) ≤ h*(n)，其中h*(n)是节点 n 到目标节点的实际最小代价（即 n 到目标的最短路径代价）。C*为初始节点到目标节点的实际最小总代价，G*为最优目标节点（即沿最优路径到达的目标节点，其g(G*)=C*）。G2为任意非最优的目标节点，（**即沿非最优路径到达的目标节点)**其g(G2) > C*（即路径代价大于最优值）。f(n) = g(n) + h(n)，其中g(n)是初始节点到 n 的实际路径代价。A算法会根据 f(n) 的值来选择下一个节点，我们需要证明：**当 h(n) 可采纳时，树搜索的 A会优先扩展最优路径上的节点，最终找到最优目标节点 G*，而非次最优节点 G2**。即 f(n) < f(G2) 恒成立。
n被 A*扩展：由于树搜索的后继函数会生成n的相邻节点，其中必有一个节点n'仍在最优路径上（否则该路径不是最优），因此n'会被加入待扩展队列，成为新的未扩展节点。设n是最优路径上的任意未扩展节点，需证明f(n) ≤ C*：
n在最优路径上，g(n)是初始节点到 n 的实际代价，而g*(n)是初始到 n 的实际最小代价（因 n 在最优路径上，故g(n)=g*(n)）。h(n) ≤ h*(n)），h*(n)是n到 G*的实际最小代价。g*(n) + h*(n)正是初始节点经 n 到 G*的实际最小总代价，即C*（最优路径代价）。f(n) ≤ 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∗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的子最优节点，最终找到最优路径。
局部搜索不关心从初始状态到目标的'路径'，只关心'找到最好的状态'
w = 0，f(n) = 2 * g(n)，此时相当于只关注当下；w = 2，f(n) = 2 * h(n)，此时相当于只关注目标。
因此，0≤h(B)≤12
因此，0≤h(B)≤10
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
生成新的随机RSA私钥和公钥pem证书。 在线工具，RSA密钥对生成器在线工具，online
基于 Mermaid.js 实时预览流程图、时序图等图表，支持源码编辑与即时渲染。 在线工具，Mermaid 预览与可视化编辑在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online