Curiosity
地铁换乘怎么秒级排出最优路线
地铁 App 用从起点按乘车时间逐层向外扩展的贪心搜索，每个站点只保留一次最优到达方式，因此几秒内就能锁定全程最短的换乘路线。
Before you enter
A complete interactive classroom, not just a preview.
Start when you are ready to enter this Stage's 7 scenes and explore, respond, and learn as you go.
7
Scenes
14 min
Estimated
Content language: zh-CN
地铁查询 App 是怎么在几秒内，从上百个站点组成的线网里，找出总耗时最短的换乘方案的？
打开任意一个地铁查询 App，输入起点与终点，1 秒内就能拿到一条总耗时最短的换乘方案——而一座城市的地铁站常在上百座以上。
What makes it puzzling
如果要把所有可能的换乘组合都列出来比较，即便只算 20 站以内的方案，组合数也已经大到计算机跑不完；那么 App 是怎么做到秒级响应的？
What you will see
在网格化地铁线网上演示一种逐站向外扩展的扩散过程：起点发出的“波纹”按乘车时间一圈圈蔓延，每抵达一站只保留一次最优到达方式，直到覆盖到目标站时停下。
Payoff
App 把每个车站看作一个节点，用类似“逐层向外推”的贪心搜索只检查每个站点最优的一次到达方式，因此几秒内就能锁定全程最短的换乘路线。
What you might think at first
最稳妥的办法是把所有可能的换乘组合都列出来，逐条比较总耗时，再挑出最短的一条。
Answer
Not covered here
- 实时拥挤度、班次时刻表、步行接驳与出站后导航
- 换乘通道的具体步行时间建模
- 多种交通工具混合出行
What happens inside
- 01几秒排出最优换乘？slide
- 02把所有换乘组合列出来比一比？interactive
- 03一圈圈向外推：扩散波纹slide
- 04为什么“只检查一次”就够了？slide
- 05迁移一下：城际铁路规划呢？quiz
- 06什么时候这个思路会不够用？slide
- 07回到开头的问题slide
Discussion
Discussion threads for a Stage aren't available yet.
Where this leads
Next on this path
More from this author
Other versions of this lesson
Explore more
