一圈一圈地找
广度优先搜索,把附近的岔路都看一遍。
不预判方向,按离起点的距离探索。
同一张地图,两种找路的直觉
先跑完这张图,留住地图和结果。再改一格墙,再跑一次看变化。
三猫去同一个零食点广度优先搜索,把附近的岔路都看一遍。
不预判方向,按离起点的距离探索。
A* 搜索,同时考虑已走距离与预计余程。
猜的是下一个要探索的格子,不是最终路线的下一步。实线框是你的选择,双线框是算法的选择。
方向只是线索,遇到墙也要绕路。
我的这一步,改变了什么
先完整跑完一轮,我们会留住地图和结果。再改一格墙,就能把前后放在一起看。
虚线框是改动位置 · +加墙 · −去墙 · S / G 起终点 · 实线轨迹是最终路径
| 指标 | 之前 | 之后 | 变化 |
|---|---|---|---|
| 路线步数 | |||
| BFS 探索格 | |||
| A* 探索格 |
对照不会自动替换;只保留在当前页面,刷新会清空。探索格数不是运行速度。
三猫小场景 · 只改一格
嘿姆、波比、臭臭从不同的地方出发。点一格就能加墙或拆墙,看看谁要绕路、谁捡到了近路。
每次只改一格,不叠加。点墙拆开,点空地加墙,再比较三只猫的路。键盘用方向键移动,空格或 Enter 改一格。
| 猫咪 | 原图 | 改后 | 变化 |
|---|
每只猫都用 A* 单独找路,只能上下左右走,每格 1 步。起点不同,比较的是路程,不是猫的速度或算法的快慢。
猫头像是起点,★ 是零食点;粉线是当前选中猫的一条最短路。
这一局,发现了什么
先跑一轮,再挪动一块墙。地图里的一个小改变,就可能让算法换一种走法。
亲手改一张地图,让 A* 少探索至少一半格子,还能找到出口。
先跑完一轮,留住对照。
这里只能上下左右走,每一步成本相同。广度优先搜索按层展开,所以第一次找到终点就是最短路。
A* 使用「已走步数 + 曼哈顿距离」排序。曼哈顿距离是不考虑墙时的横向加纵向距离,在这张地图里不会高估余程,所以也能保证最短路。分数相同优先预计余程更短的节点,再按入队顺序。
两边每一拍各展开一个格子,找到终点后各自停止。探索数包括起终点,不包括仅进入待探索队列的格子;路线步数不包括起点。探索更少不等于实际运行更快,A* 还要维护排序。
相同地图必得相同结果。A* 不保证在每张地图上都省下一半搜索;路线可能不同,但最短长度相同。刷新会重置地图,无账号、上传或追踪。
四向移动,每步成本为 1。动画用来理解过程,不代表性能跑分。
MADE BY CHEN QUAN