设想你是一名山地向导，要带着登山队从山脚营地登上山顶。山路四通八达，岔路口极多，每条路的长短不一。你手里有一张手绘地图——上面标注的并不是实际距离，而是“从每个路口到山顶还剩多远”的估算值。每到一个岔路口，你都要盘算两笔账：从营地走到这里已经花了多少力气（已行路程），以及地图上还写着多少个“弯”（剩余估算）。两笔账加在一起，就是你决定往哪儿走的“总信心值”。你会优先选择总信心值最小的方向——这，就是 A* 算法最朴素的生活原型。 可如果这张地图不靠谱呢？假设地图把一条实际还剩 10 公里的路标成“只剩 2 公里”，算法就会过于乐观地冲上去；反过来，把一条近路标成“还有 20 公里”，算法又会畏首畏尾，绕远路甚至找不到山顶。前者关乎“不能夸大困难”，后者关乎“相邻路口的估算要自洽”。前者叫可采纳性（Admissible），后者叫一致性（Consistent）。本文就用向导小明登山这张地图，把这两个条件、它们的验证方法以及常用设计技巧讲透，让你既能看懂 A* 的数学公式，也能在真实工程里选对、造对启发式函数。

岗位关联

对 AI 从业者来说，可采纳性与一致性直接决定搜索算法能否返回最优解、以及搜索耗时是否可接受，是路径规划、游戏 AI、机器人导航等系统的性能基石。

目录
  1. 可视化演示
  2. 算法基础——“总信心值”怎么算
  3. 可采纳性条件——地图不能夸大困难
  4. 一致性条件——相邻路口的估算要自洽
  5. 性质关系——一致是更强的承诺
  6. 验证方法——出发前逐段核对地图
  7. 常见启发式——好地图的几种款式
  8. 效率影响——好地图省腿力
  9. AI 应用场景
  10. Python 演示
  11. 常见误区
  12. 面试题

可视化演示

展示A*算法在网格地图上的启发式搜索过程：f(n)=g(n)+h(n)，蓝色为已展开节点，橙色为待探索节点，绿色为最终路径。

本节配有交互动效（进入视口后自动加载，约 3KB）。

A*启发式搜索过程 起点S：搜索起始节点 已展开：closed集中的节点 待探索：open集中的节点 f(n) = g(n) + h(n) 曼哈顿距离h(n)满足可采纳性，保证A*找到最短路径。

算法基础——“总信心值”怎么算

向导小明站在山脚的营地，面前是密密麻麻的岔路。他不慌不忙，掏出两样工具：一块记步手表——从营地走到现在这个路口，走了多少步，这是精确已知的；一张手绘地图——每个路口都标注着“到山顶的估算剩余距离”。他把“已走过的步数”和“估算剩余的距离”加起来，得到的就是这个岔路口的“总信心值”。小明总选择总信心值最小的路口先探路，这就是 A* 搜索的本质动作。

在计算机里，这个“总信心值”被写成评价函数 f(n)。其中 g(n) 是从起点到节点 n 的真实代价，搜索过程中可以通过累加精确获得；h(n) 则是从 n 到目标代价的启发式估计，来自问题的领域知识。A* 维护一个按 f 值排序的开放列表（open list），每次取出 f 最小的节点扩展，直到目标节点被弹出。

你看，g 像手表那样可靠，h 则像地图那样充满“估算”的味道。A* 的全部智慧，就藏在这个 h 应该如何设计、如何约束之中。地图画得好不好，直接决定了小明能不能少走冤枉路、最终能否准时登顶。

