动机
选择行动之前,程序必须知道什么才算成功。送货机器人可能要找总成本最低的路线;游戏程序则要选择一个经得起对手最佳回应的行动。两者都探索未来,但数学目标不同。一条路线的成本只涉及该路线;一个可靠的游戏选择,却要计及由对手决定的多种后续局面。
若每个状态至多有 个后继,深度为 的完整搜索树可有 个节点。启发式估计能把注意力放在较有希望的方向,但看似合理的得分并非证明。我们要找出哪些不等式令结果可靠,以及哪些实现上的选择会破坏它们。
读者应熟悉有限图、归纳法及基本渐近记号。
定义
定义 1.1.1
(搜索问题与最优剩余成本)
确定性搜索问题包含状态集 、起点 、目标状态、有向合法转移,以及边成本 。路径成本是各边成本之和。以 表示由 到任一目标的最低剩余成本;没有可行路径时取无穷大。在有限且成本非负的图中,删去非负成本循环不会增加成本,因此可达目标的最优值可由某条简单路径取得。
定义 1.1.2
(状态与搜索节点)
搜索节点记录一条特定路径,状态则记录足以决定往后合法行动的信息。因此,多个节点可以对应同一状态。若燃料会影响行动,单用位置作状态便不够完整,合并这些节点可能丢掉正确答案。图搜索通常保留最小已发现路径成本 ,以及用来重建路径的前驱。
定义 1.1.3
(可采纳与一致的启发式;A*)
非负启发式函数 称为可采纳,若每个状态均有 ,并要求所有目标的估计为零。若每条合法边均满足下式,便称它一致:
沿到达目标的路径反复应用此式,可见一致性蕴涵可采纳性;反方向一般不成立。A* 以 排列已发现而尚未展开的状态。松弛一条边,是在 时改善后者并更新前驱。若已展开的状态获得改善后重新进入边界集合,便称为重新开启。
定义 1.1.4
(局部搜索与爬山法)
爬山法作出另一种取舍:它只保留当前候选,移到目标得分更好的邻居,不必保存其他路径。局部最大点没有更好的邻居,却可能远逊于别处。平台上的同分行动要有明确处理规则,否则无限制横向移动可能造成循环。
定义 1.1.5
(极小极大值)
游戏部分假设搜索树有限、转移确定、完全信息,MAX 与 MIN 轮流行动,每个叶节点有一个给 MAX 的收益。叶节点的极小极大值就是其收益;MAX 节点取子节点最大值,MIN 节点取最小值。这是零和模型,假设 MIN 正在最小化 MAX 的同一收益。随机结果或隐藏信息需要另外的模型。
定理/命题
定理 1.1.6
(一致启发式下的 A*)
设有向图有限,边成本非负,启发式非负、一致且在目标为零。A* 每次取最小 ,只在成本严格改善时更新,并忽略优先队列中的过期项目,便可在取出状态时永久关闭它。每个已取出状态的 均为最优成本;若在取出目标时停止,所得路径最便宜。
命题 1.1.7
(可采纳启发式配合重新开启的 A*)
设有向图有限,边成本非负, 可采纳且在目标为零,并设从 可达某个目标。考虑这样的 A*:每当标记 被严格改善, 就重新放回边界集合,即使它之前已展开过;并在取出目标时停止。则它必会停止,且所返回的路径最便宜。
命题 1.1.8
(极小极大值与 - 截断)
在上述有限交替游戏树中,极小极大值是 MAX 面对最佳对抗仍可保证的收益。深度优先计算时,若 MAX 节点目前下界已不小于祖先 MIN 选择的上界,可停止该节点其余分支;若 MIN 节点目前上界已不大于祖先 MAX 选择的下界,也可停止。这些截断保留根节点的极小极大值。
正确性不等于普遍高效。有限状态图仍可能非常庞大,- 也不排除最坏情况下的指数级叶节点数。定理说明在指定模型中答案有什么保证,没有承诺任意问题都能快速解决。
证明思路
证明
(重加权把 A* 化为 Dijkstra)
引入重加权边成本:
一致性恰好表示新成本非负。从 到 的路径中,中间启发式项互相抵消,故新成本等于原成本加 。因此,按 排序,等价于按暂定的新路径成本排序。A* 的永久关闭论证于是转成非负边上的 Dijkstra 论证。
具体来说,假设某次取出的 还有更便宜的路径。在该路径上取第一个未关闭状态 ;它的前驱已用最优成本关闭,因此松弛后, 有最优暂定标记。由于余下的新边成本非负, 的新暂定成本不超过 的最优新成本,却严格小于目前取出项目的成本,与取最小值矛盾。起点成本为零,归纳便完成所有状态的论证。目标估计为零;若还有更便宜的目标,其路径必有优先值更小的边界前缀,故不能先取出较贵目标。
证明透视
启发式不等式真正提供什么
关键是假设每条边一致,而不只是估计通常偏低。一致性把所有重加权边变成非负,后来的路径便不能经过负成本新边,偷偷降低已确定的标记。可采纳性仍可提供目标的下界论证,却不足以单独支持永久关闭。
证明
(已定案的前缀令边界上有状态不超过最优值)
终止性。 每个标记 都是一条由松弛串联而成的路线的成本。由归纳可知这些路线都是简单路径:若到达 的路线已经经过 ,则 的标记早已不大于该前缀的成本,而标记只降不升,故经 的松弛不会是严格改善。有限图只有有限条简单路径,所以每个状态只可能有有限个标记值。每次重新放入边界集合都跟随一次严格下降,因此放入次数有限。
最优性。 设 是成本为 的最便宜目标路径,其每个前缀都是到该端点的最便宜路径,成本为 。若 曾在标记等于 时被展开,便称它已定案。假设尚未取出任何目标,则 未定案,所以路径上有第一个未定案的状态 。若 ,则 在边界上,标记为 。若 ,则 已用最优标记展开,所以 得到的标记不大于 。标记是路径成本,故它等于 。由于 尚未以该标记展开,而每次严格改善都会令状态重新进入边界,所以它在边界上。它的优先值满足
因为路径余下部分到达目标的成本是 。所以在取出目标之前,边界非空,且最小优先值至多为 。以标记 取出的目标,其优先值就是 (目标处 )。取出最小优先值项目,故 ;又因 是从 到某个目标的路径成本,所以 。因此 。
证明
(对树高归纳,再传递界限)
极小极大法用树高归纳。叶的值由模型指定。MAX 可以选取保证值最大的子节点,MIN 则能把任何其他选择限制在其子节点值;MIN 节点作对称论证。这同时证明收益可保证,以及对手能达到相应上界。
剪枝时,若较早选择已保证根收益至少为 ,新 MIN 子节点只要找到一个收益不超过 的回应,该整个子节点的值便至多为 。其余回应只可能令最小值更低,不能改善根选择。MAX 的情况对称。相等时可为求值或找一个最优行动而剪枝,但若要列出所有同分最优行动,就可能要保留更多分支。被截断子树的返回值亦可能只是界限,而非精确值。
下面的追踪使用另一棵有八个叶节点的树。比较根节点的精确值与被剪枝子树返回的界。
当确切值已不影响决策,就可剪去分支
MAX 与 MIN 轮流行动,所有终端收益都从 MAX 的角度度量。追踪搜索窗口,分清确切极大极小值与足够作判断的界。反转每组兄弟节点的访问顺序,改变计算工作而不改变游戏本身。
显示层只改变你能看见的信息,不会替模拟搜索读取叶节点,也不改变计数。
MAX–MIN 交替的博弈树
根 R 是 MAX;A、B 是 MIN;下一层是 MAX。▶ 与粗边框表示当前调用;虚线框与 × 表示已剪枝节点。隐藏收益用 ? 表示,已读取的叶节点显示确切收益;◇ 表示仅由学习显示层揭示、搜索尚未读取的收益。v 表示当前累计值;内部节点的 =、≥、≤ 分别表示其真正极大极小值的确切值、下界及上界。下表提供相同信息。
下表提供相同的节点与搜索信息。 递归调用路径: 无. 已读取的终端收益数: 0; 已剪去的终端收益数: 0.
当前最佳值只是子节点返回值的累计比较,并非声称已知确切极大极小值。α、β 是继承的决策阈值;子树真值未必在该窗口内。
| 节点 | 角色 | 本次子节点顺序 | 搜索状态 | 进入时 (α, β) | 当前 α | 当前 β | 当前最佳子节点返回值 | 返回信息 |
|---|---|---|---|---|---|---|---|---|
| R | MAX | A, B | 尚未进入 | (—, —) | — | — | — | 尚未得到 |
| A | MIN | A1, A2 | 尚未进入 | (—, —) | — | — | — | 尚未得到 |
| B | MIN | B1, B2 | 尚未进入 | (—, —) | — | — | — | 尚未得到 |
| A1 | MAX | A1a, A1b | 尚未进入 | (—, —) | — | — | — | 尚未得到 |
| A2 | MAX | A2a, A2b | 尚未进入 | (—, —) | — | — | — | 尚未得到 |
| B1 | MAX | B1a, B1b | 尚未进入 | (—, —) | — | — | — | 尚未得到 |
| B2 | MAX | B2a, B2b | 尚未进入 | (—, —) | — | — | — | 尚未得到 |
| A1a | 终端 | 无 | 尚未进入 | (—, —) | — | — | — | 尚未得到 |
| A1b | 终端 | 无 | 尚未进入 | (—, —) | — | — | — | 尚未得到 |
| A2a | 终端 | 无 | 尚未进入 | (—, —) | — | — | — | 尚未得到 |
| A2b | 终端 | 无 | 尚未进入 | (—, —) | — | — | — | 尚未得到 |
| B1a | 终端 | 无 | 尚未进入 | (—, —) | — | — | — | 尚未得到 |
| B1b | 终端 | 无 | 尚未进入 | (—, —) | — | — | — | 尚未得到 |
| B2a | 终端 | 无 | 尚未进入 | (—, —) | — | — | — | 尚未得到 |
| B2b | 终端 | 无 | 尚未进入 | (—, —) | — | — | — | 尚未得到 |
- 根节点的确切极大极小值
- 尚未确立
- 已读取的终端收益数
- 0
- 已剪去的终端收益数
- 0
- 剪枝判断次数
- 0
- 递归调用路径
- 无
事件 1 / 36: 搜索开始前
尚未进入递归调用,也未读取终端收益。
为什么剪枝保留根节点值
终端节点的 V 是已给定收益;MAX 节点的 V 是各子节点值的最大值,MIN 则取最小值。这些递推式定义了本图有限、确定、双人零和、信息完全且交替行动的博弈之极大极小值。所有收益都以 MAX 为准,所以 MIN 也比较同一组数值,并选择较小者。
继承窗口 (α,β) 记录祖先已有的替代选择:MAX 有价值至少 α 的替代方案,MIN 有价值至多 β 的替代方案。这并不保证当前子树真值介于两者。MAX 一旦收到足以达到 β 的子节点返回值,MIN 就可使用既有替代方案避开此分支;未访问子节点即使隐藏更大值,也不能改变这个判断。MIN 若达到不大于 α 的值,MAX 同样可避开此分支;未访问的更小值不会使它更有利。因此 α≥β 时可剪去仍未访问的兄弟节点。只求极大极小值、而非列出全部平手最优行动时,等号已足够。
本图采用 fail-soft 搜索,返回当前见过的最佳子节点返回值,不把它截到窗口边界。设进入时 a<b,子树真值为 m,内部节点返回 r,其契约是:r≤a 则 m≤r;a<r<b 则 m=r;r≥b 则 m≥r。对子树高度归纳:叶节点提供确切值,MAX 以最大值结合子节点依据,MIN 以最小值结合;剪枝只需要上述单边界,落在窗口内的结果则为确切值。表格用进入时窗口保守标记内部节点的返回值,不使用已更新窗口。界可能刚好等于真值,标记并非声称两者必定不同。已读取叶节点一律标为确切值。
根节点从 (−∞,+∞) 开始。返回值有限,严格位于进入窗口内,所以上述契约保证它是确切极大极小值。重排兄弟节点不改变最大、最小值的递推式,却会改变何时找到有用的界。已剪枝节点不会被指定为零,也不会在同一次搜索稍后再访问。递归路径与叶节点计数描述模拟算法操作;绘制预设树及打开学习显示层则是另一回事。
严格不等式例子从左到右只读取八个叶节点中的五个,根值为 5;从右到左读完八个,根值仍为 5。正向搜索中,A2 返回 ≥6,但它的真值为 9;未读取的 9 不会改变 MIN 节点 A 已有的 5。等号例子从左到右时,α=β 已足以剪枝,根值为 4。负收益例子的根值为 −6;MAX 的累计初值必须是 −∞,不能是 0。
本图计算已读取的终端叶节点,以及确实尚有子节点未访问的剪枝判断。若最后一个子节点处理完后窗口才闭合,不会当作节省了工作。这些小例子展示顺序影响,并不保证一般加速幅度。最坏情况下 alpha–beta 仍须搜索整棵博弈树;良好排序则可能大幅减少工作。复制状态、排版与学习显示层都不计入计数。
即时检查:A2 返回 ≥6,是否表示它的确切极大极小值为 6?
不是。搜索只证明了下界;在严格不等式例子中,真值为 9。MIN 节点 A 已有价值 5 的替代方案,因此 6 与 9 的差异不会改变 A 的最小值。剪枝省去一次评估,并非把未见收益改成零。
当前事件记录(显示全部收益后可看完整追踪)
- 尚未进入递归调用,也未读取终端收益。
三个原创八叶博弈例子,都搜索至终端深度;不包括机会节点、启发式深度截断或重复状态缓存,也不声称能解决所有博弈。
例题详解
例题 1.1.9
(一致的路线估计)
边为 成本 、 成本 、 成本 、 成本 、 成本 。设 。每边均一致,包括 。A* 先取 ,再以 取 ,把 改善至 ,并发现成本 的目标。展开 后,目标改善至 。取出 才证实路径 的成本为 。较早发现成本 的目标不足以停止。
例题 1.1.10
(需要重新开启的可采纳估计)
边为 成本 、 成本 、 成本 、 成本 。取 。从 出发的真成本为 ,故估计可采纳。A* 先以成本 关闭 ,因其优先值 低于 的 ;随后发现成本 的目标。展开 后才找到成本 的 ;若不重新开启它,改善无法传至目标,便错误返回 ,而非 。失败的一致性不等式在 :。重新开启 便能修正结果。
下面的互动使用的图与上面两个例子不同:一致图的最优成本是 7,首次生成的目标成本是 10;不一致图中重新开启得到 5,拒绝改善已关闭状态则得到 6。比较两种停止策略并追踪队列,不要直接应用上例的数值。
让更好前缀传到目标
逐个队列或边事件追踪 A*,比较重开与永久关闭,以及移出目标与首次生成目标时停止。更便宜前缀尚未处理完,一条路径已可能看起来很有希望。
队列按 (f、保存 g、状态名称) 递增排列。每个被接受的严格改善都加入一项,相同或更差候选不加入。过时 g 会在目标测试前被拒绝。永久关闭演示甚至丢弃到已关闭状态的更便宜候选,因此保存 g 未必仍代表已观察过的最佳候选。
目前是初始前沿,没有上一事件。
有向图与目前事件
箭头是允许方向,标签是边成本。圆内显示状态与所选 h,G 多一圈。粗框/粗边标示目前事件,虚线节点尚未发现。完整表格列出保存成本、路径及展开状态。上下位置只作排版,不是计算 h 的坐标。
S→A: 2; S→B: 5; A→B: 1; A→C: 4; B→C: 1; B→G: 7; C→G: 3. 事件: 初始前沿只有 S,g=0。 .
h* 与最优成本仅用于核对,A* 只使用边成本、保存 g 与所选 h。恰好得到此例最优值,与所选规则具有一般正确性论证,是两项不同判断。
| 状态 | 已接受的保存 g | 所选 h | 优先值 f=g+h | 供核对的已知 h* | 目前关闭 | 出边展开次数 | 已记录路径 |
|---|---|---|---|---|---|---|---|
| S | 0 | 6 | 6 | 7 | 否 | 0 | S |
| A | 尚未发现 | 5 | 尚未发现 | 5 | 否 | 0 | 尚未发现 |
| B | 尚未发现 | 4 | 尚未发现 | 4 | 否 | 0 | 尚未发现 |
| C | 尚未发现 | 3 | 尚未发现 | 3 | 否 | 0 | 尚未发现 |
| G | 尚未发现 | 0 | 尚未发现 | 0 | 否 | 0 | 尚未发现 |
| 状态 | 条目保存的 g | 所选 h | 优先值 f=g+h | 目前过时 | 已记录路径 |
|---|---|---|---|---|---|
| S | 0 | 6 | 6 | 否 | S |
前沿表按下一次移出顺序排序。旧项留至移出才处理,返回目标时仍可能有过时项未移出。不可变路径记录让每个成本始终对应真正产生它的路径。
| 边 | 成本 c | h(起点) | h(终点) | 变换成本 c+h(终点)−h(起点) | 一致性成立 |
|---|---|---|---|---|---|
| S→A | 2 | 6 | 5 | 1 | 是 |
| S→B | 5 | 6 | 4 | 3 | 是 |
| A→B | 1 | 5 | 4 | 0 | 是 |
| A→C | 4 | 5 | 3 | 2 | 是 |
| B→C | 1 | 4 | 3 | 0 | 是 |
| B→G | 7 | 4 | 0 | 3 | 是 |
| C→G | 3 | 3 | 0 | 0 | 是 |
已到达事件
| # | 事件 | 状态 | 边 | 候选成本 | 条目/记录成本 |
|---|---|---|---|---|---|
| 0 | 初始前沿只有 S,g=0。 | — | — | — | — |
- 此例 h 可采纳
- 是
- 每边 h 均一致
- 是
- 所选规则具有标准最优目标论证
- 是
- 首次生成目标路径的成本
- 尚未返回
- 返回目标路径成本
- 尚未返回
- 供核对的已知最优成本
- 7
- 返回成本等于此例最优值
- 尚未返回
0: 初始前沿只有 S,g=0。 . 继续检查下一次移出或边检查。
可采纳性、一致性与安全目标测试
到 v 的已记录路径成本为 g(v),h(v) 估计剩余成本,A* 用 f=g+h。可采纳性指 0≤h(v)≤h*(v),且 h(G)=0。f 是完成这条特定前缀的下界,不一定是全局最佳答案的下界,因为该前缀本身可能已更昂贵。
一致性要求每边 h(u)≤c(u,v)+h(v),即变换成本 c_h=c+h(v)−h(u)≥0。沿路径加总时启发项相消,变换成本等于原成本+h(v)−h(S)。因此一致时按 f 排序等同在非负变换边上使用 Dijkstra,可将目前状态确定下来而不必重开。边表逐项核对,没有仅凭启发值更小就推断一致。
交互的五状态图的最佳目标路径为 S→A→B→C→G,成本 7。展开 B 首次生成成本 10 的目标,但 C 仍以 f=7 留在前沿。生成目标即返回就太早;移出目前最低优先值目标则等到 C 将 G 改善至 7。h=0 时,过时 B、C 项会在 G 前真正移出并被丢弃;原启发值下,返回目前目标时它们仍留在队列。
四状态图 h(B)=4 可采纳,因为 B→A→G 的真实剩余成本为 4,但 B→A 不一致:4>1+0。A 先以 g=3 展开并生成 G 成本 6,之后 B 找到 A 成本 2。重开 A 可将更好前缀传给 G,得 5;永久拒绝改善则将 A 保留为 3,返回 S→A→G 成本 6。重开优先值从 B 的 5 降至 A 的 2,正对应变换边成本 −3。
可采纳并允许重开时,为什么移出目标安全?假设返回目前目标成本 C 大于最优 C*。沿最优路径仍会有一个前沿项带最优前缀成本:展开更早最优前缀时会加入下一状态,即使它曾展开过。该 v 有 f(v)=g*(v)+h(v)≤g*(v)+h*(v)=C*,必须先于 f=C>C* 的目标移出,矛盾。须先丢弃过时项,而 h(G)=0 使目标优先值等于路径成本。不一致时永久关闭会破坏这个最优前缀前沿论证。
即时检查:h=0 是否让首次生成目标即返回变得安全?
不是。五状态图的零启发搜索仍先生成 10,才发现 7;四状态图却恰好先生成最优 5。一次成功不能建立一般停止规则。h=0 配合移出目标及正常改善策略,才回到 Dijkstra 的安全优先规则。
两个固定有限有向图,成本为正整数。所有可选启发值均可采纳,但局部一致性可能失败。搜索采用精确小整数运算,教学队列用排序数组及事件快照,不是堆性能比较。不实现任意图编辑、启发学习或网格动画。
例题 1.1.11
(确实成立的 - 截断)
MAX 根有两个 MIN 子节点。先读左边叶收益 ,得左子值 ,根下界为 。右子节点的第一个叶收益为 ,已给整个右子树上界 ,故可跳过其余叶。若未读叶为 ,右子值仍是 ;若为 ,右子值成为 。两者都不能改善根的选择,根值为 。
常见错误
反例模式
局部改善未必通往最佳状态
链状邻居 的得分依次为 。从 严格爬山会到 并停止,因两个邻居都较差;全局最大却在 。停止只证明没有允许的局部步骤能改善当前值。随机重启或扩大邻域可在实际中帮助,成功保证仍须另证。
常见错误
(在刚发现目标时便停止)
A* 必须在状态从边界集合取出时才检查目标,而不是在它被生成时。在上面一致路线的例题中,目标 最先以 被生成,但最便宜的路径成本是 ,要展开 后才找到。
常见错误
(用已知路线检验可采纳性)
可采纳性比较的是 与真正最优值 ,并非与已找到的某条路线的成本。在重新开启的例题中,从 最先找到的路线成本为 ,而 。若声称 ,它通过 的检验,却违反 。
常见错误
(把每一层都当作 MAX)
每层都取最大值,等于假设对手会合作。设 MAX 根有两个 MIN 子节点,叶分别为 与 ,则极小极大值是 ;每层都取最大值却会声称 ,而对手根本不必容许这个收益。
状态键要保留所有会影响未来的信息。深度截断的极小极大法只对截断树及指定叶评估精确,对完整游戏的预测仍受未搜索战术与评估误差影响。
时间与空间成本也要分开:A* 常保存大量边界及成本标记,深度优先游戏搜索可只保存与深度成正比的调用栈,另加行动生成及可选表格。若用置换表重用局面,必须区分精确值、下界及上界,也要记录剩余深度;剪枝所得界限不能随意冒充完整求值。
在最佳走法次序下,剪枝只需检查完整树叶子数的大约平方根。
自然的下一个问题
剪枝最多能省下多少叶子?
在最佳走法次序下,剪枝只需检查完整树叶子数的大约平方根。
在分支因子为 、深度为 、叶值互异的均匀树中,- 至少要检查 片叶子,完整极小极大则要检查 片。当 、 时,是 片中的 片。最佳情况需要有利的走法次序,而这事先并不知道;最坏情况仍要检查所有叶子。
总结
先说清每个数值的意义,再判断算法。A* 的 是已发现路径成本, 是剩余成本的下界估计,一致性容许永久关闭。极小极大值是面对对抗的保证,- 用界限省去不影响选择的工作。局部搜索只凭得分的改善并不提供全局证明。状态模型、停止规则及重复状态策略都是算法规格的一部分。
练习
练习 1.1.12
(在每步成本为一的四邻居方格上,证明到固定目标的曼哈顿(Manhattan)距离一致,即使部分格被封闭。从某状态根本无法到目标时,可采纳性如何解读?)
基础证明
解答(3)
- 1
检查一步合法移动
关键一步
记 。相邻格只有一个坐标改变一,绝对值的三角不等式给出 。
依据: 两项坐标差中只有一项改变,且最多改变一。
- 2
封闭格与路径
封闭格只删除边,所以保留下来的每条边上不等式仍成立,目标处 为零。沿一条由 到目标的 步合法路径,把不等式用 次得 ,因此 。
- 3
无法到达的状态
∎若从 根本无法到达目标,则 ,有限的估计 仍满足 。可采纳并不承诺路径存在。
练习 1.1.13
(对上面的不一致例题,求所有真正剩余成本,列出每条失败的一致性不等式,并追踪容许重新开启的 A*,直到取出目标。)
核心
解答(3)
- 1
求真正剩余成本
关键一步
。从 只有路线 ,故 。从 只有路线 ,故 。从 出发,路线 与 的成本分别是 与 ,所以 。
- 2
逐边检验
:。:。:。: 不成立。只有 不一致。
- 3
追踪容许重新开启的 A*
以 记标记。展开 后有 、;展开 得 ;展开 把 改善并重新开启为 ;再展开 ,把 改善为 。取出 返回成本 。优先值在展开后下降,正反映一致性不成立。
快速检查
(MAX 根的三个 MIN 子节点,叶列表为 、、,按左至右搜索。求根值,并列出以无穷初始界限执行 - 时跳过的叶。)
解答 · 答案
三个子值为 ,根值为 。左边两叶均须读取,才确立根下界 。中间子节点的第一叶 已不大于此界,可跳过叶 。最后一组先读 不能截断,仍要读叶 才定出其值。因此只跳过一片叶,即 。在 MIN 节点看见一个高收益回应,不代表其他回应也高。
练习 1.1.14
(若 都是非负、一致且目标为零的启发式,证明它们逐点最大值仍一致。它们的和必定可采纳吗?给明确例子。)
核心
解答(3)
- 1
选取达到最大值的下标
关键一步
令 ,并固定一条边 。选下标 使 ,则 。
依据: 每个 都一致,而 是最大值,故 。
- 2
检查其余性质
非负函数的最大值仍非负;在目标处两者皆为零,故 亦为零。所以 是一致且目标为零的启发式。
- 3
检验它们的和
取只有一条成本 的边 ,两个估计在 均为 、在 均为零。各自精确且一致,但其和在 为 ,超过真成本 。最大值可安全结合这些下界,相加则需要额外的成本分解依据。所以和不一定可采纳。