CSCI3230 L10 · Part 1/4 Introduction

课程：CSCI3230 (ESTR3108) Fundamentals of Artificial Intelligence · 2025T1 本讲：L10，第 1 部分 / 共 4 部分 · 原件 L10-Informed-Search-2025T1.pdf（本地课件） p.1–11 定位：用剩余成本估计引导搜索，但先检查估计的含义。 前后：下一份 Greedy best-first search

整讲导航：

• 1. Introduction：p.1–11。
• 2. Greedy best-first search：p.12–25。
• 3. A-star search：p.26–45。
• 4. Summary：p.46–48。

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

额外知道什么

已经花多少，还不够判断哪条路值得试（p.1–4）

p.1–3给本讲四部分路线：启发函数、贪心搜索、A*、小结。p.4要解决的是L09留下的低效：即使两个候选已经付出的成本相同，它们离目标也可能一近一远。若能便宜地估计“剩下还要花多少”，就可以少试一些明显绕远的方向。

先准备三个词：状态是现在世界的情况；路径节点还记录怎样到达；frontier是等待处理的候选。启发函数的作用不是替你求出完整最短路线，而是给每个候选一个有根据的估计。如果必须先解完整问题才算得出估计，就失去了帮助搜索的意义。

看得见目标，仍可能被墙挡住（p.5–6）

p.5让起点S在“向上”和“向右”两个同成本动作之间选择。只知道已走成本，两者难分；p.6补上目标位置，就有朝目标方向试的理由。

但“位置更接近”只是线索，不是保证：前面可能有墙，暂时离目标更远反而能绕过去。这里必须区分直觉和数学保证。直觉帮助构造估计；要保证最优，还要检查估计是否高估，以及搜索算法怎样使用它。

距离估计先从最熟悉的坐标开始（p.7）

图（p.7）：迷宫中一条水平差标10，一条竖直差标5，直线标11.2；蓝线是障碍，红线是用来说明距离的几何线段，并非全部合法走道。 看什么：忽略障碍可以给下界，不能把穿墙红线当成实际解路径。

设当前位置坐标 $(x,y)$、目标 $(x_G,y_G)$，每个坐标分量是一个位置数。四方向、每格成本1时，至少要消除水平差与竖直差，因此曼哈顿距离为

绝对值让差的方向不影响长度。用图中差值代入，$h_M=10+5=15$。这15的单位是格/单位步成本，不是“概率”。墙可能要求更多步，但不可能让必须消除的水平与竖直差凭空消失。

欧氏距离是平面直线长，由勾股定理得到

课件显示11.2是四舍五入。直线通常更乐观，因为它连“四方向走”这条约束也放松了；曼哈顿距离保留了四方向限制，所以在这种动作规则下通常更贴近真实成本。

改变动作，必须重新检查估计。 补充例：若允许每次沿对角线移动一格且成本1，从(0,0)到(1,1)只需1步，曼哈顿给2便高估了。不是公式算错，而是公式假设与问题不匹配。若边成本是时间，还要考虑速度；不能把公里直接加到小时。

一个函数究竟输入输出什么（p.8）

$h(n)$ 表示从当前节点状态到某个目标的估计最低剩余成本。输入是状态，输出是标量；到达目标后剩余任务已经为0，所以规定 $h(G)=0$。同一状态在不同路径中出现，通常有同一个 $h$，但已付成本 $g$ 可以不同。

补充数值：你先走了7公里到X，估计还需3公里；这里 $g(X)=7,h(X)=3$。若另一条路线用了5公里到同一个X，$h(X)$ 仍是3，但新 $g(X)=5$。不要把“当前累计”记进 $h$，否则后面加 $g+h$ 时会重复计算。

真实的最便宜剩余成本常写 $h^{\ast}(n)$。星号表示理想真实值，不是我们已经能轻易算出的输入。启发函数是估计它；A*再讨论什么估计可以保证最优。

煎饼排序：排序提示不一定是次数下界（p.9–10）

p.9问题是把不同大小煎饼按小上大下排序；一个动作可以翻转栈顶某个长度的前缀。p.10有四个大小10、15、25、35，按由小到大编号1、2、3、4。课件的启发是“仍然放错位置的最大煎饼编号”。例如4在正确底部但3错位，值可能为3；全对则为0。

原图p.10的全部示例状态可用从栈顶到底部的编号重建；下表按启发值分组，编号1/2/3/4对应大小10/15/25/35：

