迷宫设置
算法选择
动画速度
统计信息
图例
理论说明
BFS： f(n) = g(n)（仅实际代价）
使用队列，保证最短路径。
DFS： 使用栈，深度优先探索。
不保证最短路径。
A*： f(n) = g(n) + h(n)
h = 曼哈顿距离（启发函数）
最优且高效。
Dijkstra： 考虑所有边权重。
等价于h=0的A*（均匀网格）。
请先生成迷宫
理论与主要公式
$$f(n) = g(n) + h(n)$$
A*アルゴリズムの評価関数：\(g(n)\) スタートからのコスト、\(h(n)\) ゴールへの推定コスト（ヒューリスティック）
$$h(n) = |x_n - x_{goal}| + |y_n - y_{goal}|$$
マンハッタン距離ヒューリスティック：グリッド迷路で最適
$$O(b^d) \text{ (BFS)}, \quad O(b^{d/2}) \text{ (双方向BFS)}$$
計算量：\(b\) 分岐係数、\(d\) 解の深さ
什么是路径搜索算法
🙋
这个迷宫求解器里说的BFS和DFS是什么？听起来好复杂。
🎓
简单来说，你可以把它们想象成两种不同的“找人”策略。BFS（广度优先搜索）就像在迷宫里，你同时派出很多分身，从起点开始，一层一层、一圈一圈地往外找目标。DFS（深度优先搜索）则像你一个人，沿着一条路走到黑，碰壁了再退回来换条路。你试着在模拟器里把“算法”从BFS切换到DFS，然后点“开始”，就能立刻看到它们探索迷宫的方式完全不同！
🙋
诶，真的吗？那BFS找到的路径是不是一定最短？
🎓
没错！在像迷宫这样所有“格子”代价都一样的情况下，BFS保证能找到最短路径。因为它是一层一层“平推”过去的，最先碰到终点的路径就是最短的。而DFS可能会绕远路。你可以在模拟器里生成一个复杂点的迷宫，比如把“尺寸”滑块拖到30x30以上，然后分别运行BFS和DFS，对比一下它们最终找到的路径长度和探索的节点数量，差别会非常明显。
🙋
那A*和Dijkstra又是什么？它们好像比BFS和DFS更高级？
🎓
可以这么理解。BFS和DFS在迷宫里“瞎找”，而A*和Dijkstra是“聪明地找”。Dijkstra算法会考虑每一步的“代价”，总是先探索当前累积代价最小的路径。A*则更聪明，它除了看已经花了多少代价（$g(n)$），还会估计一下离终点还有多远（$h(n)$），然后优先探索总估计代价最小的方向。你试试在模拟器里运行A*，会发现它探索的红色区域非常有方向性地直奔终点，比BFS和DFS高效太多了！
物理模型与关键公式
路径搜索算法的核心是评估和选择下一个要探索的节点。对于Dijkstra算法，它基于从起点到当前节点的实际累积代价（通常为距离或权重）来做决策。
$$d[v] = \min(d[v], d[u] + w(u, v))$$
其中，$d[v]$ 是从起点到节点 $v$ 的当前已知最短距离，$d[u]$ 是到其邻居节点 $u$ 的距离，$w(u, v)$ 是从 $u$ 到 $v$ 的边的权重。算法不断选择 $d$ 值最小的未访问节点进行探索和更新。
A*算法在Dijkstra的基础上引入了启发式函数，其核心是评估函数 $f(n)$，它决定了节点的探索优先级。
$$f(n) = g(n) + h(n)$$
$g(n)$ 是从起点到节点 $n$ 的实际代价（与Dijkstra中的 $d[n]$ 类似）。$h(n)$ 是从节点 $n$ 到目标点的启发式估计代价（例如曼哈顿距离或欧几里得距离）。当 $h(n)$ 是可采纳的（即从不高估实际代价）时，A* 保证能找到最短路径。
现实世界中的应用
CAE网格生成与连通性分析：在有限元分析中，需要确保计算网格的连通性。DFS可用于遍历网格单元，检查是否存在孤立的网格区域，这对于保证计算稳定性至关重要。
流体管网与电路网络分析：在复杂的管道系统或电路板布线中，Dijkstra算法可用于寻找两点间阻力或电阻最小的路径，从而实现最优的流体输送或电流传导设计。
机器人路径规划与自动驾驶：A*算法及其变种被广泛用于机器人的实时避障和路径规划。通过将环境地图网格化，并利用启发函数引导搜索，可以快速为机器人或自动驾驶汽车找到安全高效的行驶路线。
游戏AI与NPC寻路：在电子游戏中，非玩家角色（NPC）的移动几乎都依赖于A*等路径搜索算法。游戏引擎将地图划分为导航网格，算法快速计算出到达玩家位置的最优路径，使NPC的行为看起来更智能。
常见误解与注意事项
开始使用本模拟器时，有几个需要注意的要点。首先，“A*算法并非总是最快”。虽然启发函数确实提升了效率，但在迷宫极其简单（例如几乎没有墙壁的广阔空间）的情况下，启发式计算的开销可能导致其性能不如简单的广度优先搜索（BFS）。你可以在工具中将“尺寸”调小、“墙壁密度”接近0%进行尝试，亲身体验这一现象。
其次，启发函数的选择会直接影响结果。例如，在对角线移动不被允许的迷宫中使用欧几里得距离，可能会低估实际代价，导致不必要的搜索范围扩大。NovaSolver之所以采用曼哈顿距离，正是因为它能在网格状迷宫中发挥最佳效果。实际实现时，选择与问题结构相匹配的距离度量至关重要。
最后，存在一个容易忽略的陷阱：“探索节点数”与“计算时间”并不成正比。深度优先搜索（DFS）可能仅访问较少节点就深入迷宫，表面看似“轻量”，但如果频繁遇到死胡同并需要回溯，反而可能耗费更多处理时间。尤其在复杂迷宫中对比“计算时间”的显示结果，你会发现不同算法内部处理负荷的差异，这非常有趣。
具体计算示例
在30×30迷宫中寻找左上角(0,0)到右下角(29,29)的路径。BFS遍历约450个节点，耗时约9秒（speed=20ms）；DFS可能遍历600个节点但路径次优；A*启发式搜索仅需280个节点，耗时5.6秒；Dijkstra均匀扩展遍历520个节点。实际复杂度为O(n²)，其中n=迷宫边长。