← 图形原理 · 交互课 课题十一 · 寻路 · 第 2 课

猜一个数：让搜索朝终点走

全课题骨架：寻路不是"找一条路"，而是"给地图上每个位置记一个数"，而记数只有一条规则 —— 从已经确定的那一圈往外推一格，给新格记下它自己的数。
上一课的缺口很直白：泛洪朝四面八方推，而终点只在一个方向 —— 它把 965 个格全定了数， 其中绝大多数与最优路径毫无关系。这一课只补一件事：让每一格的数里，再加一项"从它到终点还要花多少"的猜测， 取的时候按"已经花的 + 猜的还要花的"来取 —— 搜索就朝终点那边偏过去了。
四段路：先把这一项加上（25.1）→ 问"猜多少才合适"（25.2）→ 问"猜过头会怎样"（25.3）→ 干脆把它当旋钮用，并给出一个上界（25.4）。
★ 量出来才敢写的一件事：加了这个猜测之后，要定的格从 965 降到 233（少算 75.9%），而解一模一样 —— 代价都是 47；而且有一条完全独立的路线把这个 47 又算了一遍（从终点反向泛洪，得到 h*(起点) = 47）。 另一件同样重要：猜测越过"不高估"这条线之后，答案就真的会坏 —— 实测 k = 1.25 那档虽然已经有 841 个格被高估，却仍然给出最优解；一直到 k = 1.5 才坏（代价 52，比最优贵 5）。 也就是说"不可采纳"丢掉的不是"答案"，而是"保证"。 保真度：示意 · 等价重现 —— A*、反向泛洪、参考解都是纯图算法 （页面现场跑的十条与离线定稿 q112.mjs 同口径），画面是本页自己的二维软件光栅， 不是任何引擎或导航库的内部实现。 ★ 本页与第 1 课同一张地图、同一套价（泥地 ×4）—— 所以 965 / 47 这些数可以两页对照着看。 ★ 本页不做对角走位、不做 JPS（那是第 3 课）；平局怎么断本页钉死成"下标最小的那个" （一手源原话："Resolve ties arbitrarily, but always in favor of any node n ∈ T"），换断法会改工作量、不改代价。

分段：
推进： ｜画面里深色那一块是 A* 定的格，最淡的一层是第 1 课泛洪定的格（用来对照）

（脚本启动中…）

定点观察：（脚本启动中…）

本帧的读数

（脚本启动中…）

25.1 段 · 给数加一项"猜"

本段只增加一样东西：那个猜测 h（读者只动「单步 / 跑到底」，段内 k 固定在 1、W 固定在 1）。 保真度：示意 · 等价重现。上一课取的是"d 最小的待定格"，也就是只按已经花了多少排队； 本段把队列的键换成 f = g + h：g 是"已经花了多少"， h 是"从这一格到终点还要花多少"的猜测。取最小的仍然是同一句话，只是那个"数"里多了一项。
★ 一手源把这两件事写成一句（HN R 1968 原话）："We can write f(n) as the sum of two parts: f(n)=g(n)+h(n)"， 以及取的时候 "Select the open node n whose value of f is smallest."
★ 本段的猜测取最朴素的那个：h = 曼哈顿距离（横格数 + 竖格数）。 它为什么"不算高估"？因为每走一步至少要花 1（本页最便宜的格也是 1）—— 所以"还要走几步"永远不会超过"还要花多少"。
★ 实测：泛洪定 965 格，A* 只定 233 格（少算 732 格，75.9%）， 而两者的解代价都是 47。另有第三条独立路线给这个 47 作证：从终点反向泛洪得到的 h*(起点) = 47，与它逐位相等。