f(n)=g(n)+h(n)\displaystyle f(n) = g(n) + h(n)
  1. f(n) 总估价f 表示从起点出发、途经当前节点、最终到达目标点的全程估计代价，是 A* 决策的唯一依据。
    f(n)=g(n)+h(n)\displaystyle f(n) = g(n) + h(n)
  2. g(n) 已行代价g 记录起点到当前节点已经花费的实际代价，从父节点继承后再加上一步的边代价即可精确得到。
    g(n)=g(parent)+c(parent,n)\displaystyle g(n) = g(\text{parent}) + c(\text{parent}, n)
  3. h(n) 剩余估算h 是对当前节点到目标剩余代价的启发式预测，由领域知识构造，是整个评分中唯一“不确定”的部分。
    h(n)=cost^(n,goal)\displaystyle h(n) = \widehat{\text{cost}}(n, \text{goal})

可采纳性条件——地图不能夸大困难

假如小明手里的地图是“悲观主义者”画的：明明从这条路到山顶只剩 2 公里，地图却标注“还有 15 公里”。于是这个路口的 f 值被虚抬得很高，A* 每次优先排序时都会冷落它，转而去探索那些“看似更近”的绕远路。结果队伍辛辛苦苦绕了一大圈，才恍然发现原来那条近路才是最优的——可惜已经在错误方向上浪费了大量体力。这正是启发式函数“夸大困难”带来的恶果。

要避免这种误导，启发式函数必须满足可采纳性条件：对任意节点 n，h(n) 都不能超过从 n 到目标的真实最小代价 h*(n)。换句话说，估计只允许乐观偏低，不允许悲观偏高。只要满足这个条件，A* 在第一次从开放列表中弹出目标节点时，得到的路径一定是最优的。

所以，一张好地图的品格是“谦逊”：可以低估前方的路（多走几步冤枉路），但绝不高估困难（否则会错过最优路线）。不过请你记住，可采纳性只保证了“最终找到最优解”，它并没有承诺搜索过程一定高效——这就是我们接下来要讲一致性条件的原因。

h(n)≤h∗(n)\displaystyle h(n) \le h^{*}(n)
  1. h*(n) 真实剩余h*(n) 表示从节点 n 到目标节点的真实最小代价，是所有可行路径代价的下确界，也是理论上不可欺骗的基准。
    h∗(n)=min⁡p∈paths(n, goal)cost(p)\displaystyle h^{*}(n) = \min_{p \in \text{paths}(n,\, \text{goal})} \text{cost}(p)
  2. h(n) 估计值启发式函数 h 输出的是对真实剩余代价的估算，它允许保守（低于真实），但不允许自大（高于真实）。
    h(n)=estimate(n→goal)\displaystyle h(n) = \text{estimate}(n \to \text{goal})
  3. 可采纳不等式将估计值与真实值比较，要求估计不大于真实，这就是“地图不夸大困难”的数学表达。
    h(n)≤h∗(n)\displaystyle h(n) \le h^{*}(n)

一致性条件——相邻路口的估算要自洽

想象小明走到一个路口，看地图说“到山顶还剩 5 公里”。他沿着山路走了 500 米，停下来再次看地图，却赫然写着“还剩 100 米”。队伍沸腾了，以为马上到顶，结果翻过垭口才发现下面是万丈悬崖，还要绕 4.5 公里。这个场景意味着什么？两个相邻路口之间的估算落差（5 公里减 100 米，约 4.9 公里）远远超过了实际走过的路程（500 米）。这种“估算突然跳水”的地图，会让 A* 算法产生一个严重后果：f 值沿路径不升反降，算法需要反复回到已探索过的节点，重新计算、重复展开，效率暴跌。

正式地，一致性条件要求对图中任意相邻节点 n 和 n'，启发式函数的取值满足：h(n) 不超过“从 n 到 n' 的实际代价 c(n, n') 再加上 h(n')”。这个式子形似几何中的三角不等式，它把两个相邻节点的估计用真实边权捏合在一起，防止估算在一步之间过度跳变。

有了这把“自洽”的尺子，A* 沿任意路径推进时，f 值都只会单调不减。这就好比小明每走一段路，心中的“总信心值”只增不减，整个探索过程一路向前，不需要频繁回头。你会发现，一致性这个条件比可采纳性更“苛刻”，但正是这份苛刻，换来了搜索效率的大幅提升。

