第 12 讲 · 问题求解与无信息搜索

机器学习通常直接学习“输入到输出”的映射；问题求解智能体则要找一串行动，例如从城市 A 到城市 B、移动八数码方块或在迷宫中走到出口。搜索的前提是规则已知，但不知道哪条行动序列能到目标。

课件目录还列出约束满足和对抗搜索，但本份课件正文实际展开的是状态空间与无信息搜索；这里不拿课件外内容补齐那两个标题。

先把现实问题形式化

一个搜索问题包含：

初始状态：从哪里出发；
动作或后继函数：当前状态允许做什么；
状态转移：动作后到哪里；
目标测试：怎样算完成；
路径代价：不同路线如何比较。

解是一条从初始状态到目标状态的动作序列，最优解是路径代价最小的解。若形式化错了，搜索再快也只会精确解决错误问题。

状态和搜索节点不是一回事

状态描述世界，例如“八数码当前排列”；搜索节点还记录父节点、所用动作、路径代价和深度。同一个状态可能由不同路径到达，因此搜索树里可以出现多个对应节点。

通用树搜索流程：把初始节点放进 frontier，循环选择一个节点；若达到目标则返回，否则展开后继并放回 frontier。各算法最核心的差别，就是“下一次从 frontier 取谁”。

评价算法时常用：

完备性：有解时能否找到；
最优性：能否找到代价最小解；
时间复杂度：生成多少节点；
空间复杂度：同时保存多少节点。

设分支因子为 $b$ ，最浅目标深度为 $d$ ，最大深度为 $m$ 。

广度优先搜索 BFS

BFS 用 FIFO 队列，总是先展开最浅层：

frontier <- queue(initial)
while frontier not empty:
    node <- pop_front(frontier)
    if goal(node): return solution
    push_back(frontier, children(node))

有限分支下 BFS 完备；每步代价相同的时候，第一个目标也是最优。时间和空间约为 $O(b^{d+1})$ ，最大的缺点是要把整层节点留在内存。

课件用量油问题、城市路径、迷宫和八数码说明：只要每一步代价相同且目标不太深，BFS 很直接。若边代价不同，浅不等于便宜，应改用一致代价搜索。

一致代价搜索 UCS

UCS 用优先队列，每次取累计路径代价 $g(n)$ 最小的节点。只要每步代价至少为某个正数，它完备且最优。Dijkstra 算法可看作图上的 UCS。

关键是：不能在节点刚生成时就认定它的路径最优；应在它以当前最小代价从优先队列弹出时确认。若之后发现到同一状态更便宜的路径，还要更新队列中的记录。

深度优先搜索 DFS

DFS 用栈或递归，总沿一条路径走到底。它只需保存当前路径和少量兄弟节点，空间约为 $O(bm)$ ；但在无限深空间可能永远走错分支，既不完备也不最优。

课件以连连看路径和素数环为例。DFS 适合用约束尽早剪枝：一旦部分解已经不可能完成，就不要生成后面整棵子树。剪枝不是改变答案，而是利用问题结构排除不可能分支。

深度限制与迭代加深

深度限制搜索给 DFS 一个上限 $\ell$ ，避免无限下潜，但目标若更深就会漏掉。迭代加深依次用上限 0、1、2……重跑深度限制搜索。

它看似重复很多，但搜索树最底层节点数量最多，前几层重复成本相对小。单位步长下，迭代加深兼具 BFS 的完备、最优与 DFS 的低内存：时间约 $O(b^d)$ ，空间约 $O(bd)$ 。

双向搜索

若能从目标反向生成前驱，可以同时从初始和目标搜索，在中间相遇。理想情况下深度从 $d$ 变成两边各 $d/2$ ，节点量由约 $b^d$ 降到约 $2b^{d/2}$ 。但它要求目标明确、逆操作可生成，还要高效判断两边 frontier 是否相交。

图搜索为什么要记录访问状态

树搜索可能在环中重复。图搜索增加 explored/closed 集合，避免反复展开相同状态。不过对 UCS 和下一讲的 A*，如果找到到同一状态更便宜的路径，不能简单地一律丢弃；实现要保存当前最佳代价并允许更新。

无信息搜索只利用问题定义，不知道哪个方向更接近目标。第 13 讲会加入启发函数 $h(n)$ ，让搜索顺序利用领域知识。