跳转到内容
← 返回算法
图算法计算机科学 · 人工智能 · 搜索约 28 分钟阅读

A* 搜索算法

A* Search Algorithm

1968 年，Stanford Research Institute 的三位研究员——Peter Hart、Nils Nilsson 和 Bertram Raphael——在开发一台机器人（Shakey）的导航系统时，需要一种高效的路径规划算法。 他们提出的算法发表在论文"A Formal Basis for the …

A*启发式搜索路径规划人工智能

1968 年，Stanford Research Institute 的三位研究员——Peter Hart、Nils Nilsson 和 Bertram Raphael——在开发一台机器人（Shakey）的导航系统时，需要一种高效的路径规划算法。

他们提出的算法发表在论文"A Formal Basis for the Heuristic Determination of Minimum Cost Paths"中，被命名为 A（读作"A-star"）。五十多年后，A 仍然是路径规划领域最重要的算法之一，是游戏引擎、地图应用、机器人导航的标准工具。

Dijkstra 的局限

理解 A 需要先理解它在解决什么问题。Dijkstra 算法在已知图上找最短路径，是精确且通用的，但它有一个根本问题：它不知道目标在哪里*。它从源点出发，以"涟漪"形式向四面八方展开，直到遇到目标——这意味着在目标方向上的搜索效率与在错误方向上相同，浪费了大量计算。

在大型地图上，Dijkstra 可能需要探索数百万个节点；而如果我们能告诉算法"目标大概在东北方向"，就可以优先往那个方向搜索，大幅提升效率。这就是启发式搜索（Heuristic Search）的思想，A* 是其最成功的实现。

核心思想：$f = g + h$

A 对每个节点 $n$ 维护一个估计函数*：

f(n)=g(n)+h(n)f(n) = g(n) + h(n)

  • $g(n)$：从起点到节点 $n$ 的已知实际代价（与 Dijkstra 一样）
  • $h(n)$：从节点 $n$ 到目标的启发式估计代价（对未来的猜测）
  • $f(n)$：经过节点 $n$ 的路径的估计总代价

算法每次从优先队列中取出 $f$ 值最小的节点，与 Dijkstra 每次取 $g$ 值最小相比，A* 用启发函数 $h$ 引导搜索朝向目标。

A* 算法框架：
open_set = {start}  （带优先级，按 f 值）
g[start] = 0
f[start] = h(start)

while open_set 非空： current = open_set 中 f 值最小的节点 if current == goal: 返回路径 for 每个邻居 neighbor: tentative_g = g[current] + cost(current, neighbor) if tentative_g < g[neighbor]: g[neighbor] = tentative_g f[neighbor] = g[neighbor] + h(neighbor) 将 neighbor 加入 open_set ```

启发函数的关键：可接受性

A 正确性（保证找到最短路径）的关键条件：启发函数 $h$ 必须是可接受的（admissible）*，即：

h(n)≤h∗(n)h(n) \leq h^*(n)

其中 h∗(n)h^*(n) 是从节点 $n$ 到目标的真实最短代价。换言之，$h$ 不能高估实际代价。

为什么？直觉：若 $h$ 高估，则某些"绕路"的节点因为 $h$ 值被高估而被算法跳过，可能错失真正的最短路径。若 $h$ 从不高估，被跳过的路径一定不是最优的。

更强的条件是一致性（Consistency / Monotonicity）：

h(n)≤cost(n,n′)+h(n′)h(n) \leq cost(n, n') + h(n')

对所有 $n$ 的邻居 $n'$ 成立（类似三角不等式）。一致的启发函数一定可接受，且使得 A* 无需重新处理节点，效率更高——这句话的分量比它看起来重得多，下文有专门一节。

常用启发函数

网格地图（Grid Map）：

  • 曼哈顿距离（Manhattan Distance，仅允许上下左右移动）：h=∣x1−x2∣+∣y1−y2∣h = |x_1 - x_2| + |y_1 - y_2|
  • 欧几里得距离（允许任意方向移动）：h=(x1−x2)2+(y1−y2)2h = \sqrt{(x_1-x_2)^2 + (y_1-y_2)^2}
  • 切比雪夫距离（允许对角移动）：h=max⁡(∣x1−x2∣,∣y1−y2∣)h = \max(|x_1-x_2|, |y_1-y_2|)

地图路由（道路网络）：直线距离除以最大速度，是行驶时间的下界。

八数码（8-puzzle）：每个数字到目标位置的曼哈顿距离之和——这是可接受的，因为每个数字至少需要这么多步移动，各数字不妨碍彼此。

手算一遍：A* 与 Dijkstra 在同一张网格上

拿一张 4 列 × 3 行的网格，四连通、每步代价 1，# 是墙：

text
        x=0   x=1   x=2   x=3
 y=0     S     .     #     .
 y=1     .     .     #     G
 y=2     .     .     .     .
```