h(n)≤c(n,n′)+h(n′)\displaystyle h(n) \le c(n, n') + h(n')
  1. c(n,n') 边代价c(n,n') 表示从节点 n 走到相邻节点 n' 需要付出的真实代价，在图中它是已知的边权。
    c(n,n′)=cost of edge(n,n′)\displaystyle c(n, n') = \text{cost of edge}(n, n')
  2. h(n') 后继估计h(n') 是到达相邻节点 n' 之后，对新位置剩余路程的启发式估算。
    h(n′)=estimate(n′→goal)\displaystyle h(n') = \text{estimate}(n' \to \text{goal})
  3. 一致不等式将“当前估计”与“实际边价加后继估计”比较，防止 h 值沿边下降过快，这就是三角不等式约束。
    h(n)≤c(n,n′)+h(n′)\displaystyle h(n) \le c(n, n') + h(n')

性质关系——一致是更强的承诺

小明的队里有两位向导徒弟。徒弟甲的地图不夸大困难（可采纳），但相邻路口之间的估算经常“跳崖”（不一致）；徒弟乙的地图既不大话连篇，又逐段自洽（一致）。你更愿意相信谁？显然是乙。其实从数学上看，乙的承诺确实更强：只要启发式满足一致性，并且目标节点的估计值归零，就必然同时满足可采纳性。换句话说，“一致”是“可采纳”的一个充分条件。

证明的思路非常直观：从任意节点 n 出发，沿着它到目标的最优路径 n → n₁ → n₂ → … → G 一步一步套用一致性不等式，把 h(n) 像击鼓传花一样逐级传递下去，最后一头撞上真实总代价 h*(n)。于是 h(n) 被压在了真实代价之下，可采纳性得证。反过来，“可采纳”却推不出“一致”，前者只是单点约束，后者是逐边约束。

这张“传递链”说明，一致性是比可采纳性更严格的资质认证。在实际工程中，如果你能构造出一致的启发式，就等于同时拿到了“最优性”与“不重开节点”的双重保险；而如果只能保证可采纳，则还要在搜索中处理节点重复展开的问题。

h(n)≤c(n,n1)+h(n1)≤c(n,n1)+c(n1,n2)+h(n2)≤⋯≤h∗(n)\displaystyle h(n) \le c(n,n_1) + h(n_1) \le c(n,n_1) + c(n_1,n_2) + h(n_2) \le \cdots \le h^{*}(n)
  1. 取最优路径设 n 到目标 G 的最优路径为 n→n₁→n₂→…→G，其真实总代价恰为 h*(n)。
    h∗(n)=c(n,n1)+c(n1,n2)+⋯+c(nk,G)\displaystyle h^{*}(n) = c(n,n_1) + c(n_1,n_2) + \cdots + c(n_k, G)
  2. 沿路径套用一致性对路径上每条相邻边，都套用一致性不等式，得到当前估计的上界递推式。
    h(n)≤c(n,n1)+h(n1)\displaystyle h(n) \le c(n,n_1) + h(n_1)
  3. 逐级放大至目标把上一级的结果代入下一级，反复展开直到目标，最终整串代价相加恰好不超过真实最优代价。
    h(n)≤∑i=1k+1c(ni−1,ni)=h∗(n)\displaystyle h(n) \le \sum_{i=1}^{k+1} c(n_{i-1}, n_i) = h^{*}(n)

验证方法——出发前逐段核对地图

小明出发前有个好习惯：把地图铺在桌上，沿着每一条山路逐段核对。他手里拿着一把直尺和一块秒表，对每一对相邻路口 n 和 n'，都做一次心算：地图上 n 处的剩余路程，减去 n' 处的剩余路程，这个落差绝不允许超过两路口之间实际要走的路程。只要所有相邻对都过了关，这张地图就是一致的。

