🏠 总目录📚 本教程 08 · 启发式怎么设计 ← →

怎样造出既便宜又有用的启发式下界?

读后可检查:从松弛问题解释估计来源,再比较支配性、取 max 与计算成本。

📑 本页目录(点开跳转)

08 · 启发式怎么设计

⏱ 29 分钟 | 阅读参考,不是完成时限;先会算一个例子,再按需要看证明和实验。


🎯 一句话

先解一个规则更宽松的问题,得到“至少还要花多少”的下界,再用实验判断这个下界是否值得算。

上一章的h估计“从这里到目标还要付出的代价”。本章沿用非负、目标处为0的约定;可容许表示它不会高于真正的最小剩余代价。

这里不要求你凭灵感猜h。先看8-数码:同一局面,错位块数给出6,曼哈顿距离给出14,真正最短解是20步。


🔢 一、8-数码的两个启发式,手算一遍

先认清一次合法动作

3×3方格里有8个数字块和一个空格。每次只能把空格与上、下、左、右相邻的一个数字交换,代价为1步;不能斜着换。

8-数码:本章起始棋盘与目标棋盘 初态逐行为7、2、4;5、空格、6;8、3、1。目标逐行为1、2、3;4、5、6;7、8、空格。2和6已经在目标位置。 起始状态 目标状态 724 56 831 123 456 78 空格空格 → 绿色位置:2和6已经放对;空格不计入两个h。
先看绿色的2和6:它们在位,其余6个数字错位。箭头只表示本题要达到的目标,不代表一步就能到达。

一个数错位,一个数还差几格

  • 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. 初态与目标就是本章两张棋盘;每次交换代价1。
  2. 空格后继固定按上、下、左、右生成,不合法方向略过。
  3. 使用最小堆;f相同时,本表先取较早入队者(FIFO)。
  4. 每个状态记录当前最小g,只把更小g的新路线入队,过期候选取出后跳过。
  5. 目标在取出时返回。展开数只统计真正生成后继的非目标候选,不含最后目标,也不含过期项。
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与空格的模式 左侧初态为7、2、4;5、空格、6;8、3、1。右侧保留2、4、空格、3、1原位置,将7、5、6、8换成其他。空格仍在中间,不能任意瞬移。 具体棋盘 查询用的模式 724 56 831 2431 空格空格 其他其他其他其他 → 只省略其他数字的身份,没有取消空格的移动规则。
看右侧仍在中心的空格:抽象只忘掉5—8号的区别,不允许空格随便移动。这就是一份明确的查询状态。

先建表,再查表

  1. 定义目标模式。 1—4在各自目标位,空格在右下角;剩下格子由“其他块”占据。
  2. 倒着求最短路。 本例交换可逆且每步计1,从目标模式做BFS,记录每个可达模式的最少交换次数。
  3. 把当前棋盘映射成模式。 保留1—4和空格的位置,不再记录其他数字分别是什么。
  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个角块的表。 距离公式与模式表是不同估计器,不能把某一次成本权衡推广到所有魔方算法。

用同样要求验收,再比较时间

  1. 解的要求不变。 是必须最优,还是允许近似?不能让更快的方案悄悄返回更差解。
  2. 内存和时间预算明确。 搜索栈省了,模式表仍可能放不下。
  3. 输入与协议相同。 包括并列、重复处理、启发式调用和预处理范围。
  4. 再看端到端时间。 记录多次运行或多实例的波动,展开数用来解释原因,而不是替代计时。

本页只给出可复跑的搜索计数,没有把它包装成任何电脑上的速度保证。


🔗 这一章连到哪里

去哪 为什么
强化学习基础 03 · 价值函数与贝尔曼方程 h估计剩余代价,V常表示未来回报;对应时要统一正负号、目标、转移和折扣。h不只可手工设计,V也不只可从经验学习
推荐算法 10 · 向量检索与ANN 可类比“提前计算换查询方便”,但近似向量检索索引不是PDB最短费用表,不能照搬可容许保证
AI基础设施 index 在解质量、内存与预处理约定一致后,看端到端时间;单独减少一个操作数量,不等于整个系统一定更快