起点 $S=(0,0)$，目标 $G=(3,1)$，启发函数用曼哈顿距离 $h(x,y) = |3-x| + |1-y|$。

$h(S) = 3 + 1 = 4$，但真正的最短路是 6 步——$x=2$ 那一列在 $y=0,1$ 被堵住，必须绕到 $(2,2)$。$h$ 在起点低估了 2，低估的正是墙迫使你多走的绕路。这是所有网格 A* 的常态：启发函数看不见障碍物。

逐步展开（同 $f$ 时取 $h$ 更小者，再同则按入队顺序）：

步取出的节点$g$$h$$f$新生成 / 更新的节点（$g,h,f$）
1(0,0)044(1,0) 1,3,4；(0,1) 1,3,4
2(1,0)134(1,1) 2,2,4（右侧 (2,0) 是墙）
3(1,1)224(1,2) 3,3,6（(2,1) 是墙；(0,1) 经此更差，不更新）
4(0,1)134(0,2) 2,4,6
5(1,2)336(2,2) 4,2,6
6(2,2)426(3,2) 5,1,6
7(3,2)516(3,1) 6,0,6
8(3,1) = G606命中，返回 6 步

这张表最该注意的是第 3 步到第 5 步之间那个跳变：$f$ 从 4 变成 6。前四步 A 一直相信"4 步就能到"，直到把 $y=0,1$ 两行的出路都试完，才被迫接受 $f=6$。$f$ 值的单调上升就是启发函数被现实修正的过程*，而它上升的总量（4 → 6）恰好等于障碍物造成的绕路代价。

A 一共扩展了 8 个节点*：$(0,2)$ 一直躺在 open 里没被取出，$(3,0)$ 连生成都没有。

同一张图上跑 Dijkstra（等价于 h≡0h \equiv 0），按 $g$ 递增出队：$(0,0)$@0 → $(1,0)$@1、$(0,1)$@1 → $(1,1)$@2、$(0,2)$@2 → $(1,2)$@3 → $(2,2)$@4 → $(3,2)$@5 → $(3,1)$@6。9 个节点，比 A* 多了一个 $(0,2)$。

10 个可走格子里省下 1 个，实在不值一提。关键是这个差距怎么随规模长。换成一张 8 列 × 5 行、完全没有墙的空地，$S=(0,2)$、$G=(7,2)$：

对任何被最优地到达的格子，$g = x + |y-2|$、$h = (7-x) + |y-2|$，于是

f(x,y)=7+2 ∣y−2∣f(x,y) = 7 + 2\,|y - 2|

$f$ 只取决于它离那条直线走廊有多远：$y=2$ 一整行 $f=7$，$y=1,3$ 是 9，$y=0,4$ 是 11。A 会把所有 $f=7$ 的节点先掏空——也就是沿着 $y=2$ 一路平推——扩展 8 个节点就撞上目标，一格都不偏*。

Dijkstra 则要先取完所有 d≤6d \le 6 的格子：$y=2$ 行 7 个，$y=1,3$ 各 6 个，$y=0,4$ 各 5 个，共 29 个；再在 5 个 $d=7$ 的格子里碰到目标。总计 30 到 34 次扩展（取决于同 $g$ 值的出队顺序），是 A* 的 4 倍左右。

而且这个倍数会继续涨：空地上 A 扩展的节点数随地图边长线性增长（就那一条走廊），Dijkstra 是平方增长（整个菱形）。A 省下的不是一个常数因子，是一个维度。**

一致性为什么比可接受性更强

教科书通常把一致性写成"更强的条件，效率更高"就带过了。它真正的分量在于：只有可接受、不一致的启发函数，会让 A* 给出错误答案——只要你的实现里有一个 closed 集合而且不允许重开节点，而这几乎是所有工程实现的做法。

