为什么要保存前沿?
设想机器人在单向走廊中移动。我们需要指定起点、合法移动及目标,地图才构成一个搜索问题。若每次移动都花一分钟,最少步数就给出最短行程;若走廊的通行时间不同,步数最少的路线却可能更慢。因此,搜索策略必须配合我们想最小化的量。
定义 22.1.1
(状态与搜索节点)
状态须包含判定未来合法行动及辨认目标所需的一切数据。若开门会消耗钥匙,位置本身便不足以描述状态;可以考虑(位置、持有的钥匙)这个配对。搜索节点则可记录抵达某状态的一条具体路径;不同路径可以抵达同一状态。图搜索将重复状态合并,避免一再探索相同的未来。只有当相同状态标签确实代表相同的未来选择及代价时,这样合并才正确。
本节研究有限图上的三种基本方法,为使用启发式函数改变优先次序的 A* 作准备。
同一问题,三种前沿策略
定义 22.1.2
(搜索问题、前沿与解)
令 为有限有向图,起点为 、目标集合为 ;为重现追踪结果,固定每个状态的后继次序。路径长度是边数。一致代价搜索另为每条边指定有限非负代价 ;路径代价是边代价之和。解是由 到某目标的路径;若 本身是目标,长度零的路径也是解。前沿保存已发现但尚未处理其外出边的状态。沿父指针反向追溯至 ,便可重建路径。
定义 22.1.3
(广度优先搜索)
广度优先搜索(BFS)把 放进先入先出队列并标记为已发现。反复移除队首 ;若它是目标,返回父指针路径。否则依次检查后继:对每个尚未发现的 ,立即标记、令其父节点为 ,再把它加入队尾。队列耗尽便报告失败。加入时立即标记,可防止两个父节点把同一状态重复放进队列;对最少边数的目标而言,不必保留之后的路径。
定义 22.1.4
(深度优先搜索)
深度优先搜索(DFS)可递归实现:进入 时标记,测试它是否目标,然后按次序递归访问每个仍未发现的后继,调用前设定父指针。找到第一个目标便停止;若从 开始的调用返回仍未找到,则报告失败。递归栈保存目前路径。使用显式栈时,标记及插入后继的时机可以改变访问次序,因此应追踪实际算法,而非单凭名称推断次序。
定义 22.1.5
(一致代价搜索)
一致代价搜索(UCS)维护暂定代价 :开始时 ,其余为无穷大,最小优先队列含 。移除代价最小的项;若其状态已确定,或项目的代价不等于目前 ,便忽略它。否则确定该状态;若它是目标,返回父指针路径和代价。对每条外出边,若 ,就更新 、设定父指针为 ,并插入新项。此做法容许过期的队列项,无须实现 decrease-key。相同代价不必更换父指针。在上述条件下,已确定状态不会再得到改善,证明如下。
保证与证明
定理 22.1.6
(BFS 最小化边数)
在有限有向图上,BFS 返回边数最少的可达目标路径,或正确报告没有目标可达。每个状态至多发现一次。使用邻接表时,时间为 ,辅助状态及队列存储空间为 。
证明
(队列次序与最短距离)
队列最初只有深度零的起点。移除深度 的状态时,新状态以深度 加到队尾。因此由归纳法,队列按记录深度非递减排列;每个已发现状态的父指针均给出该深度的路径。为证明起见,考虑一个假想的完整遍历:遇到目标时不停下来,而照常展开它。对最短距离 作归纳,证明距离为 的每个可达状态都以深度 被发现。 是起点。对距离为 的 ,最短路径上其前驱距离为 ,依归纳假设以前者深度入队,并在任何深度 的状态之前被移除;届时它会发现 ,除非 已以不大于 的深度被发现。每条已发现路径都真实存在,因此其深度不可能小于最短距离 。命题成立。实际执行直至移除第一个目标之前,与完整遍历完全相同。若该目标深度为 ,却有另一目标的最短距离更小,完整遍历便会依队列次序先移除后者,矛盾。每个状态只入队一次,各外出边只检查一次,得到所述界限。队列耗尽时所有可达状态均已处理,故失败判断正确。
证明透视
队列次序带来什么
证明分两部分。不变式是队列按记录的深度排序:每次移出深度为 的状态,只会把深度为 的状态加到较旧的项目之后。真正的想法是对真实距离作归纳: 在最短路径上的前驱距离为 ,所以以深度 入队,并先于任何深度为 的状态被移出,于是 至迟在深度 被发现;又因为每个记录的深度都是实际的路径长度,不可能更早。有限性只用于穷尽,使失败报告正确。整个论证没有用到边的代价,这正是 BFS 看不到代价的原因。
定理 22.1.7
(UCS 最小化非负路径代价)
在边代价有限且非负的有限图上,上述 UCS 确定每个非过期移除状态时,其标签等于最小路径代价。因此第一个确定的目标在所有可达目标中代价最小。若没有可达目标,算法会终止并报告失败。
证明
(第一个被错误确定的状态)
每个有限暂定标签都对应实际路径,故不会小于真正的最小值。反设 是第一个被确定时标签大于最小值的状态。取一条到 的最便宜路径,令 为确定 前该路径上第一个尚未确定的状态。若 ,其标签为零;否则其前驱 已被正确确定,松弛 时已给 一个不大于该路径前缀代价的标签。由于余下边均非负,前缀代价不大于整条路径的代价。因此队列中有 的有效项,其优先值不大于 的最优代价,严格小于正在确定 的项,与最小值先出矛盾。同一前缀论证排除了第一个确定目标以外存在更便宜目标的可能。状态有限、每个状态只确定一次,而每次处理的边有限,故只会产生有限个队列项;即使有零代价边也会终止。
证明透视
非负代价的作用
最便宜路径的前缀代价必须不大于整条路径。负边可使不等式倒转:一条目前看似昂贵的前缀,之后可能通往便宜的目的地。此时永久确定状态及在第一个目标停止都可能失败。
命题 22.1.8
(带过期项的一致代价搜索的时间)
使用二叉堆与邻接表时,上述 UCS 程序在 时的时间为 ,空间为 。
证明
(计算堆操作次数)
每个状态只确定一次,确定时只检查其外出边一次,所以松弛最多 次。每次成功松弛插入一项,故全程最多插入并移除 项,堆内也从不超过 项。因 ,一次堆操作的成本为 。移除状态已确定的过期项只花一次移除,没有其他工作。再加上 的簿记工作,便得到所述界限。
有限图上的 DFS 若标记状态,而且每个邻接表有限,也必会终止;若报告失败,所有可达状态都已访问。但找到的第一个目标取决于后继次序,不保证最少边数或最小代价。使用邻接表,完整图 DFS 的时间为 ;包括已访问标记和递归的空间为 。若忽略已访问标记而只说它使用路径深度的内存,便容易误导。没有标记时,即使状态有限,环也可能使搜索永不停止。
算例:同一张图,不同答案
例题 22.1.9
(同一张图上的广度优先与深度优先搜索)
依所列次序取边: 代价 、 代价 、 代价 、 代价 、 代价 ,没有其他边。路径 有三条边、代价 ; 有两条边、代价 。
BFS 依次移除 ,此时队列为 : 由 加入, 由 加入。处理 时, 已被发现,故父指针仍为 。BFS 返回边数最少的 ;它不会比较代价 与 。
递归 DFS 每次走第一个后继,访问 并返回该路径。这次刚好得到较便宜的路径;若倒转 的两个后继,便得到 。偶然的次序不能证明最优。
例题 22.1.10
(有并列与较迟改善的一致代价搜索)
UCS 以 确定 ,以 确定 ,再以 确定 ,两者先后不限。若 先被确定,它插入 ,然后 把标签改善至 。若 先被确定,它插入 ,而 不会插入 ,因为 并非改善。最后以 确定目标,返回 。如果 先于 确定,在第一次发现 时就停止可能错误地返回 。
概念视角算法
把一致代价搜索看作细分图上的广度优先搜索
当所有代价都是正整数时,把每条代价为 的边换成由 条单位边组成的链,中间经过 个新状态。路径代价就变成边数,所以细分图上 BFS 的第 层,恰好包含最小代价为 的原有状态,而 UCS 按相同的代价次序结算原有状态。在例子的图中, 与 都在第 层; 最早在第 层出现,经由 ,而经由 的路线要到第 层才到达。这个描述需要正整数代价,因为零代价无法细分;优先队列只是扫过同样各层的省力办法。
例题 22.1.11
(零代价环与不可达的目标)
设 与 的代价都是 , 代价为 。UCS 以 确定 并插入 ;再以 确定 。松弛 不是改善,因为 不成立;松弛 则插入 。以 确定 ,返回 ,代价为 。零代价环不会造成循环:每个状态只确定一次,而替换必须是严格改善。若移除边 ,队列在确定 与 后耗尽,程序正确地报告失败,因为没有目标可达。
反例模式
边数最少不等于代价最小
直接边 代价为 ,边数比两边路径 少;但若后者两条边各花 ,总代价只有 。BFS 对单位边数、或更一般地相等正边代价,提供最优保证,对任意非负代价则没有。
常见错误
(在发现时而非确定时停止)
在例图中,若 先于 被确定, 第一次被发现时的标签是 。此刻就返回,得到代价 ,但 的代价是 ,标签 在 被确定后才出现。对 UCS,目标测试应放在状态由队列移除并确定的时刻。(BFS 可以在发现时测试,因为每条边都算作一步。)
保证的界限
有限图仍可比它的简短问题描述大得多。若一棵搜索树每个节点至多有 个子节点,深度至 的节点数至多为 ;这是对明确生成的树的界,不自动是任意问题输入比特长度的界。不同路径到达有效的共同状态时,图合并可节省工作;但若状态表示把未来不同的情况合并,结论便不可靠。
UCS 是在目标处停止的 Dijkstra 算法。若边代价均相等且严格为正,BFS 与 UCS 找到的最优目标代价相同,平手时选择则可能不同。若所有边代价均为零,每个可达目标代价都是零,而 BFS 仍选择边数最少者。A* 按 排序;它的目标判定和重新开启规则需要另外的假设,详见启发式搜索一节。
练习
快速检查
(所有边代价为一,后继次序为 、、、。写出 BFS 直至目标的移除次序及返回路径;递归 DFS 返回什么路径?)
明确维持队列,每次移除后写出队列内容。
解答 · 答案
队列由 依次变成 、、、。直至目标的移除次序是 。 的父节点为 ,故路径是 。递归 DFS 走 ,然后停止。
快速检查
(边为 代价 、 代价 、 代价 、 代价 、 代价 。执行 UCS,写出确定标签及返回路径,并解释 的过期项。)
记录每次插入及其优先值,并注意哪些项在移除时已过期。
解答 · 答案
以 确定 ,加入 ;以 确定 ,把 改善至 ,并加入 ;以 确定 ,把 改善至 。旧项 被忽略,因为 已确定,而且其优先值与目前的 不符。最后以 确定 ;父指针给出 ,代价为 。
快速检查
(设 代价 、 代价 、 代价 。说明 UCS 在确定 时停止的结果,以及证明中哪一步失效。)
写出确定 后的队列,看哪一项先被移除。
解答 · 答案
处理 后队列含 及 。算法确定 并返回代价 ,但 的代价为 。到 的前缀代价 大于整条路径代价 ;证明中的前缀界正依赖非负性。负环更会造成另一问题:最小值可能根本不存在。
快速检查
(有限图有环 和边 。若递归 DFS 在 总是先访问 再访问 ,为何没有标记时可能失败?为何有标记的版本会终止并找到 ?)
从 起跟随递归,写出调用序列。
解答 · 答案
没有标记时,递归在 间交替,永远到不了 的第二个后继。有标记时,第二次遇见 会跳过,接着便访问 。一般而言,每个状态最多进入一次,而每个有限后继表最终都会处理完,所以递归终止。