A* uses an estimate of remaining distance to focus the search.
Click empty squares to draw walls. Drag the green start or red goal to move them.
| Position (r,c) | g (cost from start) | h (heuristic) | f = g + h | Note |
|---|
BFS/DFS don't use g/h/f: they pop by FIFO/LIFO order. Dijkstra uses g only. A* sorts by f.
Pick a scenario, predict what should happen, then apply it and compare the result with your prediction.
Race A* against BFS on the same maze. Watch the frontier, visited count, and path length before deciding which algorithm actually did less work.
Open the race panel after the main grid, then compare A* and BFS on the exact same obstacle layout.
Both algorithms search the maze you built above, one node-expansion per tick. Watch how many cells each opens before reaching the goal: that's why "A* explores fewer nodes than BFS" is a measured result, not a slogan.
No state captured yet. Run or adjust the applet first.
-
Q1. BFS on the demo maze. Is the path BFS finds always the shortest?
Q2. Same maze, DFS. Compared to BFS's path length, DFS finds a path that is:
Q3. A* with admissible Manhattan heuristic vs BFS on the same maze. Number of nodes visited by A* is:
Predict which search will do less work, run a comparison, then explain how the frontier and heuristic changed the result.
Reduced-motion settings are honored where possible. The current state is also available as text, so the main result does not depend only on color, animation, or spatial position.
Accessibility note: this layer gives a text equivalent for the applet state. It does not replace a full human screen-reader audit.
Pathfinding turns a map into a graph of states and connections, then searches for a route from a start state to a goal. Breadth-first search, depth-first search, Dijkstra's algorithm, and A* are foundational strategies whose guarantees depend on edge costs, data structures, and heuristic properties.
BFS uses a first-in, first-out frontier and expands states by increasing number of edges from the start. On an unweighted graph, or one where every edge has the same cost, the first discovered goal path is shortest in edge count when duplicate-state handling is correct.
DFS follows one branch deeply before backtracking. It can use little frontier memory and is useful for reachability or exhaustive traversal, but it does not generally return a shortest path. On an infinite or cyclic space it also needs appropriate depth limits or visited-state handling.
Dijkstra's algorithm expands the state with the smallest known path cost
g(n). It generalizes BFS to graphs with nonnegative, unequal edge costs.
A* expands according to f(n) = g(n) + h(n), where h(n)
estimates the remaining cost to the goal.
h = 0, A* reduces to Dijkstra's expansion rule.
On this four-neighbor unit-cost grid, Manhattan distance is admissible because it never exceeds the shortest path length when walls can only force extra steps. It is also consistent, so standard graph-search A* returns an optimal path. A heuristic that overestimates can be faster in some cases but gives up the usual optimality guarantee.
In open space, Manhattan distance strongly directs A* toward the goal, often reducing expansions relative to BFS. In a maze that forces long detours, the heuristic may provide little useful discrimination and A* can expand nearly as much as Dijkstra or BFS. The gain is not exactly proportional to one heuristic score; it depends on how the estimates order the frontier across the entire problem.
Real routing includes weighted travel times, turn restrictions, dynamic traffic, multiple modes, and hierarchical maps. Robotics may use continuous geometry and collision checking. Games often search navigation meshes or grids and may add jump-point search, hierarchical planning, or path smoothing. These techniques preserve the central separation between accumulated cost, a frontier, duplicate-state control, and optional heuristic guidance.
Curriculum: State-space graphs, frontier discipline, explored sets, path cost, completeness, optimality, admissible and consistent heuristics, and weighted edges.
Pre-exploration prompts:
Post-exploration prompts:
Misconceptions to test: DFS is a shortest-path algorithm; Dijkstra only works on weighted graphs; A* is always faster; any heuristic preserves optimality; BFS simply becomes Dijkstra rather than being a special uniform-cost case.
寻路把地图转换为由状态和连接组成的图，再从起始状态搜索到目标的路线。广度优先搜索、深度优先搜索、Dijkstra 算法和 A* 都是基础策略，它们的保证取决于边成本、数据结构和启发式性质。
BFS 使用先进先出的前沿，按照距离起点的边数逐层扩展状态。在无权图或每条边成本相同的图中，只要重复状态处理正确，第一次找到的目标路径在边数上最短。
DFS 会沿一个分支深入，再回溯。它可以使用较少的前沿内存，适合可达性检查或穷尽遍历，但通常不返回最短路径。在无限或含环空间中，还需要适当的深度限制或已访问状态处理。
Dijkstra 算法扩展已知路径成本 g(n) 最小的状态。它把 BFS 推广到具有非负且不相等边成本的图。A* 按照 f(n) = g(n) + h(n) 扩展，其中 h(n) 估计到目标的剩余成本。
h = 0 时，A* 的扩展规则退化为 Dijkstra。
在这个四方向单位成本网格中，曼哈顿距离是可采纳的，因为墙壁只会迫使路径增加步数，不会让真实最短路径短于曼哈顿距离。它也具有一致性，因此标准图搜索 A* 会返回最优路径。高估的启发式在某些情况下可能更快，但会放弃通常的最优性保证。
在开放空间中，曼哈顿距离会明显把 A* 引向目标，通常比 BFS 扩展更少状态。在迫使长距离绕行的迷宫中，启发式可能几乎无法区分候选状态，A* 的扩展数量可能接近 Dijkstra 或 BFS。收益并不与某一个启发式分数严格成比例，而取决于估计如何在整个问题中排列前沿。
真实路线规划包含加权行程时间、转弯限制、动态交通、多种交通方式和分层地图。机器人路径规划还可能使用连续几何和碰撞检测。游戏通常在导航网格或规则网格上搜索，并可能加入跳点搜索、分层规划或路径平滑。这些技术仍保留几个核心部分：累计成本、前沿、重复状态控制，以及可选的启发式引导。
课程目标：状态空间图、前沿规则、已探索集合、路径成本、完备性、最优性、可采纳与一致启发式，以及加权边。
探索前问题：
探索后问题：
需要检验的误解：DFS 是最短路径算法；Dijkstra 只能用于加权图；A* 总是更快；任何启发式都保持最优性；BFS 只是变成 Dijkstra，而不是 Dijkstra 在单位成本下的特殊情况。