导航几秒算出全城最短路线
导航用从起点逐层向外扩展的贪心搜索，只检查每一个路口最优的一次到达方式，因此几秒内即可锁定全城最短路线。
A complete interactive classroom, not just a preview.
Start when you are ready to enter this Stage's 4 scenes and explore, respond, and learn as you go.
导航软件为什么能在几秒内找到穿越全城的最短路线？
你打开导航，输入目的地，几秒后一条穿越全城道路网的最短路线就出现在屏幕上——这座城市可能有几百万个路口和几千万条路段。
直觉上，全城搜索似乎要遍历无数种走法，几年也算不完；可导航却秒级返回答案。
用一张演示图展示一个被分成一格格小区域的简化路网，并对比逐个探索每条路与按距离由近及远一圈圈扩展两种策略的耗时差异。
导航之所以能秒算全城最短路线，是因为它不盲目枚举所有路径，而是用一种类似水波扩散的方式，从起点一圈圈向外推进，每一圈只检查一次，直到抵达目的地。.
- 不展开真实交通数据与实时路况
- 不展开 A* 启发式与更高级剪枝算法
- 不展开路网存储结构
- 不展开路线引导和语音播报
- 01几秒算完全城路线？slideSlot 1Hook
展示手机导航输入目的地后秒级出现最短路线的画面，并给出全城路网规模的体量感。
- 输入目的地
- 全城几百万个路口
- 几秒内给出最短路线
Phenomenon导航在几秒内给出穿越几百万个路口的最短路线
Question它是怎么在这么短时间内算出来的？
- 02为什么不遍历所有走法？slideSlot 2Tension
把全城路线搜索比作在迷宫里逐条尝试每条可能路径，引出指数级爆炸的计算代价。
- 每到一个路口都可以左转右转直行
- 路径数随路口数指数增长
- 即使计算机也跑不完
Prediction要保证找到最短路线，必须把所有可能路径都尝试一遍
Tempting intuition最稳妥的做法是把每一条可能的走法都列出来比一比
- 03一圈圈向外推：Dijkstra 思想slideSlot 3Reveal
说明导航不是逐条枚举路径，而是用类似水波扩散的方式，按距离从近到远一圈圈向外扩展，直到波及目的地。
- 从起点出发，先覆盖相邻路口
- 一圈圈向外，记录每个路口的最短到达时间
- 一旦覆盖到目的地，立即得到最短路线
Evidence演示动画：起点发出的波纹一圈圈扩散，每到一个路口只保留最短的到达方式，直到抵达终点。
Conclusion导航用的是逐层向外推进的贪心搜索，每个路口只被认真检查一次，所以几秒内就能锁定全城最短路线。
Mechanism- 1把每个路口看成一个小格子，起点先点亮最临近的几个格子，并记下到达它们的累计时间
- 2再从这些已点亮的格子出发，继续点亮时间更长的下一圈格子；任何格子如果第二次被到达，时间一定不会更短，因此只保留一次最优记录
- 3重复这种逐层扩展，直到终点被点亮时，当前记录的时间就是全城最短路线
- 04外卖派单也用同一个思路slideSlot 4Takeaway
把这个思路迁移到外卖派单场景：平台也要在极短时间内决定谁去送哪一单。
- 外卖订单像“目的地”
- 骑手位置像“起点”
- 同样用逐层扩散找最近骑手
Transfer把外卖平台看成“导航”：订单是目的地，骑手是起点，平台要快速找到最近骑手。
Expected inference你会预期外卖派单也用“逐层向外扩展”的思路来秒级匹配，而不是逐一对比所有骑手。
Discussion threads for a Stage aren't available yet.
