CSCI3230 L10 · Part 2/4 Greedy best-first search

课程：CSCI3230 (ESTR3108) Fundamentals of Artificial Intelligence · 2025T1 本讲：L10，第 2 部分 / 共 4 部分 · 原件 L10-Informed-Search-2025T1.pdf（本地课件） p.12–25 定位：只看h，不计已经付出的代价。 前后：上一份 Introduction · 下一份 A-star search

版本边界：本篇依据2025T1旧课件作预习与基础补课，不表示2026T1已经讲到这里；今年范围以今年教师公告为准。页码均为原PDF页号。

Greedy best-first

每次挑“看起来离目标最近”的候选（p.12–14）

p.12为分节页；p.13定义贪心最佳优先搜索，p.14从Arad到Bucharest开始示范。先复习启发函数：$h(n)$ 是当前位置到目标的估计剩余成本，不是已经走过的距离。

贪心规定 $f(n)=h(n)$。这是同一个标量被用作队列优先级。假设候选A已走100、估计还剩1，B已走2、估计还剩5，贪心仍先选A，因为它不把过去100放进排序。它有时很快到目标，却可能付出很贵的总代价。

“贪心”也不意味着只看当前节点的邻居，选完就丢掉其他路。它维护完整frontier，每次从所有尚待处理的候选里取最小 $h$。当前分支死了，仍可回到别的候选。

把罗马尼亚地图变成候选表（p.15–18）

图（p.15–18）：根Arad的孩子为Sibiu/Timisoara/Zerind；Sibiu又有Arad/Fagaras/Oradea/Rimnicu；Fagaras连Bucharest。节点标签为到Bucharest的直线距离估计。 看什么：原图会再画回Arad/Sibiu的重复节点；以下按图搜索跳过已处理状态，使待办表更容易读。

这里统一取出时验目标；课件p.18在生成目标时结束，因为该演示中它的 $h=0$ 会成为最优先候选。无论哪种时机，贪心本身都没有成本最优保证。

返回Arad→Sibiu→Fagaras→Bucharest。Timisoara一直在frontier中，并没有因选择Sibiu而消失；只因h更大一直没轮到。

小启发值怎样把算法拉进环（p.19–22）

图（p.19–22）的关键连线是S与A相连、S与B相连，h(S)=2、h(A)=1、h(B)=3；课件搜索树重复展开S与A。 看什么：树搜索未排除重复，A看起来比B好，从A回S又比B好。

具体队列：取S后[A1,B3]；取A后[S2,B3]；取S后[A1,B3,B3]。于是不断优先处理A/S，B分支被搁置。这不是“启发值每步都下降”：从A1回S2明明上升了，但S2仍比等待的B3小。要比较的是整个frontier，而不是本步与上一步的h。

p.19原启发表完整列S:2、A:1、B:3、C:2、D:2、E:2；但对应图右上末节点又写成B，没有清楚标出正文声称的目标G。因而这张图足以证明所画S↔A循环会饿死等待的B分支，却不足以凭标签复原一条明确到G的完整成功路线。保留这一原图缺口，不擅自把E或第二个B改名成G。

有限可达图配合全局去重，可以消除此类环并最终处理全部可达状态；不能把课件一般情形的“不完备”误背成“任何有限图去重实现都不完备”。无限空间则仍可能有无限多看似更好的候选，有限分支本身不足以使贪心完备。

看起来接近，为什么会多走32（p.23）

p.23给的贪心路线道路成本为140+99+211=450；另一条经Rimnicu Vilcea、Pitesti的路线为140+80+97+101=418。450−418=32。地图道路数字按公里解释；该页正文写miles，与地图沿用单位不一致，不能混用单位。

在Sibiu后，Fagaras的h178低于Rimnicu的193，所以贪心先Fagaras；它不考虑后续实际道路绕法，也没有比较整条路线成本。这解释的是失败机制，不是说贪心永远选差路线。

补充 · 单调变换启发值为什么不改变基本排序（通识讲解；演示数据不属于原题）。

贪心只比较 $h$ 的大小。若所有候选的启发值都乘同一个正数，或都加同一个常数，严格大小关系不变，因此在其他实现规则相同的情况下，选择顺序不变。演示候选启发2、5变成20、50，仍先取第一项；它没有因为数字看起来更精确而多利用已经走过的成本。

但不能把这个结论照搬到 A*。那里排序的是 $g+h$，只放大 $h$ 会改变它与 $g$ 的权衡，可能改变路径和最优性保证。还要保留平局规则：原来相等的启发仍相等，谁先取出仍需约定。比较实验时应说明算法实际用的优先级表达式，不能只看函数名叫heuristic。

补充：启发完全准确，贪心也可能选贵路

自编有向图S→A成本100、A→G成本1；S→B成本1、B→G成本2。令启发恰好等于真实剩余成本：$h(A)=1,h(B)=2,h(G)=0,h(S)=3$。所有值都准确，当然也不高估。

贪心取S后只比较A的1与B的2，先取A；随后生成G，启发0，比B的2小，于是返回S→A→G，总成本101。另一条S→B→G总成本3，却没被选。失败原因不是剩余估计不准确，而是排序完全没有计入已走成本100。

A*在同图中比较 $f(A)=100+1=101$ 与 $f(B)=1+2=3$，先B再G，返回3。这个反例比“启发可能骗人”更明确：即使估计没有任何误差，只优化剩余部分也不能保证完整路线最优。启发质量与队列优先级的设计是两个独立问题。

为什么最坏仍可能很慢（p.24）

设最大分支数 $b$、有限搜索树最大深度 $m$。极差的启发如所有 $h=0$，不能区分候选，最坏仍遍历整棵树，时间 $O(b^m)$。还要保存frontier与搜索记录，空间最坏也为指数阶。形状“像一路往下”不意味着具有DFS的线性深度空间，因为贪心仍保留很多被推迟的其他候选。

一个更准确的h可能减少实际扩展，但要花成本计算h。不存在“用了启发就一定更快”的无条件保证。

课堂带权图：先只读节点旁的数（p.25）

p.25 If the initial node is node B, what is the solution if use greedy best-first search?

这是同页完整题干中的问题句；题干说明节点旁数字为到G的启发、边旁数字为成本。原选项A.BEFHG、B.BCFHG、C.BCDHG、D.BADHG。

图（p.25）：无向图，起点B、目标G。启发值A12/B19/C13/D6/E6/F4/H3/G0。边BA6、BC5、BE10、AD6、CD6、CF7、EF6、DH4、FH6、HG3。 看什么：边没有箭头，不要擅自只许从左向右；实际图搜索用visited跳过回头重复。

成本另算：10+6+6+3=25，选A。注意C虽然一直等待，却没有被“当前图像中更靠左”之类视觉理由排除；它只是h13较大。下一份A*用同图比较，就能看到加上g后顺序怎样改变。

本讲核心考点

• 排序只看h，仍从完整frontier选择（p.13–18，C级）。
• 完备性受重复处理及有限/无限空间影响（p.19–22，C级）。
• 总成本必须沿最终父链另加，不能把h之和当成本（p.23–25，C级）。

附录

补充检查：在p.25图把B→E的成本从10改成100，而所有h不变，贪心的选择会怎样？

来源与证据

• 原件：L10-Informed-Search-2025T1.pdf（本地课件），具体页码标在各节。原课件保留本地。
• 例子标为“补充”时是为帮助理解而选取，不是教师题目或2026T1要求。
• 考试证据：本轮只核对上述讲义，没有据此预测今年考题；练习与自检均为通识（C级）。