输入 同一张网格 （与第 1 课逐格相同） 每格记四样 g 已经花了多少 h 还要花多少（猜） f = g + h（排队用） par 从哪儿来的 猜的是什么 曼哈顿距离 横格数 + 竖格数 为什么它不高估 每走一步至少花 1 ⇒ 步数 ≤ 花费 见判据① ② ① 排队那一句没变，只多了一项（本页真跑的 step，逐字） st.step = function () { let n = -1, best = Infinity; /* ① 取 f 最小的待定格 */ for (let i = 0; i < N; i++) if (!done[i] && f[i] < best) { best = f[i]; n = i; } if (n < 0) return false; done[n] = 1; seq.push(n); st.settled++; if (opts.early && n === goal) return false; for (let k = 0; k < 4; k++) { /* ② 唯一那条规则 */ const m = nbr(map, n, k); if (m < 0) continue; const w = wOf(map, m, opts.weighted); if (w === Infinity) continue; const cand = g[n] + w; if (cand < g[m]) { g[m] = cand; par[m] = n; f[m] = cand + W * H[m]; /* ★ 只多了这一项 */ } } return true; }; 右列读数 泛洪已定 965 格 A* 已定 233 格 少算 732（75.9%） 解代价 47 = 参考解 C* 反向泛洪 h*(起点) 47（第三条路线） h 高估的格数 0 ⇒ 可采纳 见判据① ② ③
件一：25.1 只改了取数的键。左列是每格记的四样（注意 f = g + h）， 中间是本页真跑的 st.step（逐字），右列是实测。 高亮那一行就是本课的全部改动：f[m] = cand + W * H[m]; —— 上一课是 d[m] = cand;，差别只在排队用哪个数。
件三 · 表① 加了"猜"之后的账（h = 曼哈顿、W = 1）。"反向泛洪"那一行是第三条独立路线： 它不看起点、只看终点，独立地算出同一个 47。
记的账应然实测结论怎么算类别

定点观察：① 按「跑到底」（再按「单步」可以从头看过程）； ② 看画面里深色那一块（A* 定的格）与最淡那一层（第 1 课泛洪定的格）的形状差别； ③ 结论：加了"猜"之后，搜索只朝终点那一侧铺开，定的格从 965 降到 233，而解一位不差。

25.2 段 · 猜多少

本段只增加一样东西：一个滑块 k（h = k × 曼哈顿，段内 k 只能在 0 与 1 之间动）。 保真度：示意 · 等价重现。上一段的猜测是"每步至少花 1"这个最保守的估法；可你要是猜得比它小呢？ k = 0 就是"完全不猜"（退回上一课），k = 1 是上一段那一档，中间是各种"猜一点"。 本段开页就在 k = 0 那一端（你会看到画面与上一课的泛洪一模一样），从那儿往右拖即可。
★ 这一段真正要看的是一件反直觉的事：拖这个滑块，解代价一格都不动（全是 47）， 动的只是"要定多少格" —— 774 → 696 → 626 → 536 → 233。 也就是说"猜得准"买到的不是"答案更好"，而是"算得更少"。
★ 为什么一整段都安全？因为这一整段的 k 都落在同一个区间里：h 从不高估 h*（"可采纳"）。 本段还顺手把这件事数出来了：逐格检查 h > h* 的格数，五档全部是 0。
★ 顺带一条自洽：k = 0 那一档的"已定 774 格"必须等于上一课那条早退泛洪的读数 —— 实测两档都是 774，代价也都是 47。

输入 上一段的猜测 h = 曼哈顿距离 + 一个系数 k h = k × 曼哈顿 k 的两个端点 k = 0 完全不猜 （退回第 1 课） k = 1 上一段那一档 这一段为什么安全 k ≤ 1 ⇒ h 从不高估 ⇒ 答案一位不变 买到的不是答案 是"算得更少" 见判据④⑤ ① 猜测本身（本页真跑，逐字） function hManhattan(i, goal) { const x = i % MW, y = (i / MW) | 0; const gx = goal % MW, gy = (goal / MW) | 0; return Math.abs(x - gx) + Math.abs(y - gy); } ② 本段加的那一层（本页每帧都重算一遍） function hScaled(goal, k) { const N = MW * MH; const out = new Float64Array(N); for (let i = 0; i < N; i++) out[i] = k * hManhattan(i, goal); return out; } ③ "不高估"这句话是数出来的，不是感觉出来的 逐格比较 h 与 h*（从终点反向泛洪得到） 五档的"高估格数"全是 0 ⇒ 落在可采纳区 解代价五档全是 47 —— 一位不变 右列读数 k = 0.00 已定 774 · 解 47 k = 0.25 已定 696 · 解 47 k = 0.50 已定 626 · 解 47 k = 0.75 已定 536 · 解 47 k = 1.00 已定 233 · 解 47 高估格数五档全 0 见判据④ ⑤
件一：25.2 只加了一个系数。五档的解代价都是 47，变的只有"已定"那一列 （774 → 696 → 626 → 536 → 233）—— 这就是"可采纳区"里拖滑块能看到/看不到的东西。
件三 · 表② 猜多少（k ≤ 1，全程可采纳）。整列"解代价"都是 47，整列"高估"都是 0 —— 这两列不动的地方，才是本段的正题。
记的账应然实测结论怎么算类别

