单元七 · 了解更多的算法
第26课 寻找最短的路径
一、学习目标
- 进一步了解规划算法的思想，体会把全局问题分解为局部问题的过程。
- 通过寻找最短路径的算法描述，初步了解路径规划算法的应用。
二、情境导入
有一个街道地图，共有 9 个地点，路线正好能形成 3 行 3 列的网格。其中，每个点可以对应到不同地点，例如起点是家，终点是学校，中间有超市、体育馆、公园、书店、博物馆等。
要求：这些道路都是单行线，在图上只能从左往右走或者从上往下走，不能反方向走。求解：计算从起点走到终点的最短时间。
三、核心讲解
本课学习路径：
1．用枚举法寻找最短路径
从起点出发到终点结束，只能走下方或者右侧的边。边代表所需时间（如 2 表示 2 分钟），点代表地点。
想一想：根据给定的图形，你能够列举出所有可能的路径吗？能找出用时最少的路径吗？
枚举部分路径及用时：A→B→C→F→I 为 8 分钟（3+2+2+1）；A→B→E→F→I 为 7 分钟（3+1+2+1）；A→B→E→H→I 为 8 分钟（3+1+1+3）……最短路径是 A→B→E→F→I，用时 7 分钟。
用枚举法遍历存在局限：随着地点增加，路径数量迅速增加，逐个枚举很耗费时间，而且容易遗漏。因此，要用一个计算次数尽可能少、且确保不会遗漏路径的算法。
2．用分段用时寻找最短路径
把计算整个地图最短路径的用时，转变为计算到具体一个点的最短路径的用时（动态规划思想）。
- 到一个点的用时最多有两个来源：上方节点用时 + 上方路径用时；左方节点用时 + 左方路径用时。
- 如果一个点有两个来源，选用时较少的一个，在圆圈中填写到该点的最短用时。
- 起点 A 的用时记为 0；B 点：0+3=3；D 点：0+2=2；E 点取 min(3+1, 2+3)=4。
- 继续计算 C、F 等点：C=3+2=5；F 点取 min(5+2, 4+2)=6。
- G=2+3=5；H 取 min(4+1, 5+3)=5；最终 I 取 min(6+1, 5+3)=7，全局问题得以解决。
路径规划算法在导航系统、物流配送、电力网络等领域应用广泛。
流程图：分段用时求最短路径
弄清以上要点后，再进入下方 Python Online，体验最短路径搜索。
四、动手体验 · Python 3 Online 编程
五年级 · 最短路径：对照课文网格，比较两条路径用时。
正在载入 Python 3 Online
正在载入编程环境…
五、课堂总结
- 动态规划是将全局问题转化为局部问题，随着局部问题的解决逐渐扩大到全局问题的解决。
- 在解决局部问题时，可能会出现多个选择，需要抓住局部问题的关键特征，深入思考，进行局部的最优选择。
- 在现实生活中，路径规划算法应用广泛，它与我们的生活、工作和学习已经息息相关。
六、拓展提升
- 篮球赛中重要的就是队员互相配合。现在知道对方球队有著名的三人组 A、B、C，在进攻时组成三角形进攻。如果在一轮进攻中球员 A 拿到球，然后把球传给球员 B 或球员 C，三人之间一共有 10 次传球，那么第 10 次传球仍然能传到球员 A 手中的可能性有多少种？
测评
选出后点「检查」。答错会显示简短说明。
「用分段用时寻找最短路径」体现了什么思想？
用枚举法寻找最短路径的主要局限是？
计算某点最短用时时，若该点可从上方和左方到达，应如何选取？
本节小结
最短路径可先枚举对比，但更宜用分段用时（动态规划）逐点求局部最优；导航、物流等都离不开路径规划算法。