把一致性不等式移项，就能得到这个更便于工程检查的形式：h(n) - h(n') ≤ c(n, n')。于是验证流程变得非常机械：遍历图中所有有向边，逐条检查落差。除此之外还有两个边界项必须确认：第一，目标节点自身的 h 值必须为 0，否则它的估计会被“高估”；第二，若图中存在孤立节点或不可达区域，要单独核对。这两步合起来，就是完整的“一致性体检”。

这段“核对地图”的功夫，在工程上就是一行行自动化测试。造好一个启发式函数后，先用程序遍历所有相邻对，跑一遍上面的不等式，几毫秒就能判断它是否一致。这比等到搜索中途才发现反复展开节点，要划算得多。

h(n)−h(n′)≤c(n,n′)∀(n,n′)∈E\displaystyle h(n) - h(n') \le c(n, n') \qquad \forall (n,n') \in E
  1. 移项整理将一致性不等式两边同时减去 h(n')，得到“估算落差 ≤ 实际代价”的直观形式，便于逐边验证。
    h(n)−h(n′)≤c(n,n′)\displaystyle h(n) - h(n') \le c(n, n')
  2. 逐边检查遍历图中每一条有向边，验证相邻节点的估算落差是否越界，这是验证算法最核心的循环。
    ∀(n,n′)∈E:  h(n)−h(n′)≤c(n,n′)\displaystyle \forall (n, n') \in E:\; h(n) - h(n') \le c(n, n')
  3. 终点回零目标节点到自身的真实剩余代价为 0，因此要求它的启发式估计也必须为 0，否则一致性自动失效。
    h(goal)=0\displaystyle h(\text{goal}) = 0

常见启发式——好地图的几种款式

不同地形需要不同款式的地图。在只能横平竖直行走的城市街区里，小明用“曼哈顿距离”——就像出租车从 A 点开到 B 点，只能沿街道转向，把东西向差距和南北向差距相加。在可以翻山越岭任意直行的开阔原野上，他改用“欧氏距离”，拿尺子直接量两点间直线长度。前者是最经典的可采纳且一致启发式，在网格路径规划中几乎是无脑首选；后者在连续空间中同样满足两个条件。

还有一种更精巧的设计思路叫“松弛化”：把原问题的某些约束放宽，再用放宽后的最优解作为启发式。例如八数码游戏中，忽略“空格一次只能移动一张牌”的约束，只计算每个棋子到目标位置的曼哈顿距离之和，得到的值一定不会超过真实步数，因此天然可采纳；又因为每走一步最多让总和减少 1，它也满足一致性。

选对地图的“款式”，等于给搜索装上了涡轮增压。一张贴合问题结构、满足两种性质的地图，能让 A* 像老马识途一样直奔目标；而一张随随便便的地图，则会让算法像无头苍蝇一样到处乱撞。

hManhattan(n)=∣xn−xg∣+∣yn−yg∣\displaystyle h_{\text{Manhattan}}(n) = |x_n - x_g| + |y_n - y_g|
  1. x 轴差距当前节点与目标节点在 x 方向上的坐标差，取绝对值得到横向距离。
    Δx=∣xn−xg∣\displaystyle \Delta x = |x_n - x_g|
  2. y 轴差距y 方向上的坐标差，同样取绝对值得到纵向距离。
    Δy=∣yn−yg∣\displaystyle \Delta y = |y_n - y_g|
  3. 求和得曼哈顿距离将横向与纵向相加，即四方向网格中至少需要移动的步数，是既乐观又自洽的估计。
    hManhattan(n)=Δx+Δy\displaystyle h_{\text{Manhattan}}(n) = \Delta x + \Delta y

效率影响——好地图省腿力

同样是带队登顶，徒弟乙拿着好地图，每到一个路口只需探一次就再不回头；徒弟甲的地图虽然不夸大困难，却因为相邻估算落差失控，队伍几次三番折返，同一个岔路口走了三四遍。在 A* 里，“折返”对应着节点的重复扩展：一个已经进入关闭列表（closed list）的节点，竟因为新的 g 值更优而被迫重新打开，既浪费时间又污染路径图。而一致性条件从根上杜绝了这种局面。

原因在于，一致性保证 f 值沿任意路径单调不减。当某个节点第一次被扩展时，它的 f 值不会比将来任何绕路到达它的方式更大，因此第一次到达它时的 g 值就是全局最优——关闭列表里的节点从此不再需要被唤醒。随着启发式估计越接近真实代价，扩展的节点数越少；而 h=0 的极端情况虽然也满足两个条件，却退化成盲目搜索，展开的节点数最多，好比手里没有地图、只能一寸寸摸索。

可见，一张既一致又贴合真实代价的地图，是搜索效率的双引擎。可采纳性守护最优性，一致性守护流畅性，两者齐备，A* 才能在有穷时间内给出一条漂亮的黄金路线。下山后，小明把这两条铁律刻进了登山手册的第一页，也刻进了每一位算法工程师的脑海。

f(n′)=g(n)+c(n,n′)+h(n′)≥g(n)+h(n)=f(n)\displaystyle f(n') = g(n) + c(n, n') + h(n') \ge g(n) + h(n) = f(n)
  1. 后一节点评分扩展 n 到相邻节点 n' 后，n' 的 f 值由“起点到 n 的 g 值、n 到 n' 的边代价、n' 的估计值”三部分构成。
    f(n′)=g(n)+c(n,n′)+h(n′)\displaystyle f(n') = g(n) + c(n, n') + h(n')
  2. 代入一致性条件由 h(n) ≤ c(n,n') + h(n') 可知，边代价与后继估计之和不小于当前节点的估计值。
    c(n,n′)+h(n′)≥h(n)\displaystyle c(n, n') + h(n') \ge h(n)
  3. 得单调不降结论因而 f(n') 不小于 f(n)，沿扩展路径 f 值只升不降，印证了“已扩展节点无需重开”。
    f(n′)≥g(n)+h(n)=f(n)\displaystyle f(n') \ge g(n) + h(n) = f(n)

AI 应用场景

游戏 NPC 寻路

阶段：搜索与决策

解决的问题：在庞大开放世界地图中，NPC 需要实时绕开障碍找到玩家。若启发式不一致，NPC 会在墙角反复横跳、走向抖动，玩家看到的就是“鬼畜”；若不可采纳，NPC 可能抄一条观感很差的绕路。一致且可采纳的启发式（如曼哈顿距离）让 NPC 的路径即时、平滑且最优。

具体案例：某开放世界手游中，上千个 NPC 同时寻路。采用曼哈顿距离作为启发式，提前用遍历验证一致性后，单帧寻路耗时从 8ms 降到 1.2ms，且彻底消除了“NPC 在门口反复掉头”的 bug。

仓库机器人导航

阶段：路径规划与调度

解决的问题：Kiva 式仓库里上百台机器人共享网格地面，每条任务都要在几百毫秒内算出最优路线。传统做法用 Dijkstra（等价于 h=0）虽然保证最优，但展开节点过多；采用一致性启发式后，机器人不仅走最优路径，还因为免重开机制而响应极快，能应对高频调度。

具体案例：某电商仓库中，AGV 在 300×200 的栅格地图上执行拣货任务。将曼哈顿距离与障碍物松弛化设计结合，通过一致性校验后，平均规划耗时从 45ms 降至 6ms，多机冲突率下降 70%。

拼图类 AI 解题器

阶段：状态空间搜索

解决的问题：八数码、15 数码等滑动拼图的求解器，本质是在状态图上做 A* 搜索。启发式设计的好坏直接决定“秒解”还是“穷举到死”。以曼哈顿距离之和作为启发式，配合一致性验证，求解器在保证最优解的同时，展开节点数比错误启发式少两个数量级。

具体案例：某在线 AI 课堂设计八数码求解器时，对比了三种启发式：h=0、错位棋子数、曼哈顿距离之和。一致性验证通过后，曼哈顿方案平均只展开 180 个节点，而 h=0 方案展开超过 3 万个节点。

Python 演示

python80 行
import heapqimport math  def verify_consistent(grid, goal, h_func):    """依次检查每对相邻节点是否满足 h(n) <= c(n,n') + h(n')."""    rows, cols = len(grid), len(grid[0])    h = {(r, c): h_func((r, c), goal) for r in range(rows) for c in range(cols)}    for (r, c), hv in h.items():        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):            nr, nc = r + dr, c + dc            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 0:                if hv > h[(nr, nc)] + 1:                    return False, (r, c, nr, nc)    return True, None  def manhattan(node, goal):    return abs(node[0] - goal[0]) + abs(node[1] - goal[1])  def euclidean(node, goal):    return math.hypot(node[0] - goal[0], node[1] - goal[1])  def twice_manhattan(node, goal):    return 2 * manhattan(node, goal)  def astar(grid, start, goal, h_func):    rows, cols = len(grid), len(grid[0])    heap = [(h_func(start, goal), 0, start)]    g_best = {start: 0}    parent = {}    expanded = 0    while heap:        f, g, node = heapq.heappop(heap)        if node == goal:            path = []            while node in parent:                path.append(node)                node = parent[node]            path.append(start)            return list(reversed(path)), expanded, g_best[goal]        if g > g_best.get(node, float('inf')):            continue        expanded += 1        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):            nr, nc = node[0] + dr, node[1] + dc            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 0:                nxt = (nr, nc)                ng = g + 1                if ng < g_best.get(nxt, float('inf')):                    g_best[nxt] = ng                    parent[nxt] = node                    heapq.heappush(heap, (ng + h_func(nxt, goal), ng, nxt))    return None, expanded, None  def main():    grid = [        [0, 0, 0, 0, 0],        [0, 1, 1, 1, 0],        [0, 0, 0, 0, 0],        [0, 0, 1, 0, 0],        [0, 0, 0, 0, 0],    ]    start, goal = (0, 0), (4, 4)    for name, h_func in (("manhattan", manhattan),                         ("euclidean", euclidean),                         ("2x_manhattan", twice_manhattan)):        ok, pos = verify_consistent(grid, goal, h_func)        path, expanded, cost = astar(grid, start, goal, h_func)        print(name, "consistent:", ok, "expanded:", expanded, "cost:", cost)        if pos:            print("  violated at", pos)  if __name__ == "__main__":    main()
目的：在 5×5 网格地图上，验证三种启发式函数的一致性，并对比它们驱动 A* 搜索时扩展的节点数量。
  1. h = {(r, c): h_func((r, c), goal) for r in range(rows) for c in range(cols)}预先为网格中每个格子算好启发式值，避免验证时重复计算。
  2. if hv > h[(nr, nc)] + 1:核心一致性检查：当前格估计值超过“相邻格估计值 + 边代价 1”即违规。
  3. heap = [(h_func(start, goal), 0, start)]初始将起点以 (f, g, 节点) 三元组压入优先队列，f 越小越先扩展。
  4. if g > g_best.get(node, float('inf')): continue若该节点已有更优路径，则跳过本次出队，等价于处理节点重开。
  5. heapq.heappush(heap, (ng + h_func(nxt, goal), ng, nxt))用新的 g 值加上启发式估计构成 f 值压堆，驱动搜索方向。

常见误区

误区我以为只要启发式函数不高估真实代价（可采纳），那就万事大吉了，搜索效率也自然最优。

正解可采纳性只保证 A* 能找到最优解，并不保证节点只被扩展一次。一个可采纳但“相邻估算落差过大”的启发式，会让 f 值沿路径下降，导致节点反复进出关闭列表，效率大幅受损。一致性是比可采纳性更强的逐边约束，两者是“及格”与“优秀”的关系。

为何常见：教科书常先证明可采纳性实现最优，读者容易误以为满足它就够了，忽视了搜索过程中的重复展开。

误区我觉得 h 值算得越“激进”、数值越大，越能体现领域知识，搜索应该越快。

正解h 值一旦超过真实代价就违反可采纳性，A* 不再保证最优；即便控制在可采纳范围内，如果它破坏了“相邻落差不超过边代价”的一致性，同样会因为节点重开而变慢。正确的策略是在可采纳且一致的前提下，尽量让 h 贴近真实代价。

为何常见：直觉上“更精确”与“数值更大”常被混为一谈，实际上精确度取决于与真实代价的贴合度，而非绝对大小。

误区h=0 肯定可采纳也一致，用它最保险，最多慢一点。

正解h=0 确实满足两个性质，但它等于放弃所有领域信息，A* 退化为 Dijkstra，节点展开数可达曼哈顿启发式的数百倍。在实时系统中，这种“保险”可能导致无法接受的延迟。一致性只是“不重复扩展”，真正决定扩展范围的是 h 与真实代价的贴近程度。

为何常见：学习者看到 h=0 满足所有数学条件，就误以为它是“零风险方案”，忽略了效率这个工程维度。

误区所有网格地图都能用曼哈顿距离当启发式，结果一定最优。

正解曼哈顿距离成立的前提是“仅允许上下左右四方向移动、且每步代价为 1”。如果地图允许对角线移动，真实最短路径可能短于曼哈顿距离，此时它反而高估真实代价，破坏可采纳性。选启发式前必须先确认移动代价模型。常用验证脚本对所有相邻节点对做一致性检查，能快速暴露这类设计失误。

为何常见：许多入门教程以四方向网格为默认场景，读者未注意假设条件，照搬到对角移动或带权图时出错。

面试题

Q1. 在 A* 的评价函数 f(n) = g(n) + h(n) 中，哪一项表示“从当前节点到目标的启发式估计”？

单选题 · easy

  • A.f(n)
  • B.g(n)
  • C.h(n)← 正确答案
  • D.c(n, n')

答案：C。g(n) 是从起点到当前节点的实际代价，h(n) 才是对剩余代价的启发式估计，两者相加得到 f(n)。c(n,n') 是相邻节点的边代价，与题意不符。可类比向导的“已走步数”与“地图剩余估算”两个角色。

Q2. 可采纳性条件的数学表述是？

单选题 · easy

  • A.h(n) ≥ h*(n)
  • B.h(n) ≤ h*(n)← 正确答案
  • C.g(n) ≤ g*(n)
  • D.f(n) ≤ f*(n)

答案：B。可采纳性要求启发式估计 h(n) 不超过真实最小代价 h*(n)，即“地图不夸大困难”。若 h(n) ≥ h*(n) 表示过度悲观，A* 可能放弃最优路径。g 是已知代价，f 是综合评分，均不是约束对象。

Q3. 一致性条件的数学形式是？

单选题 · mid

  • A.h(n) ≥ c(n, n') + h(n')
  • B.h(n) ≤ c(n, n') + h(n')← 正确答案
  • C.h(n) ≤ h(n') - c(n, n')
  • D.g(n) ≤ g(n') + c(n, n')

答案：B。一致性要求当前节点估计不超过“边代价加后继节点估计”，即三角不等式。它保证相邻路口的估算不会突然跳水，从而让 f 值沿路径单调不减。B 选项正是这个关系；A 方向相反，C、D 公式不成立。

Q4. 若启发式函数满足一致性，A* 搜索可以获得哪项关键性质？

单选题 · mid

  • A.已扩展节点无需重新打开← 正确答案
  • B.开放列表永远为空
  • C.启发式值必须为零
  • D.不必维护关闭列表

答案：A。一致性保证 f 值单调不减，因此节点第一次被扩展时 g 值已是最优，关闭列表中的节点不必重开。A 正确；开放列表仍可能非空，启发式不必为零，关闭列表在一致性下仍然用于防止重复扩展，故 B、C、D 均错。

Q5. 关于 h(n)=0 的说法，正确的是？

单选题 · mid

  • A.不可采纳，A* 找不到解
  • B.可采纳但违反一致性
  • C.可采纳且一致，但搜索效率很低← 正确答案
  • D.一定会导致死循环

答案：C。h=0 时估计不高于真实代价，故可采纳；任意相邻节点间 0 ≤ c(n,n')+0 恒成立，故也一致。但它不携带任何启发信息，A* 退化为 Dijkstra，展开节点数极多，故选 C。

Q6. 若启发式满足可采纳性但不满足一致性，可能出现哪些现象？

多选题 · mid

  • A.A* 必然找不到最优解
  • B.某些节点可能被多次扩展← 正确答案
  • C.f 值可能沿路径下降← 正确答案
  • D.搜索必然提前终止

答案：BC。可采纳性保证了最优解，故 A 错；不一致意味着相邻估算落差过大，f 值可能沿某条路径下降，使已扩展节点被更优 g 值“唤醒”而重开，B、C 正确。搜索终止条件与一致性无关，D 错。可类比向导地图“相邻路口跳崖”导致队伍折返。

Q7. 在仅允许四方向移动、每步代价为 1 的网格地图上，哪些启发式函数可采纳且一致？

多选题 · hard

  • A.曼哈顿距离← 正确答案
  • B.欧氏距离← 正确答案
  • C.两倍曼哈顿距离
  • D.切比雪夫距离（max(|Δx|,|Δy|)）← 正确答案

答案：ABD。真实最短路径代价恰为曼哈顿距离，A 中 h 等于下界故可采纳且一致；欧氏距离不大于曼哈顿距离且相邻变化不超过 1，故 B 正确；切比雪夫距离是曼哈顿距离的下界且每步变化不超过 1，故 D 正确；C 中两倍曼哈顿距离超过真实代价，违反可采纳性。

Q8. 在允许对角线移动且对角步代价为 1 的网格中，曼哈顿距离可能发生什么？

单选题 · mid

  • A.仍然可采纳且一致
  • B.高估真实代价，破坏可采纳性← 正确答案
  • C.仍然一致但不可采纳
  • D.退化为欧氏距离

答案：B。对角线移动使真实最短路径短于曼哈顿距离，此时曼哈顿值高于真实代价，违反可采纳性。选启发式前必须先明确移动代价模型，不能在四方向假设外盲目套用。

Q9. 工程上验证一个启发式是否一致，最直接的做法是？

单选题 · hard

  • A.只检查目标节点的 h 是否为 0
  • B.遍历所有相邻节点对，检查 h(n)-h(n') ≤ c(n,n')，并确认 h(goal)=0← 正确答案
  • C.把启发式值取平方后再比较
  • D.运行一次 A* 看路径是否平滑

答案：B。一致性是逐边约束，必须遍历所有有向边核对估算落差，同时校验目标点 h 归零，B 描述的正是标准流程。A 只是边界条件之一；C 是数值变换，无意义；D 属于事后观察，既不可靠也无法定位违规边。

Q10. 若 h₁ 与 h₂ 都满足可采纳性，那么 h(n)=max(h₁(n), h₂(n)) 一定怎样？

单选题 · hard

  • A.一定可采纳且一致
  • B.一定可采纳，但不一定一致← 正确答案
  • C.一定一致但不可采纳
  • D.一定不可采纳

答案：B。由于 h₁、h₂ 都不超过真实代价，二者取 max 仍不超过真实代价，故可采纳性保持。但取 max 可能让相邻节点的估算落差变大，破坏“落差 ≤ 边代价”的一致条件，因此不一定一致。可类比两张地图各取较保守标注，整体未必逐段自洽。