看这张 4 节点图（边上的数字是代价）：

边代价
S→AS \to A3
S→BS \to B1
B→AB \to A1
A→GA \to G2

真实最短路是 S→B→A→G=1+1+2=4S \to B \to A \to G = 1+1+2 = 4。真实剩余代价 h∗h^*：h∗(A)=2h^*(A)=2，h∗(B)=3h^*(B)=3，h∗(S)=4h^*(S)=4。

取启发函数 $h(S)=0$、$h(A)=0$、$h(B)=3$、$h(G)=0$。它完全可接受（0≤40\le4、0≤20\le2、3≤33\le3）。但它在边 B→AB\to A 上违反一致性：

h(B)=3  >  cost(B,A)+h(A)=1+0=1h(B) = 3 \;>\; cost(B,A) + h(A) = 1 + 0 = 1

带 closed 集、不重开节点的 A* 这样跑：

步取出$g$$f = g+h$发生了什么
1S00生成 A（$g=3$，$f=3$）、B（$g=1$，$f=1+3=4$）
2A33A 被以 $g=3$ 关闭（真实最优是 2）；生成 G（$g=5$，$f=5$）
3B14发现经 B 到 A 只要 $g=2 < 3$——但 A 已在 closed 里，丢弃
4G55返回 5

答案 5，最优 4。启发函数一点没高估，A* 却错了。错因是 $h(B)$ 太大，把真正的好路（经 B）压在了 open 队列后面，等它浮上来时 A 已经被"定稿"了。

允许重开节点（把 A 从 closed 挪回 open，$g=2$、$f=2$）就能修正到 4。所以一致性的真实含义是：

$h$ 一致   ⟺  \iff $f$ 沿任何路径单调不减   ⟺  \iff 一个节点被取出时它的 $g$ 已经是最优的   ⟺  \iff 永远不需要重开节点。

链条里最后一环才是工程上关心的：一致启发下每个节点至多扩展一次，A 的复杂度就和 Dijkstra 同阶。而 Alberto Martelli 在 1977 年证明，放弃一致性假设后，A 在最坏情况下需要 O(2N)O(2^N) 步*（Artificial Intelligence* 8, 1–13）——不是慢一点，是指数爆炸。

好消息是常见启发函数几乎都是一致的。均匀代价四连通网格上的曼哈顿距离一定一致：走一步只改变一个坐标 1，所以 ∣h(n)−h(n′)∣≤1=cost(n,n′)|h(n) - h(n')| \le 1 = cost(n,n')，三角不等式自动成立。这就是为什么游戏引擎可以放心地用最朴素的"进了 closed 就不再看"实现。真正容易踩坑的是把多个启发取最大值、或者从学习模型／查表里得到 $h$ 的场合——那时 $h$ 可接受不代表它一致，closed 集就成了一个正确性漏洞。

不可接受启发的代价：把启发函数放大 1.5 倍

Weighted A\（f=g+w⋅hf = g + w\cdot h，$w>1$）是最常用的加速手段，它把可接受的 $h$ 故意放大成不可接受的，换取更少的扩展。代价有一个明确的上界：返回路径的代价不超过 $w \cdot C^$（C∗C^* 为最优代价）。

先说一个诚实的实验结果：在上面那张 4×3 网格上取 $w=1.5$，A\* 仍然走出了最优的 6 步，扩展次数也还是 8。$w$-最优性只承诺"不超过 1.5×6=91.5\times 6 = 9 步"，这次它没有用上这份宽容。想看它真的失手，需要一个 $h$ 在不同区域松紧不一的例子——地图上的死胡同正是这种地形。

边代价节点真实剩余 h∗h^*给出的 $h$
S→AS \to A2A88（很紧）
A→GA \to G8B121（极松）
S→BS \to B1S103
B→GB \to G12

几何上的读法：B 是一条隔着河的死胡同——直线距离上它离终点很近（$h=1$），实际要绕 12 的路才能过去。A 方向看着远（$h=8$），但那 8 是真的。$h$ 完全可接受（8≤88\le8、1≤121\le12、3≤103\le10）。

$w=1$（标准 A*）：

