· 人工智能导论
人工智能导论 Day2:从状态空间到搜索策略
RedMoon · 2026-09-20 · 课堂阅读笔记
怎样找到一条合适的路线
搜索通过考察行动可能产生的后果来选择下一步。规划型 Agent 需要判断:采取某个行动后,环境会变成什么,之后还能怎样到达目标?反射型 Agent 则主要依据当前感知及其规则行动,不显式展开未来行动树。
课件先限定一个便于分析的世界:完全可观察、确定性、离散、静态。找到方案后可以把动作序列交给执行器。真实环境一旦变化,就可能需要反馈、重规划或不确定性建模,不能直接套用这个简化前提。
课堂历史回顾从符号推理、专家系统讲到神经网络。专家系统以知识库与推理规则为核心,不等于 MLP 加反向传播。AI 寒冬的分期存在不同口径;2006 年是深层模型研究的重要节点,不是 RBM 首次出现的年份。
先定义问题,再选择搜索顺序
一个搜索问题需要初始状态、可执行动作、转移模型、目标测试与路径代价。由初始状态经动作可到达的状态构成状态空间,可以抽象为图。
以从 Arad 到 Bucharest 的道路规划为例,状态是所在城市,动作是走一条相邻道路,转移得到下一座城市,目标测试是是否抵达 Bucharest,路径代价是路程之和。这里不需要把状态强行编码成固定的 128 维向量;表示的关键是保留决定后续行动及代价的必要信息。
“状态”和“搜索节点”也不同:同一城市可以经不同路径到达,对应多个搜索节点。节点通常记录状态、父节点、动作和累计代价,才能在找到目标后回溯解。直接把整张状态图全部展开可能过大,因此搜索按需生成后继。
通用过程是维护待展开集合 frontier,也叫 OPEN;取出一个节点,检查目标并生成后继。图搜索还维护已展开状态集合 CLOSED。真正区分策略的是:下一次从 frontier 取谁,以及遇到重复状态时怎样处理。对带权搜索,只记“见过”往往不够,还要保留当前最佳代价,必要时更新或重开节点。
课堂主线:盲目搜索的取舍
评价策略有四个问题:有解时能否找到,即完备性;是否找到最低代价解,即最优性;花多少时间;占多少空间。搜索过程消耗的计算资源与执行路线的领域代价不是一个单位,只有先统一到共同成本尺度,才适合相加比较。
记分支因子为 $b$,最浅目标深度为 $d$,最大搜索深度为 $m$。
| 策略 | frontier 的规则 | 完备性与最优性 | 常见代价口径 |
|---|---|---|---|
| BFS 宽度优先 | FIFO 队列,先浅后深 | 有限分支且目标在有限深度时完备;等步长代价时最优 | 课件按生成目标即检测的口径为时间、空间 $O(b^d)$ |
| DFS 深度优先 | 栈或递归,沿分支深入 | 无限深度或环可阻止找到解;通常不最优 | 树搜索时间 $O(b^m)$,保存路径及待选兄弟时空间 $O(bm)$ |
| IDS 迭代加深 | 深度上限逐轮增加 | 有限分支、有限目标深度时完备;等步长时最优 | $b>1$ 时常记时间 $O(b^d)$、空间 $O(bd)$ |
| UCS 一致代价 | 按累计代价 $g(n)$ 的优先队列 | 非负边权的有限图可求最短路;无限空间还需终止条件 | 与最优解代价范围内实际探索节点数有关 |
这张表中的实现前提不能省略。BFS 若在出队时才检测目标,找到目标之前可能生成下一层节点,常见教材也写 $O(b^{d+1})$。DFS 的线性空间指树或路径搜索;若保存全局 visited,额外存储可达 $O(V)$。有限图配合正确去重的 DFS 可以完备,不能笼统写成“DFS 永远不完备”。
IDS 会重复访问浅层,但分支数大于一时,最深层节点通常占多数,重复浅层不会改变上述渐近阶。深度受限搜索应区分“触及深度上限”与“此分支确实无解”。双向搜索是另一种课件方案:从起点和目标同时推进,理想情况下规模约为 $O(b^{d/2})$,但要能有效生成反向前驱、检查相遇,并采用正确停止条件;不是任意问题都适用。
两步路线和三步路线,哪条更好
以两条简单路线比较:$S\to A\to G$ 的边权为 1、9;$S\to B\to C\to G$ 的边权均为 2。BFS 会优先找到两步路线,代价为 10;UCS 会找到三步路线,代价为 6。
UCS 必须在目标以当前最小代价从优先队列弹出时接受它,而不是第一次生成目标就停止。否则较早发现的昂贵路线会遮住后来出现的便宜路线。非负边权、正确松弛和过期队列项处理,使它与 Dijkstra 的思想一致。无限搜索空间中,“每条边代价至少为某个正数 $\epsilon$”是常用的充分条件,可避免无限多极小代价步骤阻挡目标。
用启发式估计剩余路程
这节课的课堂主线是盲目搜索;以下启发式搜索、与或图和博弈内容属于课件延伸,重点是不同方法怎样利用问题本身的信息。
贪心最佳优先只看 $h(n)$,即估计离目标还有多远;UCS 只看已经走过的 $g(n)$;A* 将二者结合:
\[f(n)=g(n)+h(n).\]罗马尼亚地图中,用到 Bucharest 的直线距离作启发式很自然,因为在同一距离度量下道路路线不会短于两点直线。课件中贪心倾向 Arad、Sibiu、Fagaras、Bucharest,路程为 $140+99+211=450$;经 Rimnicu Vilcea、Pitesti 的路线为 $140+80+97+101=418$。只看“现在离目标近不近”会错过整体更便宜的路。
贪心不保证最优;在没有去重的无限空间可能不完备,但有限图上正确去重、最终展开所有候选时可以找到可达目标,不能无条件断言其从不完备。
可采纳与一致:为什么 A* 的条件很重要
可采纳要求不高估真实最小剩余代价:
\[0\leq h(n)\leq h^*(n).\]一致性对每条边提出更强的局部条件,并取目标启发值为零:
\[h(n)\leq c(n,n')+h(n'),\qquad h(G)=0.\]可采纳启发式支持 A* 树搜索的最优性;不重开 CLOSED 节点的 A* 图搜索通常要求一致性。若允许更优路径出现时重新展开状态,可处理可采纳但不一致的启发式。有限分支、合理正代价下界等条件则与终止、完备性相关,不能只凭一个公式宣称算法必定成功。
课件第 62 页给了很好的反例:$S\to A=1$,$S\to B=1$,$A\to C=1$,$B\to C=2$,$C\to G=3$;取 $h(A)=4,h(B)=1,h(C)=1,h(G)=0$。先经 B 展开 C,得到 $g(C)=3$;后来经 A 得到更好的 $g(C)=2$。若 C 已关闭且不允许重开,最终可能得到代价 6 而不是 5。这里 $h(A)=4>1+h(C)=2$,恰好违反一致性。
启发式可以来自放松约束的问题:放松后最优代价不大于原问题代价,可成为下界。若两个启发式都可采纳,且一个在所有状态上都不小于另一个,它提供更紧的下界;但实际速度还要考虑启发式计算成本、平局规则与实现,不能只看值更大就断言运行更快。
与或图:一个方案需要完成哪些子任务
有的问题需要同时解决多个子问题,而不是从多个动作中选一个。课件用全等四边形证明说明:证明两个三角形全等可能都要完成,构成 AND;证明三角形又可以选择不同判定法,构成 OR。梵塔把搬运任务递归拆解,Fibonacci 递推则展示多个子问题的依赖。
OR 节点有一个可解后继即可;AND 节点要求所需后继全部可解。解因此是一棵解树或子图,不一定是单一路径。终止节点对应可直接解决的本原问题;未展开的 frontier 是未知状态,不能仅因当前没有孩子就宣告无解。
为避免与 A* 的累计路径代价混淆,以下将课件中的子问题求解代价 $g(x)$ 记为 $J(x)$:
\[J(x)=\min_y\{c(x,y)+J(y)\}\quad\text{(OR)},\] \[J(x)=\sum_y\{c(x,y)+J(y)\}\quad\text{(AND,总工作量)}.\]终止问题代价为零,已确认的死路为无穷。若评价的是可并行子任务的完成时间,且满足并行执行假设,可用最大子任务时间而非求和;代价模型必须先说明。
例如,根节点可选择“解决 B、C 两个子问题”或“单独解决 D”,三条相关边代价均为 1,剩余代价分别为 2、3、7。前者总代价为 $1+2+1+3=7$,后者为 $1+7=8$,所以当前偏好前者。
AO* 自顶向下扩展当前最有希望的部分解图,再自底向上更新估价与可解标记,反复修正希望树。AND 分支需要保留整组必需子问题,OR 分支选当前最优方案。对含环或共享子问题的复杂图,还需明确实现假设,不能把树上的说明无条件外推。
对手也在选择
对抗搜索关注两方轮流行动的博弈。课件的主要前提是二人、零和、完全信息、确定性。囚徒困境和纳什均衡用于引入博弈思想:均衡关注单方改变策略是否能获益,不等于双方共同收益最大,也不是极大极小算法的别名。
Minimax 在我方节点取最大值,在对手节点取最小值;叶子用真实终局收益,深度截断处用评估函数。课件井字棋例子用双方仍可能形成三连线的条数差估计非终局,但它仍只是启发式评分。对称棋盘可合并,减少重复。
再用一个两层小树试算:根是 MAX,两个 MIN 子节点的叶值分别为 $(3,5)$ 和 $(2,9)$。子节点值为 3 和 2,根选择 3。全树最大的 9 不会被选中,因为对手会在那条分支选择 2。
Alpha-beta 剪枝维护 MAX 已有保证的下界 $\alpha$ 和 MIN 的上界 $\beta$,当 $\alpha\geq\beta$ 时,该分支后续不可能改变祖先决策,可以停止展开。在上述例子中,左侧确定 3 后,右侧先见到 2,就不必再看 9。相同搜索深度与评估下,剪枝不改变根的 minimax 值;排序影响能剪掉多少,平分时可选动作可能不同。
课件最后区分 AlphaGo 与 AlphaGo Zero:前者结合策略网络、价值网络、快速 rollout 与 MCTS;后者突出策略价值网络和自我对弈,不应把两代系统的组件混写。MCTS 使用抽样并不意味着围棋规则含有随机机会节点。1997 年 Deep Blue 与 2016 年 AlphaGo 的成绩说明特定棋类系统的进展,不是所有智能问题已经解决。
搜索方法的比较与复习要点
搜索过程包含三个连续选择:先决定怎样描述世界,再决定怎样评价候选,最后决定怎样控制搜索规模。数据结构对应不同的判断标准:队列偏好浅层,优先队列偏好低代价,启发式则引入对未来的估计。
- 为一个具体任务写出搜索问题五要素,区分状态与节点。
- 手算 BFS、DFS、UCS 的 frontier,说明何时检测目标。
- 解释 DFS 线性空间、BFS 最优、A* 最优分别需要哪些条件。
- 重算罗马尼亚两条路线与 A* 不一致反例。
- 对与或图同时写出可解条件与代价递推,区分未知和无解。
- 手算一次 minimax 和 alpha-beta,说明被剪分支为何不影响根决策。