跳到主要内容
Z

A* 寻路算法可视化工具

在方格网格上交互式演示 A* 寻路算法,使用曼哈顿距离启发式函数——绘制墙壁障碍、拖动起点/终点、生成迷宫、逐步执行搜索过程。完全在浏览器中运行。

免费 无需注册 客户端运行 注重隐私 Updated

Move the indigo token with ↑ ↓ ← → / WASD (or tap an adjacent cell) from the green start to the red goal. Walls block you.

Moves: Time: 🎉 Reached the goal!
/

伪代码

使用方法

  1. 1 按住鼠标拖动来绘制墙壁障碍;拖动绿色起点或红色终点即可改变位置。
  2. 2 点击 Play 观看 A* 借助距离启发式函数向目标推进的过程。
  3. 3 使用 Maze 立即生成障碍物,或使用 Step 逐个节点地执行搜索。
  4. 4 留意 A* 相比 Dijkstra 或 BFS 遍历的格子要少得多。

为什么使用此工具

  • 直观感受曼哈顿距离启发式函数如何引导搜索过程直奔目标。
  • A* 能找到最短路径,同时遍历的节点数远少于无信息搜索。
  • 可在本工具与 Dijkstra / BFS 可视化工具之间切换,对比不同的遍历方式。
  • 完全在你的浏览器中运行,无需注册,无需上传文件。

常见问题

什么是 A* 算法?

A*(读作 A-star)是一种最佳优先(best-first)寻路算法,它按照 f = g + h 对边界节点(frontier)排序,其中 g 是从起点出发的实际代价,h 是到目标点代价的启发式估计值。

这个工具使用的是哪种启发式函数?

曼哈顿距离(|Δrow| + |Δcol|),这是一种在四方向网格上可采纳(admissible)的启发式函数——它永远不会高估实际代价,因此 A* 始终能保证找到最短路径。

A* 算法的时间复杂度是多少?

最坏情况下与 Dijkstra 相同,为 O(E log V),但在有良好启发式函数的情况下,实际遍历的节点数会少得多。

A* 在什么情况下优于 Dijkstra?

只要你有一个明确的单一目标点以及一个有效的启发式函数,A* 就更有优势。A* 会集中朝目标方向搜索,而 Dijkstra 则会向各个方向均匀扩展。

什么是 A* 寻路算法可视化工具？

A* 寻路算法可视化工具动态演示了 A* 搜索算法在方格网格上的运行过程。A* 按照 f = g + h(已走过的代价加上曼哈顿距离启发式估计值)对边界节点(frontier)进行排序,从而使搜索过程朝目标方向推进,在比无信息搜索算法(uninformed search)遍历少得多的格子的情况下,找到最短路径。

功能特性

逐步动画演示

观察开放集在 f = g + h 的引导下逐步向目标扩展。

复杂度

取决于启发式函数（最坏情况下为指数级）；采用可采纳启发式函数 → 最优路径。空间复杂度：O(V)。

100% 隐私保护

完全在浏览器本地运行——不会上传任何数据。

示例

Input

grid with start, goal, obstacles

Output

expand lowest f = g + h toward goal → optimal path (with an admissible heuristic)

常见使用场景

  1. 1

    网格寻路

    在游戏和地图中绕开障碍物，找到最短路线。

  2. 2

    启发式函数与 Dijkstra 算法对比

    了解一个好的启发式函数如何让 A* 比 Dijkstra 算法探索更少的节点。

  3. 3

    可采纳性与最优性

    了解为什么可采纳的启发式函数能保证得到最优路径。

概要

Zerethon 的 A* 寻路可视化工具会在浏览器中动态演示网格上的 A* 搜索过程，按照 f = g + h（已耗费的代价加上到目标的启发式估计值）的顺序扩展节点。在采用可采纳（admissible）启发式函数的情况下，A* 能找到最优路径，且通常比 Dijkstra 算法探索的节点数少得多。其运行时间取决于所用的启发式函数（最坏情况下为指数级）；开放集与封闭集所需的空间复杂度均为 O(V)。

分类
算法
价格
免费
隐私
基于浏览器
注册
无需

参考资料

隐私

除非另有说明，否则你的数据永远不会离开浏览器。A* 寻路算法可视化工具 完全在客户端运行 — 无需上传服务器，不记录日志，不追踪你输入的内容。

刚接触？阅读包含 Big-O 分析的分步讲解： 了解 Graph Algorithms →

对比

Dijkstra vs A*

相关工具

Dijkstra 算法可视化工具

在网格上可视化 Dijkstra 寻路算法——绘制墙壁、拖动起点/终点、生成迷宫，并逐步查看搜索过程。直接在浏览器中运行。

打开工具

广度优先搜索（BFS）可视化工具

在网格地图上交互式演示广度优先搜索——绘制墙壁、拖动起点/终点、生成迷宫，逐层查看搜索范围如何扩展。直接在浏览器中运行。

打开工具

深度优先搜索（DFS）可视化工具

在方格网格上交互式演示深度优先搜索——绘制墙壁、拖动起点/终点、生成迷宫、逐步查看深入探索的过程。直接在浏览器中运行。

打开工具

冒泡排序可视化工具

带动画演示的冒泡排序模拟器，提供单步执行、速度调节、自定义输入数据、实时比较/交换计数器以及伪代码同步高亮。完全在浏览器中运行。

打开工具

在 Zerethon Social 上创作、分享与成长

免费注册。赚取积分，收集成就，与全球创作者建立联系。

免费试用 Zerethon