步取出$g$$f = g+h$结果
1S03生成 A（$g=2$，$f=10$）、B（$g=1$，$f=2$）
2B12生成 G（$g=13$，$f=13$）——先被死胡同骗了
3A210$10 < 13$，把 G 的 $g$ 修正到 10
4G1010返回 10 ✅ 最优

标准 A 也走错了第一步，但它自己爬了回来：随着 $g$ 累积，死胡同那条路的 $f$ 涨到 13，A 方向的 10 反超。可接受性保证的正是这个"总能爬回来"。*

$w=1.5$（$f' = g + 1.5h$）：

步取出$g$$f' = g+1.5h$结果
1S04.5生成 A（$g=2$，$f'=2+12=14$）、B（$g=1$，$f'=1+1.5=2.5$）
2B12.5生成 G（$g=13$，$f'=13$）
3G1313$13 < 14$，先弹出目标，返回 13 ❌

返回 13，最优是 10，多走了 30%（仍在 1.5×10=151.5\times10=15 的承诺内）。差别只有一处：放大 $h$ 之后，A 方向那个诚实的 $h=8$ 被抬成 12，$f'(A)$ 从 10 涨到 14，反超了死胡同路线的 13。

该记住的机制：$w$ 放大的是"猜测"相对于"已付出代价"的话语权。$g$ 是事实，$h$ 是估计；$w>1$ 等于宣布"我更信估计"。所以 Weighted A 出错的地方永远是估计最不可靠的地方——障碍物背后、死胡同深处、任何 $h$ 严重低估真实距离的区域。这也解释了实践中的用法：$w$ 通常只取 1.1 到 1.5，而且往往配上 ARA（见下文）那样"先出一个 $w$ 大的粗解，再逐步减小 $w$ 精修"的框架。

效率：$h$ 越紧越好

  • $h = 0$：A* 退化为 Dijkstra——均匀展开，无方向性，最慢但保证最优
  • h=h∗h = h^*（完美启发）：A* 直接找到最短路，不走弯路，最快
  • h>h∗h > h^*（不可接受）：速度快但可能错过最优路径（变为近似算法）

这揭示了一个根本权衡：启发函数越精确，搜索越高效；但精确启发往往难以计算。实践中追求"足够紧"的可接受启发。

这里有一个流传极广、但严格来说是错的说法需要点出来："启发函数更准，A\* 扩展的节点一定更少"并不成立。Robert Holte 在 2010 年专门写了一篇文章罗列这类误解（Common Misconceptions Concerning Heuristic Search，SoCS 2010），这一条排在第一位，并给出了反例。

真正成立的是一个更弱的版本。任何可接受的 A 都必须扩展所有满足 $f(n) < C^$ 的节点（C∗C^* 是最优代价）——否则无法确信没有更好的解。若处处 h2≥h1h_2 \ge h_1，则 f2≥f1f_2 \ge f_1，于是

{n:f2(n)<C∗}⊆{n:f1(n)<C∗}\{n : f_2(n) < C^*\} \subseteq \{n : f_1(n) < C^*\}

"被迫扩展"的那部分确实随启发变紧而缩小。漏洞在边界上：f(n)=C∗f(n) = C^* 的节点扩不扩展取决于平局怎么打破，而更紧的启发会把更多节点从"f<C∗f < C^*"推到"f=C∗f = C^*"上——那批节点的命运就交给了实现细节，完全可能反而被多扩展一批。

所以把若干可接受启发取 max⁡\max 通常是划算的，但它不是数学上的"稳赚"，而是一个经验判断，而且还要留意上一节的坑：取 max 可能破坏一致性。

A* 的复杂度与局限

理论复杂度（最坏情况）：O(bd)O(b^d)，$b$ 是分支因子，$d$ 是解的深度。在无启发的情况下，A* 与 BFS 一样是指数级的。但好的启发函数可以将有效分支因子降到接近 1，使时间近乎线性。

内存是 A* 的主要瓶颈：在最坏情况下，open set 可能存储指数多的节点。这一点比时间更致命——时间不够可以等，内存不够会直接崩。改进方案都是围绕这一点：

  • IDA（Iterative-Deepening A，Korf 1985）：用迭代加深代替优先队列，内存 $O(d)$，在许多场景（如数字拼图）更实用
  • SMA（Simplified Memory-Bounded A）：内存满时删除最不有希望的节点
  • 双向 A*：从起点和终点同时搜索，在某些图上大幅提速

