08 · 启发式怎么设计
⏱ 29 分钟 | 阅读参考,不是完成时限;先会算一个例子,再按需要看证明和实验。
🎯 一句话
先解一个规则更宽松的问题,得到“至少还要花多少”的下界,再用实验判断这个下界是否值得算。
上一章的h估计“从这里到目标还要付出的代价”。本章沿用非负、目标处为0的约定;可容许表示它不会高于真正的最小剩余代价。
这里不要求你凭灵感猜h。先看8-数码:同一局面,错位块数给出6,曼哈顿距离给出14,真正最短解是20步。
🔢 一、8-数码的两个启发式,手算一遍
先认清一次合法动作
3×3方格里有8个数字块和一个空格。每次只能把空格与上、下、左、右相邻的一个数字交换,代价为1步;不能斜着换。
一个数错位,一个数还差几格
- h₁:错位块数。 只数没在目标位置的数字,不数空格。这里8个数字中2个在位,所以h₁=6。
- h₂:曼哈顿距离之和。 每个数字离自己的目标位置,还差几行、几列?把这两个距离相加,再对8个数字求和。
下表的“第几行、第几列”从1开始计数。只是在量距离,暂时不安排真正的移动顺序。
| 数字 | 当前位置(行,列) | 目标位置(行,列) | 纵向差 | 横向差 | 合计 |
|---|---|---|---|---|---|
| 7 | (1,1) | (3,1) | 2 | 0 | 2 |
| 2 | (1,2) | (1,2) | 0 | 0 | 0 |
| 4 | (1,3) | (2,1) | 1 | 2 | 3 |
| 5 | (2,1) | (2,2) | 0 | 1 | 1 |
| 6 | (2,3) | (2,3) | 0 | 0 | 0 |
| 8 | (3,1) | (3,2) | 0 | 1 | 1 |
| 3 | (3,2) | (1,3) | 2 | 1 | 3 |
| 1 | (3,3) | (1,1) | 2 | 2 | 4 |
所以h₂=2+0+3+1+0+1+3+4=14。6与14都是下界,不是承诺一定能在6步或14步完成。 后面的同一套搜索程序会验证最短解为20步。
🪢 二、松弛问题:这两个h从哪里来
让问题变简单,但不能把动作变贵
原题要求:移动的数字必须与目标格相邻,而且目标格必须为空。我们暂时放宽这些规则,同时保留“移动一个数字的费用是1”。
| 放宽什么 | 新问题允许什么 | 为什么能精确计算 |
|---|---|---|
| 相邻与空位限制都取消 | 一个数字可直接移到任意目标格,允许与其他数字暂时重叠 | 每个错位数字至少动1次,也确实只需1次,所以答案是h₁ |
| 只取消空位限制 | 数字仍一次走相邻一格,但允许穿过、占用有其他数字的格子 | 每个数字可独立走最短格路,所以答案是h₂ |
这里的“允许重叠”只是求下界的数学新规则,不是原棋盘真的可以这样操作。 不需要把数字互相让路、把空格挪回来,问题就便宜了。
原题的任意一条合法解,在这个更宽松的问题里仍然合法,费用也没有增加。因此,更宽松问题的最优费用,不会超过原题的最优费用。
这就是“可容许”的理由。只求出了松弛问题的某条可行路线,却没有证明它最优,不足以把那条路线的费用当成下界。Poole 与 Mackworth:由松弛问题构造启发式
已经学过一致性:为什么这种造法还常能保证一致?
需要固定同一个松弛问题,使原题每个动作都能映射为费用不更高的松弛动作。此时“先走这一步,再走松弛问题的最短路”也是候选路线,因此松弛最优值满足h(s)≤c(s,s′)+h(s′)。
不能在每个状态随意切换不同规则,然后只凭“各自都是下界”就断言一致。上一章的正确重开机制也不因此可以省略。
地图:公里与直线距离要用同一单位
撤掉“只能沿公路走”,允许从当前位置直接到目标。以公里为费用时,直线距离不超过任何连接两点的公路路线长度,所以得到上一章的hSLD。
如果优化的是时间,公里数就不能直接与已花秒数相加。必须另建时间下界,例如在明确的最高速度约束下用距离除以该速度。
旅行商:整程下界,不等于中途的剩余下界
旅行商问题要访问各城市并回到起点。先考虑边代价非负的无向图:从一条完整巡回中删去一条边,会留下连接所有城市的生成树;最小生成树(MST)不会比它更贵。
所以整图MST是完整巡回总代价的下界。这个放松不再要求每城进出恰好一次,也不再要求闭环;它仍要求把指定城市连接起来。
但搜索走到中途时,h必须估计剩余费用。比如三城A、B、C,两两距离都为1:已经走完A→B→C,只需花1回A;整图MST却为2,不能再把它当剩余下界。
一种简单的剩余下界,是对“当前城市、尚未访问的城市、起点”构成的集合计算MST;在通常的非负、无向、逐城巡回模型下,任一剩余路线也必须连接这些点。没有未访问城市时,它退化为当前城市回起点的边代价。不要不加说明地套到有向道路或其他旅行规则上。
魔方:先定义“距离”,再讨论除以8
这里采用一次面转计1步的口径:转一面90°、180°或270°都算一次。不同口径会改变最优步数与距离表。
Korf在1997年的论文中考虑的是:只管某一个小块,把它的位置和朝向恢复,最少需要多少次面转。忽略其他小块的归位要求,分别算角块和棱块,再求和。
一次面转同时影响4个角块和4个棱块。对任何被影响的小块,这一次操作最多使它的单块最短面转距离减少1;因此把所有小块的这种距离之和除以8,是整个魔方还需面转次数的下界。
论文也讨论把角块、棱块分开各除以4,再取较大者。除数来自“一次操作最多能减少多少这类距离”,不是看到8个小块就随手除8。Korf 1997 原论文
为什么不能直接用三维坐标的横差、纵差、高差?
从复原魔方转一面90°,只需反向转一次就能复原。但用小块中心的三维整数坐标算L1距离,这8个小块的距离总和是16;直接除8得到2,已经高于真正的1步。
所以旧称呼“三维曼哈顿距离”容易误导:这里必须按独立小块的最少面转数定义,且考虑朝向,不能直接照搬数码棋盘的坐标相减。
🏆 三、支配性:更强的下界,能帮多少忙
先比较下界,不先承诺速度
如果h₁和h₂都可容许,而且对所有相关状态都有h₂≥h₁,就说h₂支配h₁。它给出的下界至少一样紧,允许有些状态两者相等。
每个错位数字的曼哈顿距离至少为1,因此本章h₂始终不小于h₁。非负约定下,恒零h又被它们支配;A*使用h=0时,优先级f=g,退化为一致代价搜索。
较大的下界能排除更多“看起来仍可能很便宜”的路线。但不代表任意一次运行都严格展开更少,更不等于墙钟时间一定更短。
同一局面,用同一套规则比较
先把实验协议固定下来,避免把不同实现的数字拼在一起:
- 初态与目标就是本章两张棋盘;每次交换代价1。
- 空格后继固定按上、下、左、右生成,不合法方向略过。
- 使用最小堆;f相同时,本表先取较早入队者(FIFO)。
- 每个状态记录当前最小g,只把更小g的新路线入队,过期候选取出后跳过。
- 目标在取出时返回。展开数只统计真正生成后继的非目标候选,不含最后目标,也不含过期项。
| h | 本协议的非目标展开数 | 返回步数 |
|---|---|---|
| 恒零 | 55,408 | 20 |
| 错位块数h₁ | 3,666 | 20 |
| 曼哈顿距离h₂ | 282 | 20 |
这一次,最短解没有变,展开量明显减少。 55,408÷282约为196.5;这是展开数量之比,不是测得的时间加速比。
自己复跑:完整Python,同时比较三种并列规则
这段代码使用Python标准库,可整段独立运行。先关注misplaced、manhattan和entry:前两个算h,后一个明确相同f时谁先出队。
expanded在目标检查之后增加,故不包括目标;effective_b只把实际展开数加上目标,换算成本章下文约定的b*。
from heapq import heappop, heappush
from itertools import count
START = (7, 2, 4, 5, 0, 6, 8, 3, 1)
GOAL = (1, 2, 3, 4, 5, 6, 7, 8, 0)
TARGET = {tile: divmod(i, 3) for i, tile in enumerate(GOAL)}
def neighbors(state):
blank = state.index(0)
row, col = divmod(blank, 3)
for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
nr, nc = row + dr, col + dc
if 0 <= nr < 3 and 0 <= nc < 3:
other = nr * 3 + nc
nxt = list(state)
nxt[blank], nxt[other] = nxt[other], nxt[blank]
yield tuple(nxt)
def misplaced(state):
return sum(tile != 0 and tile != GOAL[i]
for i, tile in enumerate(state))
def manhattan(state):
return sum(abs(i // 3 - TARGET[tile][0])
+ abs(i % 3 - TARGET[tile][1])
for i, tile in enumerate(state) if tile != 0)
def astar(start, h, tie="fifo"):
serial = count()
best_g = {start: 0}
parent = {start: None}
def entry(state, g):
secondary = (state if tie == "lex" else
-g if tie == "larger_g" else 0)
return g + h(state), secondary, next(serial), g, state
frontier = [entry(start, 0)]
expanded = 0
while frontier:
_, _, _, g, state = heappop(frontier)
if g != best_g[state]:
continue
if state == GOAL:
path = []
while state is not None:
path.append(state)
state = parent[state]
return g, expanded, path[::-1]
expanded += 1
for nxt in neighbors(state):
new_g = g + 1
if new_g < best_g.get(nxt, float("inf")):
best_g[nxt] = new_g
parent[nxt] = state
heappush(frontier, entry(nxt, new_g))
return None, expanded, []
def effective_b(expanded, depth):
# 本页约定:expanded含起点、不含目标,所以总数再加1。
total = expanded + 1
low, high = 1.0, max(2.0, total)
for _ in range(80):
middle = (low + high) / 2
size = sum(middle ** i for i in range(depth + 1))
if size < total:
low = middle
else:
high = middle
return (low + high) / 2
print("手算核对:", misplaced(START), manhattan(START))
for tie in ("fifo", "lex", "larger_g"):
print("并列规则:", tie)
for name, h in (("h=0", lambda s: 0),
("h1", misplaced), ("h2", manhattan)):
cost, expanded, path = astar(START, h, tie)
assert cost == 20 and len(path) == 21
assert all(b in tuple(neighbors(a)) for a, b in zip(path, path[1:]))
print(name, "展开=", expanded, "步数=", cost,
"b*=", round(effective_b(expanded, cost), 3))
第三个参数只改并列规则:lex按整个棋盘元组的字典序;larger_g先取g更大者,再按入队顺序。没有改变h的定义,也没有改变每步费用。
| 相同f时的规则 | h=0展开数 | h₁展开数 | h₂展开数 |
|---|---|---|---|
| FIFO | 55,408 | 3,666 | 282 |
| 棋盘元组字典序 | 48,389 | 2,458 | 123 |
| 更大g优先,其余FIFO | 55,408 | 2,340 | 91 |
九次运行都返回20步。并列规则会改变展开计数,所以比较h时必须固定它。 本程序不是对任意h都自动证明最优:这里用的恒零、错位数、曼哈顿距离均满足所需条件。
旧版两组统计:保留记录,但不混称本次实测
旧版同一棋盘写的是48,389、3,666、282,解长均为20,还据此说展开相差约170倍。旧版没有保存足够的并列和重复处理协议。
现在可以分别复现其中的数值,但上表表明:换一套并列规则,其他列也会变化。没有足够证据把旧三数组合作为同一协议比较,也不能因此断言它们是伪造的。 读者复跑时以本页明确给出的程序为准。
历史讲义的典型成本:不是本页棋盘,也不是本轮重新测量
官方AIMA搜索讲义第33页将下面这些数字列为“典型搜索成本”。本次已对照该页核过深度标签与数值;这里保留它们,但不拿它们代替刚才的实验。
| 讲义标注的解深度 | IDS节点记录 | A*(h₁)节点记录 | A*(h₂)节点记录 |
|---|---|---|---|
| d=14 | 3,473,941 | 539 | 113 |
| d=24 | 约54×10⁹ | 39,135 | 1,641 |
来源:Russell与Norvig:AIMA搜索讲义,第33页。该页未交代完整测试集、是否取平均、并列和计数规则;本次也没有重新运行数百亿节点的IDS实验。因此不能把它们宣称为同一实例、同一设备或已完整复现的性能报告。
它们提示的是:较好的下界可能显著改变可处理的问题规模。但“540亿节点”不自动等于任何机器都跑不完;还要知道算法、每节点成本、资源和时限。无需背这些历史计数。
为什么不能保证“更强就一定展开更少”
设最优总代价为C*。在满足上一章条件、正确处理重复的A*分析中,要区分两类候选:
- f<C*: 对已经进入开放表、没有过期的候选,它会先于费用为C*的目标被取出。对同一个候选及其g,提高h可能把它移出这个严格低价范围。
- f=C*: 已与最优目标同价,哪一个先出队取决于并列规则。它们可能被展开,也可能等目标返回后不再处理。
这是对当前候选及其g的比较,不是说图上所有满足某个不等式的状态都一定已经生成。特别是h不一致时,祖先和后代的f可能下降,不能省略生成过程。
实际图搜索还要区分同名状态的不同g、是否重开及重复记录。因此支配是“下界信息至少一样强”,不是对所有实现、所有运行的总展开数和耗时作无条件保证。Poole 与 Mackworth:A*的代价边界
一个很小的反例:两个h都一致,更强者这次仍多展开1个
图中S的邻居先列B再列A,其余边如下。目标是G,最短路线S→A→G,费用2。
| 边 | 费用 |
|---|---|
| S→B | 1 |
| S→A | 1 |
| B→D | 1 |
| D→G | 10 |
| A→G | 1 |
| 状态 | 弱h | 强h |
|---|---|---|
| S | 0 | 0 |
| B | 1 | 1 |
| A | 0 | 1 |
| D | 0 | 0 |
| G | 0 | 0 |
只把A的h从0提高到1。两表都非负、目标为0,并在每条边上满足一致性;强表在每个状态上不小于弱表。
下面独立程序固定FIFO,直接打印非目标展开顺序:
from heapq import heappop, heappush
from itertools import count
GRAPH = {"S": [("B", 1), ("A", 1)], "B": [("D", 1)],
"A": [("G", 1)], "D": [("G", 10)], "G": []}
WEAK = {"S": 0, "B": 1, "A": 0, "D": 0, "G": 0}
STRONG = dict(WEAK, A=1)
def search(h):
serial = count()
frontier = [(h["S"], next(serial), "S", 0)]
best_g = {"S": 0}
log = []
while frontier:
_, _, state, g = heappop(frontier)
if g != best_g[state]:
continue
if state == "G":
return g, log
log.append(state)
for nxt, cost in GRAPH[state]:
new_g = g + cost
if new_g < best_g.get(nxt, float("inf")):
best_g[nxt] = new_g
heappush(frontier, (new_g + h[nxt], next(serial), nxt, new_g))
assert all(STRONG[s] >= WEAK[s] for s in GRAPH)
for name, h in (("弱h", WEAK), ("强h", STRONG)):
assert all(h[s] <= cost + h[nxt]
for s in GRAPH for nxt, cost in GRAPH[s])
cost, log = search(h)
print(name, "代价=", cost, "展开=", len(log), "顺序=", log)
弱h展开S、A、B,共3次;强h展开S、B、A、D,共4次。两者都返回费用2。多出的D恰好落在f=C*=2的并列边界,并没有违背“更强下界”的定义。
➕ 四、有好几个启发式的时候:取max
max:不用重复证明每条路线
若多个h都估计同一个目标、同一个费用单位,而且都可容许,可以取:
$$h(s)=\max\bigl(h_1(s),\ldots,h_m(s)\bigr).$$
每一项都不超过真正的最小剩余代价,最大那项也不会超过。它还逐点不小于任何一项,所以支配各组成项。
如果组成项还都一致,max也一致。代价是可能要多算几个h,或者存几张表;不能只凭“全都要”就断言更省时间。
直接相加可能重复计费,但不是永远禁止相加
先看坏例:距离目标只差把最后一行的7、空格、8改成7、8、空格,真实只需1步。此时错位数为1、曼哈顿距离也为1,直接相加得2,就高估了。
原因是两个h把同一个“移动8”动作各算了一次。
一个安全的加法例子:把曼哈顿距离拆成两组,A组只数1—4号数字,B组只数5—8号数字。一次原题动作只移动一个数字,费用只能被其中一组计入,不会双收。
本章初态A组为10,B组为4,相加为14,恰好是原来的h₂。这里“能相加”有不重复计费的理由,不是因为数字碰巧没超过20。
更一般地,可以把每个原动作的非负费用分摊给几个子问题,只要总分摊不超过原费用,各子问题的最优代价之和就仍是下界。模式数据库也能使用这种方法。Felner、Korf与Hanan:加性模式数据库
带走这一句:没有额外证明时,取max更稳妥;想相加,先证明同一动作没有被重复计费。
🗄️ 五、子问题与模式数据库
只关心部分数字,但空格仍按规则走
模式数据库(pattern database,PDB)就是一张提前算好的子问题最短费用表。搜索时把当前状态变成表的查询键,读出一个下界,不必临时重解子问题。
本页选一个具体约定:只区分1、2、3、4号数字和空格,5—8号合并为相同的“其他块”。其他块不必各归各位,但空格仍必须与相邻块交换,每次交换仍计1步。
先建表,再查表
- 定义目标模式。 1—4在各自目标位,空格在右下角;剩下格子由“其他块”占据。
- 倒着求最短路。 本例交换可逆且每步计1,从目标模式做BFS,记录每个可达模式的最少交换次数。
- 把当前棋盘映射成模式。 保留1—4和空格的位置,不再记录其他数字分别是什么。
- 查到一个下界。 原题任意完整解也会使这个模式到达目标,且每一步可对应成同费用的抽象动作,所以子问题最短费用不更大。
这是有限表:1、2、3、4、空格分别占不同格,最多有9×8×7×6×5=15,120种位置组合。表里存的是最短费用,不是随意找到的第一条非最短路线。
如果想把两张模式表相加,动作费用要怎么改?
刚才每次交换都计1的普通PDB,不能仅凭两组数字不重叠就相加:同一次交换可能已经在两张表里各收了1。
一种加性约定是:对某一组数字,只在交换移动了该组数字时计1;空格与其他块交换时计0。空格仍按相邻交换移动,只是某张表不为这一步收费。
两组划分1—8后,一次真实交换只会被一张表收费。于是可把两张精确的子问题最短费用相加。由于表中出现0费用边,不能再把普通按层BFS当成费用最短路;可使用0–1 BFS或正确的Dijkstra算法。
Korf的魔方实验:三张表与IDA*分工不同
Korf在1997年的最优魔方求解研究中,使用全部8个角块的一张模式表,以及两组各6个棱块的表,查询时取三者最大值。
这些表负责提供更紧的剩余步数下界;IDA*负责降低搜索记录的内存。IDA*的搜索栈较省内存,不代表模式表本身也变成线性大小。 论文将预计算表与低内存搜索组合,不能据此说PDB只能搭配IDA*。Korf的研究摘要
表通常可以在相同动作、费用和目标定义的多次查询中复用。若改变计步方式或目标定义,就要证明旧表仍适用,或重建;不是“算一次就无条件用一辈子”。
📉 六、有效分支因子:把本次搜索量换成一个数
b*是拟合值,不是每个棋盘都有这么多合法动作
本章定义:E是非目标展开次数,包括起点、不包括目标。令T=E+1,把最终目标也加上;解深度d以实际交换步数计。
找一个b*,使一棵“每层规模按b*增长”的理想树具有相同总量:
$$1+b^*+(b^*)^2+\cdots+(b^*)^d=T.$$
式子里的1是起点,最后一项对应深度d。它只是把这次计数换成便于比较的数字,不表示真的生成了这棵均匀树。
| 本章FIFO实验 | E | d | b*(约) |
|---|---|---|---|
| h=0 | 55,408 | 20 | 1.648 |
| h₁ | 3,666 | 20 | 1.418 |
| h₂ | 282 | 20 | 1.218 |
同样深度和口径下,b*更接近1表示展开更接近只沿一条解路径前进;b*=1时T=d+1。它不是说算法一定没有其他生成、排序或查表开销。
旧版“无信息约2.8”没有交代对应样本与统计定义,不作为本例结论;上面h=0的值也不能推广为所有8-数码问题的常数。比较不同报告时,先问N或E究竟数了生成、展开、目标中的哪些部分。
⚖️ 七、启发式不是免费的
少展开,并不自动少耗时
错位数要检查数字是否在位;曼哈顿距离还要计算行列差;PDB要把状态编码成查询键,并访问内存或存储中的表。
搜索还有生成后继、记录最小g、处理重复、操作优先队列等成本。h往往在生成或入队时求值,不是只对最终展开的节点算一次。
因此“总时间=展开数×算一次h的时间”不是精确公式。一个更实用的拆分是:
| 时间花在哪里 | 比较时要记录什么 |
|---|---|
| 预处理与加载 | 建表、加载是否计入;一次查询还是多次查询摊销 |
| h的计算 | 实际调用次数、编码与查表成本 |
| 搜索本身 | 后继生成、堆、去重、记录路线与重开 |
| 整体运行 | 相同环境下的端到端耗时和峰值内存 |
“节点少10倍、每个节点总成本慢20倍,可能反而慢2倍”可以作粗估,但必须假定其余成本与计数口径可比。不能把它当任意实现的严格等式。
原论文的取舍,不要扩成“实践从不用角块”
Korf论文先讨论过一种简单的单块距离启发式:加入角块那一项的计算收益不大,于是该基础方案主要使用棱块项。
这不是说角块信息没有价值。同一研究后来用到的更强PDB,恰好包含了全部8个角块的表。 距离公式与模式表是不同估计器,不能把某一次成本权衡推广到所有魔方算法。
用同样要求验收,再比较时间
- 解的要求不变。 是必须最优,还是允许近似?不能让更快的方案悄悄返回更差解。
- 内存和时间预算明确。 搜索栈省了,模式表仍可能放不下。
- 输入与协议相同。 包括并列、重复处理、启发式调用和预处理范围。
- 再看端到端时间。 记录多次运行或多实例的波动,展开数用来解释原因,而不是替代计时。
本页只给出可复跑的搜索计数,没有把它包装成任何电脑上的速度保证。
🔗 这一章连到哪里
| 去哪 | 为什么 |
|---|---|
| 强化学习基础 03 · 价值函数与贝尔曼方程 | h估计剩余代价,V常表示未来回报;对应时要统一正负号、目标、转移和折扣。h不只可手工设计,V也不只可从经验学习 |
| 推荐算法 10 · 向量检索与ANN | 可类比“提前计算换查询方便”,但近似向量检索索引不是PDB最短费用表,不能照搬可容许保证 |
| AI基础设施 index | 在解质量、内存与预处理约定一致后,看端到端时间;单独减少一个操作数量,不等于整个系统一定更快 |
✅ 检查点
- 本章初态的错位数、曼哈顿距离和最短解各是多少?为什么不把空格也算进两个h?
- 松弛问题为何能给下界?求一条松弛问题的任意可行路线就足够吗?
- 8-数码的相邻、空位限制分别怎样放宽?h₁与h₂各对应哪一种?
- 地图直线距离删掉了什么限制?旅行商走到中途时,为何不能直接拿整图MST当剩余h?
- 魔方距离“除8”到底除的是什么距离总和?一次面转怎样计步?为何不能照搬三维坐标L1?
- 什么叫支配?它对f<C*与f=C*意味着什么?h=0对应哪种搜索?
- 本章FIFO协议下三个展开数是什么、解长是否相同?为什么换并列规则后不能继续混用这组计数?
- 官方讲义d=24行的IDS与A*(h₂)量级是多少?它为什么不是本次实测,也不等于任意机器必然跑不完?
- 多个可容许h何时可以取max?直接相加为什么可能高估,什么条件下可以安全相加?
- 本页PDB保留什么状态、怎样移动空格?Korf的三张表各管什么,与IDA*怎样配合?
- 本章b*怎样用展开数与深度定义?为何不能把“无信息约2.8”当成本例固定答案?
- 比较更强h是否值得使用时,除了展开数,还必须检查哪些要求和成本?原论文不用某个简单角块距离项,是否等于从不使用角块信息?
对照答案:先核条件,再核数值
- h₁=6,h₂=14,最短20步。一次交换只移动一个数字;把空格也重复计距离可能重复收取同一步费用,不能直接套本章下界证明。
- 原题每个解仍是松弛问题的合法解,且映射后费用不增加,所以松弛最优费用不更高。任意一条松弛可行路线可能很贵;必须精确求最优,或另外证明所给估计本身是下界。
- 都取消时,每个错位数字可一次直接归位,得到h₁;只取消空位限制时,每个数字独立走最短相邻格路,得到h₂。允许重叠是新数学规则,不是原棋盘的操作许可。
- 地图取消只能沿公路走,费用仍以公里计。MST整图值估计整程;三城边全为1,已走A→B→C只余回A的1,而整图MST为2。剩余h要与当前剩余问题匹配。
- 求每个小块独立恢复位置和朝向的最少面转数,再相加除8;本口径90°、180°、270°各计1。一次面转最多使8个小块的该距离各减少1。裸坐标L1的一面90°反例为16÷8=2,高于真实1步。
- 两者都可容许且强h逐点不小于弱h。对同一候选及其g,提高h能使其不再严格低于C*;开放表中的有效低f候选先于最优目标取出。f=C*边界仍受并列影响,不能承诺每次总展开严格更少。h=0使A*按g排序,即UCS。
- FIFO下为55,408、3,666、282,均20步。邻居与并列顺序、重复和目标检测会改变计数;比较必须用同一协议。旧版48,389、3,666、282缺完整口径,不能不说明地与新实验拼接。
- 官方讲义记录IDS约54×10⁹、A*(h₂)为1,641,标签与数值已对照原页。本次没重跑该IDS,该页也没给出完整样本与算法协议。规模差异很大,但耗时还取决于机器、实现和预算,不等于无条件“跑不完”。
- 目标与单位相同且各项可容许,max仍可容许。一步之遥的错位数1加曼哈顿1会高估;如果对每个真实动作正确分摊费用、不重复计费,各子问题最优值可相加。
- 跟踪1—4与空格的位置,其他数字合并;空格仍相邻交换,每步计1,从目标模式反向BFS可建普通表。Korf用8角块和两组6棱块三表取max;IDA*减少搜索记录内存,不消除表内存,PDB也不限定只能搭配IDA*。
- E含起点但不含目标,令T=E+1,用1+b*+…+(b*)^d=T拟合。相同d与口径下,更接近1表示较少额外展开。本例h=0约1.648,2.8缺相应实例和口径,不能混用。
- 先固定最优性/解质量与内存预算,再记录预处理加载、h调用、搜索维护、端到端时间及波动。原论文对简单角块距离的取舍不是普遍禁令;后来的强PDB仍包含8角块表。
本节回顾
- 松弛问题的精确最优值是下界:原解仍合法,费用不增加。
- 更强h不等于每次严格更少或更快;并列与计数协议必须固定。
- 多个下界通常先取max;想相加,先证明没有重复计费。
- PDB把子问题预先算好;是否值得用,还要比较解质量、内存和端到端成本。
下一节 👉 09-运动规划.md