✅ 检查点

  1. 本章初态的错位数、曼哈顿距离和最短解各是多少?为什么不把空格也算进两个h?
  2. 松弛问题为何能给下界?求一条松弛问题的任意可行路线就足够吗?
  3. 8-数码的相邻、空位限制分别怎样放宽?h₁与h₂各对应哪一种?
  4. 地图直线距离删掉了什么限制?旅行商走到中途时,为何不能直接拿整图MST当剩余h?
  5. 魔方距离“除8”到底除的是什么距离总和?一次面转怎样计步?为何不能照搬三维坐标L1?
  6. 什么叫支配?它对f<C*与f=C*意味着什么?h=0对应哪种搜索?
  7. 本章FIFO协议下三个展开数是什么、解长是否相同?为什么换并列规则后不能继续混用这组计数?
  8. 官方讲义d=24行的IDS与A*(h₂)量级是多少?它为什么不是本次实测,也不等于任意机器必然跑不完?
  9. 多个可容许h何时可以取max?直接相加为什么可能高估,什么条件下可以安全相加?
  10. 本页PDB保留什么状态、怎样移动空格?Korf的三张表各管什么,与IDA*怎样配合?
  11. 本章b*怎样用展开数与深度定义?为何不能把“无信息约2.8”当成本例固定答案?
  12. 比较更强h是否值得使用时,除了展开数,还必须检查哪些要求和成本?原论文不用某个简单角块距离项,是否等于从不使用角块信息?
对照答案:先核条件,再核数值
  1. h₁=6,h₂=14,最短20步。一次交换只移动一个数字;把空格也重复计距离可能重复收取同一步费用,不能直接套本章下界证明。
  2. 原题每个解仍是松弛问题的合法解,且映射后费用不增加,所以松弛最优费用不更高。任意一条松弛可行路线可能很贵;必须精确求最优,或另外证明所给估计本身是下界。
  3. 都取消时,每个错位数字可一次直接归位,得到h₁;只取消空位限制时,每个数字独立走最短相邻格路,得到h₂。允许重叠是新数学规则,不是原棋盘的操作许可。
  4. 地图取消只能沿公路走,费用仍以公里计。MST整图值估计整程;三城边全为1,已走A→B→C只余回A的1,而整图MST为2。剩余h要与当前剩余问题匹配。
  5. 求每个小块独立恢复位置和朝向的最少面转数,再相加除8;本口径90°、180°、270°各计1。一次面转最多使8个小块的该距离各减少1。裸坐标L1的一面90°反例为16÷8=2,高于真实1步。
  6. 两者都可容许且强h逐点不小于弱h。对同一候选及其g,提高h能使其不再严格低于C*;开放表中的有效低f候选先于最优目标取出。f=C*边界仍受并列影响,不能承诺每次总展开严格更少。h=0使A*按g排序,即UCS。
  7. FIFO下为55,408、3,666、282,均20步。邻居与并列顺序、重复和目标检测会改变计数;比较必须用同一协议。旧版48,389、3,666、282缺完整口径,不能不说明地与新实验拼接。
  8. 官方讲义记录IDS约54×10⁹、A*(h₂)为1,641,标签与数值已对照原页。本次没重跑该IDS,该页也没给出完整样本与算法协议。规模差异很大,但耗时还取决于机器、实现和预算,不等于无条件“跑不完”。
  9. 目标与单位相同且各项可容许,max仍可容许。一步之遥的错位数1加曼哈顿1会高估;如果对每个真实动作正确分摊费用、不重复计费,各子问题最优值可相加。
  10. 跟踪1—4与空格的位置,其他数字合并;空格仍相邻交换,每步计1,从目标模式反向BFS可建普通表。Korf用8角块和两组6棱块三表取max;IDA*减少搜索记录内存,不消除表内存,PDB也不限定只能搭配IDA*。
  11. E含起点但不含目标,令T=E+1,用1+b*+…+(b*)^d=T拟合。相同d与口径下,更接近1表示较少额外展开。本例h=0约1.648,2.8缺相应实例和口径,不能混用。
  12. 先固定最优性/解质量与内存预算,再记录预处理加载、h调用、搜索维护、端到端时间及波动。原论文对简单角块距离的取舍不是普遍禁令;后来的强PDB仍包含8角块表。

本节回顾

  • 松弛问题的精确最优值是下界:原解仍合法,费用不增加。
  • 更强h不等于每次严格更少或更快;并列与计数协议必须固定。
  • 多个下界通常先取max;想相加,先证明没有重复计费。
  • PDB把子问题预先算好;是否值得用,还要比较解质量、内存和端到端成本。

下一节 👉 09-运动规划.md

打卡记录保存在你的浏览器里,首页能看到总进度