定点观察：① 拖「猜多少 k」那个滑块（从 0 拖到 1）； ② 看画面里深色那一块怎么从一大片收成一条朝终点的带，同时盯住读数里的"已定"与"解代价"； ③ 结论：解代价一格都不动（全是 47），动的只是"要定多少格" —— 猜得准买到的不是"答案更好"，而是"算得更少"。

25.3 段 · 猜过头

本段只增加一样东西：滑块的量程被放开到 1 以上（越过"不高估"那条线；其余控件与上一段完全相同）。 保真度：示意 · 等价重现。上一段那一整段安全，是因为 k 一直被压在 1 以内。本段把这条线跨过去 —— 猜测开始高估，而高估正是最优性证明里唯一不能碰的东西。
★ 结果比"会坏"更值得记：它不一定坏。k = 1.25 那一档已经有 841 个格被高估（"不可采纳"已经成立）， 可它仍然给出最优解 47；一直到 k = 1.5 才真的坏：代价 52，比最优贵 5。
★ 所以"可采纳"丢掉的不是"答案"，而是"保证"：越过那条线之后， 算法可能给出次优解 —— 具体坏不坏、坏在哪一档，只能量。
★ 一手源把"不高估"写成一句（HN R 1972 勘误原话）： "if the heuristic function ĥ(n) is a lower bound on the true minimal cost from node n to a goal node, then A* is admissible; i.e., it would find a minimal cost path if any path to a goal node existed."
★ 本段的读数多了一格："高估的格数" —— 逐格比较 h 与 h*（h* 由"从终点反向泛洪"独立算出）。 它从 0 变成 841 / 941 / 964，而解代价在 1.25 那一档还不动。这两个数并排看，才是这一段的全部内容。

输入 同一个滑块 量程放开到 3 那条线是什么 h* 真实还要花多少 从终点反向泛洪得到 可采纳 = 这条 h ≤ h* 逐格成立 越过之后 不再有"最优"保证 但不是必然坏 坏不坏、哪一档坏 只能量 见判据⑥ ① 本段新增的读数：高估了几个格（本页真跑，逐字） function overCount(map, H, HS) { let n = 0; for (let i = 0; i < MW * MH; i++) { if (map[i] === WALL || HS[i] === Infinity) continue; if (H[i] > HS[i] + 1e-9) n++; } return n; } ② 那条线 h* 是怎么来的（同一份真源码里） R[goal] = 0; const cand = R[u] + wOf(map, u, weighted); /* ★ 反向：加的是"被推出的那一格"的价 */ ③ 结论（右列）：这条线上的两个数要并排看 高估格数 > 0 ⇒ 不再有最优保证 解代价是否变贵 ⇒ 另说（要量） k = 1.25 高估 841 格，却仍是最优解 右列读数 k = 1.25 高估 841 格 解 47（仍最优） k = 1.50 高估 941 格 解 52（贵 5） k = 2.00 高估 964 格 解 52（贵 5） k = 3.00 高估 964 格 解 52（贵 5） 见判据⑥
件一：25.3 的中间那一格是本段新增的读数 —— 逐格数出 h 高估 h* 的格数。 右列两列并排看：高估格数很快就不再是 0，而解代价要到 k = 1.5 才动。
件三 · 表③ 猜过头（k > 1）。"高估"与"仍最优"是两件事 —— k = 1.25 那一行就是这句话的证据。
记的账应然实测结论怎么算类别

定点观察：① 把「猜多少 k」拖过 1（一直拖到 3）； ② 看读数里"高估的格数"与"解代价"这两列—— 前者立刻不再是 0，后者要过一会儿才动； ③ 结论：越过"不高估"这条线丢掉的不是答案，而是保证 —— k = 1.25 已经有 841 个格被高估，却仍然给出最优解；到 k = 1.5 才真的坏（贵 5）。

25.4 段 · 把它当旋钮用