现实应用

视频游戏：几乎所有 RTS（即时战略）游戏的单位寻路都用 A 或其变种。Warcraft、StarCraft、Age of Empires 等经典游戏的地面单位导航背后都有 A。

地图导航：Google Maps、高德地图的路线规划结合了 A* 与更复杂的层次化路由算法（如 Contraction Hierarchies，用于超大规模道路网络）。

机器人学：机器人路径规划在连续空间中用 RRT（Rapidly-exploring Random Trees）和 PRM（Probabilistic Roadmap），但离散化后的 A* 仍是基础工具。

解谜与 AI：在 15 数码、魔方等状态空间搜索问题中，IDA 是标准解法。需要区分的是：对抗性博弈（如 Deep Blue 国际象棋 AI）用的是 minimax + alpha-beta 剪枝，而非 A——A* 解决的是单智能体的代价最小化路径问题，博弈树搜索面对的是对手的对抗，两者属于不同的搜索范式。

现场：游戏与地图导航真正在用的东西

"游戏用 A 寻路"这句话对，但工业实现几乎从不是教科书里那个 A。三种工程手段构成了真实系统的骨架。

一、消除对称路径：跳点搜索（JPS）。在均匀代价网格上，从 $(0,0)$ 走到 $(3,3)$ 有大量长度相同、只是拐弯位置不同的路径。教科书 A 会把这些对称路径全部展开一遍——纯粹的浪费。Daniel Harabor 与 Alban Grastien 在 2011 年（AAAI，论文题为 Online Graph Pruning for Pathfinding on Grid Maps）给出了跳点搜索（Jump Point Search）：用两条邻居剪枝规则递归地跳过所有"不可能改变最优性"的中间格子，只把真正需要决策的跳点放进 open 队列。报告的加速是一个数量级以上，而且不需要任何预处理、不增加内存开销*——这在游戏里近乎免费。

二、抽象层次：分层寻路（HPA*）。一张 1024×1024 的地图有一百万个格子，单位又成百上千。Adi Botea、Martin Müller 与 Jonathan Schaeffer 在 2004 年提出 HPA\（Journal of Game Development 1(1)）：把地图切成固定大小的簇（cluster），只在簇的边界上取若干入口节点，预计算簇内任意两个入口之间的距离，构成一张小得多的抽象图。查询时先在抽象图上找路，再只对起点和终点所在的簇做细化。相对高度优化的 A，他们报告最多 10 倍加速，路径长度在最优值的 1% 以内——用 1% 的路径质量换 10 倍速度，这个交易在游戏里从来不用犹豫。

三、预处理换查询：收缩层次（CH）。道路网络规模更大（欧洲路网上千万节点），但它有一个宝贵性质：图是静态的。Robert Geisberger、Peter Sanders、Dominik Schultes 与 Daniel Delling 在 2008 年（WEA）提出收缩层次（Contraction Hierarchies）：按某种顺序逐个"收缩"节点，收缩时若两个邻居之间的最短路必须经过它，就加一条捷径边（shortcut）替代。查询时做双向搜索，且只许沿层次向上走。预处理换来的查询加速是几个数量级——这正是地图应用能在你打完字之前算出跨国路线的原因。这也是上文那个判断的又一次出现：静态图 + 高频查询 = 预处理一定划算。

四、路径平滑（Path Smoothing）。格点路径是锯齿状的，直接交给角色会走出机械的直角转弯。工程做法是后处理：从路径起点向后依次做视线检测（line-of-sight），能直连就删掉中间点，剩下的用样条曲线插值。另一条路是在搜索阶段就允许任意角度——Theta* 一类的 any-angle 算法在展开节点时尝试把父节点直接连到当前节点，生成的路径天生更自然。

四种手段的共同点值得点出来：它们全都不改进 A 本身，而是改变 A 面对的图。剪枝改变了邻居关系，分层与收缩改变了节点集合，平滑改变了对解的要求。这是路径规划工程里最一般的经验——当算法已经接近最优时，接下来能动的是问题的表述。

A* 的变种与继承者

Weighted A（权重化 A）：用 f=g+w⋅hf = g + w \cdot h（$w > 1$）加速搜索，以找到次优但更快的解（满足 $w$-最优）。

Theta*（Theta-star）：在网格上，允许从任意已访问节点到当前节点的直线路径，生成更自然的（非格点受限的）路径。