双向箭头表示一次前缀翻转可逆。例如(4,1,2,3)翻前4个得(3,2,1,4)，h从4到3；后者翻前3个就直接到目标，h从3到0。另一条为(3,2,1,4)翻前2个→(2,3,1,4)，再翻前3个→(1,3,2,4)，翻前2个→(3,1,2,4)，翻前3个→(2,1,3,4)，翻前2个→目标。图只画了部分状态和转换，不是四煎饼的全部24种排列。

这个量表达“还有多大的煎饼没摆好”，不是直接数“还要几次翻转”。补充反例：从上到下为(4,3,2,1)，一次整体翻转得到(1,2,3,4)，实际只需1次；但最大错位编号是4。若每次翻转成本1，这个启发就高估了。

p.33再次将同类煎饼图放在可采纳启发页，但未在这里给出足以使该编号成为翻转成本下界的代价约定。不能仅凭摆在定义页就认定它在单位翻转成本下可采纳。它可以作为排序信号，是否是安全成本下界还要另证。

补充 · 启发值必须与真实代价使用同一种单位（通识讲解；演示数据不属于原题）。

若真实路径代价是时间，直线距离本身不是时间下界。需要一个合理的速度上界，才能用“距离除以最大速度”得到乐观所需时间；不能把3公里直接与10分钟的已走成本相加。若代价是每步1的网格移动，曼哈顿距离才可能以步数为单位，而允许对角移动又会改变下界关系。

这也解释了启发函数与行动模型不可分。一个估计在只能上下左右走的地图上安全，增加更快的传送行动后可能高估。检查启发先问代价单位、允许动作和目标条件，再问数值是否“大概像距离”。“看起来直观”不足以证明它不高估真实最优余程。

补充：放松动作限制为何能构造安全下界

从原任务出发，只移除限制、不增加动作成本，使原来的每条合法解仍然是新问题的一条合法解。新问题可选路线更多，所以其最优成本不可能大于原问题最优成本；拿这个较容易问题的最优值作 $h$，就得到下界。关键是包含原可行解，不能口头说“更简单”便跳过这个关系。

自编四邻接网格，每步成本1，从 $(1,2)$ 到 $(4,6)$。无障碍时至少要改变横坐标3次、纵坐标4次；每步只改变一个坐标，故至少7步，而先横后纵确实可用7步到达，放松问题最优值就是曼哈顿距离7。加墙只可能限制路线，不能产生少于7步的四邻接解。

若允许对角一步也只花1，那么可先走3次对角、再走1次纵向，共4步，曼哈顿7就高估了。不是坐标公式自己变错，而是动作定义变了。构造启发时先写合法动作和成本，再问放松了什么，才能判断下界是否仍成立。

h提供信息，f决定排队（p.11）

评价函数 $f(n)$ 是frontier用来排序的分数。$h$ 是其中一种信息来源，不等于每个算法的最终优先级。接下来：贪心用 $f=h$，只问“看起来还多远”；A*用 $f=g+h$，同时算“已经花的”和“估计还要花的”。UCS则用 $f=g$。

补充比较：候选A已花9、估还需1；候选B已花2、估还需5。贪心觉得A的未来1更小，先A；A*算A总10、B总7，先B。改变的不是图，而是排序问题。

检验自己是否分得清这三个数，见附录 A1。

本讲核心考点

• 启发是便宜的剩余成本估计，几何接近不等于路径已经合法（p.4–8，C级）。
• 每个估计都依赖动作规则、成本单位与目标定义（p.7–10，C级）。
• $g$ 记过去，$h$ 估未来，$f$ 是算法真正使用的排序值（p.11，C级）。

附录

A1 改变到达方式时什么会变

补充检查：同一地点X原来由8公里路线到达，现在发现6公里路线；到目标直线仍为4公里。哪些数会改变？能否说真实总路线就是10公里？

历年概念问法：多知道了什么（非讲义内容）

题面（ESTR-Final-Exam-2023T1.pdf · Part II Q8 · p.5，扫描件视觉核对）：

p.5 What is the main difference between informed search and uninformed search? What is the benefit of informed search compared with uninformed search? (4%)

先别把英文句子背成“informed更聪明”。要明确多出来的是问题专属的剩余成本估计；UCS虽知道已走成本，仍属uninformed，因为那些成本本来就是问题定义的一部分。

回到正文

来源与证据

• 原件：L10-Informed-Search-2025T1.pdf（本地课件），具体页码标在各节。原课件保留本地。
• 例子标为“补充”时是为帮助理解而选取，不是教师题目或2026T1要求。
• 考试证据（沿用既有笔记的历史核对记录）：视觉核对 ESTR-Final-Exam-2023T1.pdf p.3–5中本篇引用的搜索题；仅证明ESTR旧卷相应问法出现过（A级，扫描件），不据此预测今年CSCI3230考题。 补充练习与自检均为通识（C级）。