本段只增加一样东西：权重 W（f = g + W·h，W ≥ 1；上一段那个 k 滑块不动）。 保真度：示意 · 等价重现。上一段把"猜过头"当成一种错误；本段换个身份看它： 它是一个旋钮 —— 你故意多信一点猜测，换更少的计算量，代价是解可能不是最优的 但不至于离最优多远：C ≤ W · C*。
★ 一手源原话（Pohl 1970 的加权 A\*，转引自 Chen / Sturtevant / Doyle / Ruml《Revisiting Suboptimal Search》2019）： "WA* uses a priority function of f(n) = g(n) + w · h(n) and returns w-optimal solutions, or solutions that are no more than w times longer than the optimal solution."
★ 实测（C* = 47）：W = 1 → 解 47（恰好是最优）｜W = 1.25 → 47｜W = 1.5 → 52｜ W = 2 → 52｜W = 3 → 52。五档全部落在自己的界里（W = 1.5 那一档的界是 70.5，实测 52， C/C* = 1.106）。
★ 最能看出"旋钮"性质的是两个列的方向相反：W 从 1 拖到 3，要定的格从 233 掉到 41（省了 82%）， 而解代价最多也就多 10.6%。这就是工程上真正在做的那笔交换。
★ 一个边界要写清：那个界只跟 W 有关，跟上一段的 k 无关 —— 页面上两个滑块都在， 你若把 k 拖到 0.5、W 拖到 2，界仍然是 2·C*。

输入 上一段的猜测 （系数 k 不动） + 一个权重 W f = g + W × h 换到了什么 算得更少 （已定 233 → 41） 代价是什么 解可能不是最优 但不超过 W 倍 界从哪来 h 不高估 ⇒ f 也不超过 真代价的 W 倍 见判据⑦ ① 与 25.1 / 25.2 只差这一个 W（本页真跑，逐字） const H = opts.h, W = opts.W; g[start] = 0; f[start] = W * H[start]; const cand = g[n] + w; if (cand < g[m]) { g[m] = cand; par[m] = n; f[m] = cand + W * H[m]; /* ★ 只多了这一项 */ } ② 本段新增的那个读数：上界 C ≤ W · C* （W = 1 时就退回 C = C*） ③ 为什么它成立（一句话） h 不高估 ⇒ 每条路径的 f 都不超过 它真代价的 W 倍 ⇒ 取出来的那条 路，代价 ≤ W · C* 界只跟 W 有关，与上一段的 k 无关 右列读数 W = 1.00 已定 233 · 解 47 界 47.0 · 1.000000 W = 1.50 已定 164 · 解 52 界 70.5 · 1.106383 W = 2.00 已定 98 · 解 52 界 94.0 · 1.106383 W = 3.00 已定 41 · 解 52 界 141.0 · 1.106383 见判据⑦
件一：25.4 的唯一改动还是那一行（多了个 W）， 但本段新增的是读数里多了一格"上界"。右列两列方向相反： 已定从 233 掉到 41，解代价最多涨 10.6%。
件三 · 表④ 权重 W 与上界。最后一列是"实测 ÷ 最优"， 把它和"界"那一列并排看：实测始终贴着界下面一点点。
记的账应然实测结论怎么算类别

定点观察：① 拖「权重 W」那个滑块（从 1 拖到 3）； ② 同时看画面里深色那一块怎么继续收，以及读数里"已定"、"解代价"、"上界"三个数； ③ 结论：要定的格从 233 掉到 41，而解代价从 47 只涨到 52（+10.6%）， 并且始终落在 W·C* 这条界下面 —— 这就是"故意不最优"的工程形态。

本课的收尾

这一课只补了一件事：让每格的数里多一项"到终点还要花多少"的猜测，取的时候按 f = g + h 取。四段把这一项从"是什么"问到"猜多少"、"猜过头"、"当旋钮"。
往下的缺口：猜测必须逐格算、逐格存，而且网格上还有大量互为对称的格 —— 同一对起终点、代价完全相同、只是"先横走还是先竖走"的差别。A* 会把它们一个一个评估过去。 下一课（第 3 课 · JPS）要剪掉的就是这一大批对称： 只在一部分点上记数，跳点之间的格一个都不展开（一手源原话："Intermediate nodes on a path connecting two jump points are never expanded."）。
★ 本页留了一个可以自己动手的口子：把「猜多少 k」拖到 0，你会看到画面退化成第 1 课那一大片 （已定从 233 涨回 774）—— 这就是"第 1 课是这一课的特例"这句话的图像。

自检面板

等待脚本…