BFS / 宽度优先
按层扩展，找到最少步数的路径。每步代价相同时，最少步数才等于最低代价。
01 / INTERACTIVE LAB
每一步搜索，都看得见。
在同一张地图上，观察不同算法如何探索、绕行与抵达终点。
指导书原图
正在载入地图…
试一试
选择算法后点击“运行并播放”。
起点 S终点 G最终路径先扩展后扩展
起点 S终点 G进入代价：0.512 / 35 / 810
各图按相同扩展步数回放，短序列会先结束。热力图颜色表示各自扩展顺序；重开可能重复扩展同一格。动画速度不代表计算耗时。
本次浏览器结果
| 算法 | 状态 | 步数 | 真实代价 | 扩展数 | 最大 OPEN | 重开 | 预处理 ms | 搜索 ms | 合计 ms |
|---|
计时来自当前设备的一次运行，不含动画与绘图；不与下方 Python 统计直接比较。最大 OPEN 是节点数，不是内存占用。
02 / THE QUESTION
先找到路，还是找到最好的路？
四邻域移动 · 图搜索 · 正进入代价
任务是在障碍地图中从 S 走到 G。算法的差别，在于下一步优先扩展谁；评价则同时关注解的质量与搜索开销。
DFS / 深度优先
沿一个方向深入，遇到尽头再回退。路径和工作量对邻居顺序敏感，不保证最优。
UCS / 等代价
优先走到累计代价更低的位置。正代价下给出最低代价路径，是本实验的比较基准。
Greedy / 贪心
只看离目标的估计距离，可能很快抵达，也可能绕远或付出更高代价。
A* / 代价与方向
同时考虑已付出的代价和剩余估计。使用可采纳启发式并正确处理重复路径，可保证最优。
加权 A* / 质量与速度
w > 1 更偏向目标，不保证最优；在基础启发式可采纳等条件下，完成的解满足 C ≤ wC*。
地形中的正确估计
h(n) = cmin × (|Δr| + |Δc|)进入哪个格点，就付那个格点的代价；起点不收费。存在 0.5 代价时，直接用未缩放曼哈顿距离可能高估。03 / EXPERIMENTAL EVIDENCE
从一张迷宫，到成批验证。
3,900单位代价地图 · 3127 张可解
78,000原始批量搜索
540新增地形与大图
14,580新增重复计时搜索
A / 指导书原图
相同的路径，不等于相同的搜索。
原图为 41 × 81 的树结构：1599 个可通行节点、1598 条边、0 个独立环。起终点间只有一条简单路径，五种基础算法都得到 339 步。
这里能比较的是探索开销；不能凭一次同路结果，就断言 DFS 或贪心总能最优。
| 算法 | 步数 / 代价 | 扩展数 | 最大 OPEN |
|---|---|---|---|
| BFS | 339 | 688 | 7 |
| DFS | 339 | 724 | 14 |
| UCS | 339 | 688 | 7 |
| Greedy | 339 | 658 | 8 |
| A* | 339 | 682 | 7 |
B / 3900 张单位代价地图
有多条路时，路径质量才拉开差距。
完美迷宫、带环迷宫、随机障碍和大规模地图组成固定种子地图库。保留无解样本；最优率以可解地图为分母。
| 算法 | 最优率（可解图） | 扩展 / UCS 中位数 | 最大代价 / 最优代价 |
|---|---|---|---|
| BFS | 100.0% | 1.000 | 1.000 |
| DFS | 34.6% | 0.442 | 6.684 |
| UCS | 100.0% | 1.000 | 1.000 |
| Greedy | 43.0% | 0.289 | 2.906 |
| A* | 100.0% | 0.713 | 1.000 |
标准 A* 的扩展 / UCS 中位数为 0.713，即减少约 28.7%。
这是逐图配对后的扩展比值中位数。更少的扩展不必然更快：队列、堆与启发式计算的每节点开销不同。
C / 非均匀地形
少走两步，可能多花六倍代价。
这个小反例中，BFS 走 6 步，真实代价却为 51；UCS 与 A* 绕行 8 步，代价只有 8。评价目标从“最短步数”变为“最低代价”后，算法结论也必须改变。
新增地形实验包含 3 种尺寸、2 种拓扑、3 种代价分布，共 360 张地图。参考最优值由独立 SciPy 有向 Dijkstra 复核。
D / 地形与大图批量验证
把波动和边界一起展示。
新增 540 张地图，每图 9 种算法、各重复计时 3 次，共 14,580 次搜索。大图尺寸从 201 × 401 到 401 × 801。
扩展节点数 / 同图 UCS
搜索耗时 / 同图 UCS
| 算法 | 最优率 | 扩展比中位数 [95% CI] | 耗时比中位数 [95% CI] | 预算耗尽图数 |
|---|
置信区间：每图 3 次计时取中位数，再以地图为抽样单位进行 5000 次配对百分位 bootstrap。图中的点为配对比值中位数，横线为 95% 区间；竖虚线 1 表示与 UCS 相同。效率区间仅包含完成的可解地图；最优率分母保留全部可解地图。
边界情况也保留：19 个“地图 × 算法”组合发生预算耗尽，共 57 次计时尝试；全部位于参考解判定无解的地图。预算耗尽本身仍不构成无解证明。已完成的加权结果未出现名义上界违规。
查看 Python 录制动图与完整结果图
这些图片与录制动图来自最新 Python 工程；上方实验台则在你的设备上重新计算。
04 / WHAT WE LEARNED
没有脱离地图与目标的“最好算法”。
先定义“好”
最少步数、最低代价、更少扩展、更短耗时，是不同指标。地形代价变化时，评价也要随之改变。
启发式有条件
四邻域、代价单位、可采纳性与重开规则共同决定 A* 的保证。权重增大，也可能引起更多重开。
改进需要算总账
ALT 和拓扑剪枝会增加预处理开销。一次查询与重复查询的收益不同，预处理时间必须单列。
样本与未完成都要保留
地图规模变大，A* 的相对优势并非单调增长。预算耗尽表示尚未完成，不能据此证明无解。