同一张地图,两种找路的直觉

你出题,算法找路。

先跑完这张图,留住地图和结果。再改一格墙,再跑一次看变化。

三猫去同一个零食点
改地图与画笔 画墙
画错也没关系
先跑完一轮,留住对照。
先猜,再走一步。看看算法和你想得一不一样。

两边同步,整笔可撤销。键盘:方向键移动,空格编辑,Ctrl / ⌘ Z 撤销。

看前后对照 ↓9 格墙
BFS

一圈一圈地找

等待出发

广度优先搜索,把附近的岔路都看一遍。

0已探索格子
待揭晓最短路线步数

不预判方向,按离起点的距离探索。

A*

朝着目标试探

等待出发

A* 搜索,同时考虑已走距离与预计余程。

0已探索格子
待揭晓最短路线步数

方向只是线索,遇到墙也要绕路。

S起点G终点墙已探索待探索最终路径

我的这一步,改变了什么

改一格,看懂一次变化。

回到地图改一格 ↑

先完整跑完一轮,我们会留住地图和结果。再改一格墙,就能把前后放在一起看。

三猫小场景 · 只改一格

同一个零食点,谁的路更短?

嘿姆、波比、臭臭从不同的地方出发。点一格就能加墙或拆墙,看看谁要绕路、谁捡到了近路。

每次只改一格,不叠加。点墙拆开,点空地加墙,再比较三只猫的路。键盘用方向键移动,空格或 Enter 改一格。

改后 在这张图点一格
三只猫各走几步?
猫咪原图改后变化

每只猫都用 A* 单独找路,只能上下左右走,每格 1 步。起点不同,比较的是路程,不是猫的速度或算法的快慢。

原图 对照不变

猫头像是起点,★ 是零食点;粉线是当前选中猫的一条最短路。

回实验列表

这一局,发现了什么

最短的路,不止一种找法。

先跑一轮,再挪动一块墙。地图里的一个小改变,就可能让算法换一种走法。

给你一个出题挑战

亲手改一张地图,让 A* 少探索至少一半格子,还能找到出口。

先跑完一轮,留住对照。

为什么都能找到最短路?这个比较又有什么边界?

这里只能上下左右走,每一步成本相同。广度优先搜索按层展开,所以第一次找到终点就是最短路。

A* 使用「已走步数 + 曼哈顿距离」排序。曼哈顿距离是不考虑墙时的横向加纵向距离,在这张地图里不会高估余程,所以也能保证最短路。分数相同优先预计余程更短的节点,再按入队顺序。

两边每一拍各展开一个格子,找到终点后各自停止。探索数包括起终点,不包括仅进入待探索队列的格子;路线步数不包括起点。探索更少不等于实际运行更快,A* 还要维护排序。

相同地图必得相同结果。A* 不保证在每张地图上都省下一半搜索;路线可能不同,但最短长度相同。刷新会重置地图,无账号、上传或追踪。

自己出题,才有新发现。

四向移动,每步成本为 1。动画用来理解过程,不代表性能跑分。

MADE BY CHEN QUAN

← 回到学习路线,看看下一步

给算法出道题。

  1. 先点「开始找路」,完整跑完一轮,自动留下第一份对照。
  2. 用「画墙」或「橡皮」改一格,再跑一次。下方会保留前后地图、标出改动,并解释结果的变化。
  3. 画错、清空或换错地图,点「撤销」找回来;一次拖画只算一步,保留最近 30 步。按 Esc 可取消还没松手的一笔。
  4. 点「你来猜下一格」,在 A* 或 BFS 的待探索格中选一个,再揭晓。格上的数字是 A* 总分或 BFS 排队次序;猜错可以继续,地图不会改变。按 Esc 或「回到改图」退出。
  5. 想继续实验,点「以这轮为新对照」再改图。普通「走一步」和自由播放也仍然保留。

手机可以在网格上直接画,网格外可正常滑动。键盘方向键移动、空格编辑(猜测时是选择),Ctrl / ⌘ Z 撤销,Ctrl / ⌘ Shift Z 重做。改图会清除当前动画,但保留对照;刷新会清空地图、对照与编辑历史。