D（Dynamic A）和 D* Lite（Koenig & Likhachev 2002）：动态环境下的 A* 变种，当地图部分变化时增量更新路径，广泛用于机器人实时导航。

ARA（Anytime Repairing A）：先用较大的 $w$ 快速找一个粗糙解，然后利用剩余时间逐步减小 $w$ 并复用上一轮的搜索结果，适合实时系统——它把上文那个"$w$ 越大越可能次优"的权衡变成了一个可以随时中断的连续过程。

跨域连接

  • 最优化：可接受启发本质上是原问题的一个松弛解——放宽约束后求得的最优值一定不超过原问题的最优值，因此可以当下界用。这与分支限界里的界是同一件事，八数码的曼哈顿距离就是"允许棋子互相穿过"这个松弛的精确解。想造新的启发函数，正确的问法是"删掉哪条约束之后问题变得可解"。
  • Dijkstra 最短路径：启发取零时两者相同，因此全部收益都来自启发的紧度。一致性比可接受性重要得多：只有一致的启发才保证节点出队时距离已最优，才允许"进了关闭集就不再看"这种实现。把多个启发取最大值可能破坏一致性，此时不允许重开节点就成了正确性漏洞，而不是效率问题。
  • 遥感与地理信息系统：路网上常用直线距离除以最高限速当下界，它的紧度取决于绕行系数——实际路程与直线距离之比。这给出可预测的性能差异：平原棋盘路网的绕行系数接近一，启发很紧；峡湾、山谷与跨河城市可以到两倍以上，同一份代码在那里退化到接近无方向搜索。地形而非代码决定扩展节点数。
  • 实时系统：实时系统的正确性包含截止期，"最优但可能超时"不可接受。随时可中断的搜索把最优性变成一个连续量：先用放大的启发快速出一个粗解，再用剩余时间逐步收紧并复用上一轮结果，任何时刻被打断都有可行解。代价是解的质量只有相对最优值的倍数保证，没有绝对保证。
  • 计算语言学：序列解码同样是在状态空间里找最优路径，却几乎不用启发式最优搜索——因为语言模型的分数没有可用的下界，构造不出可接受启发。于是只能退到束搜索：固定宽度地保留若干候选，放弃最优性保证。这也解释了束宽增大反而变差的现象：搜得更彻底只是更忠实地找到了模型的偏好，而模型本身有偏。

参考文献

  • Hart, P., Nilsson, N. & Raphael, B. "A Formal Basis for the Heuristic Determination of Minimum Cost Paths." IEEE Transactions on Systems Science and Cybernetics 4(2), 1968.
  • Martelli, A. "On the Complexity of Admissible Search Algorithms." Artificial Intelligence 8(1), 1–13, 1977.（不一致启发下 A* 的 O(2N)O(2^N) 最坏界）
  • Korf, R. "Depth-First Iterative-Deepening." Artificial Intelligence 27(1), 1985.
  • Koenig, S. & Likhachev, M. "D Lite." AAAI*, 2002.
  • Botea, A., Müller, M. & Schaeffer, J. "Near Optimal Hierarchical Path-Finding." Journal of Game Development 1(1), 2004.（HPA*：最多 10 倍加速，路径在最优值 1% 以内）
  • Geisberger, R., Sanders, P., Schultes, D. & Delling, D. "Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks." WEA 2008, LNCS 5038.
  • Harabor, D. & Grastien, A. "Online Graph Pruning for Pathfinding on Grid Maps." AAAI 2011.（跳点搜索 JPS）
  • Holte, R.C. "Common Misconceptions Concerning Heuristic Search." Proceedings of the International Symposium on Combinatorial Search (SoCS), 46–51, 2010.（"更准的启发一定扩展更少节点"等五条常见误解的反例）

延伸阅读

  • Russell, S. & Norvig, P. Artificial Intelligence: A Modern Approach. 4th ed. Pearson, 2020.（第 3–4 章）
  • Pearl, J. Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley, 1984.（启发式搜索的经典专著，一致性与可接受性的系统处理）
  • Amit Patel, Introduction to A\*（Red Blob Games 在线教程，交互式演示扩展节点与启发函数的关系）

正文中引用本条 · 1 · 其中 1 条来自其他领域

数学图论应用