资源简介

(共29张PPT)
（义务教育版）五年级
全一册
第26课
寻找最短的路径
学习目标
激趣导入
学习活动
学习探究
思考-讨论
课堂小结
拓展-提升
单元主题
单元主题
单元名称 课名称 核心内容
第七单元 了解更多的算法 第24 课 　多人过河巧安排 规划算法的应用，把大问题分解成小问题解决。
第 25 课 有趣的七桥问题 抽取问题中的关键要素并进行简化来解决问题，实现一笔画的判断方法。
第 26 课 寻找最短的路径 把全局问题分解成局部问题解决，寻找最小路径的算法描述。
第 27 课 网页排名有策略 网页排名算法的作用，提升网页价值的意义，网络使用的规范及其存在的风险。
学习目标
激趣导入
【生活情境】
比如在一个陌生的城市里，司机叔叔要开车去一个地方，他打开导航软件，输入起点和终点后，导航软件很快就为他规划出了一条最短的路线。
激趣导入
【想一想】
你们知道导航软件是怎么做到的吗？它背后运用了什么神奇的算法呢？
学习活动
学习活动
活动1：学习探究
一
学习活动
一、学习探究
有一个街道地图，共有9个地点，路线正好能形成2行2列的网格。其中，每个点可以对应到不同地点。例如，起点是家，终点是学校，中间有超市、体育馆、公园、书店、博物馆等。
每条边上的数代表走这条路需要用的时间，如 3 代表 3 分钟。
这些道路都是单行线，在图上只能从左往右走或者从上往下走，不能反方向走。
思考-讨论
一、学习探究
【试一试】
计算从起点走到终点的最短时间。
学习活动
活动2：用枚举法寻找最短路径
二
学习活动
二、用枚举法寻找最短路径
先来尝试用枚举法遍历所有可能的路径。
A → B → C → F → I 3 + 2 + 2 + 1 = 8
A → B → E → F → I 3 + 1 + 2 + 1 = 7
A → B → E → H → I 3 + 1 + 1 + 3 = 8
A → D → E → F → I 2 + 3 + 2 + 1 = 8
A → D → E → H → I 2 + 3 + 1 + 3 = 9
A → D → G → H → I 2 + 3 + 3 + 3 = 11
学习活动
二、用枚举法寻找最短路径
这样获得的路径是 A→B→E→F→I，用时7分钟。
思考-讨论
一、用枚举法寻找最短路径
【想一想】
这样的解法有没有问题呢？
思考-讨论
一、用枚举法寻找最短路径
【想一想】
问题比较明显：随着地点的增加，路径的数量会快速地增长，如果人工用这种方法操作，就会很耗费时间，而且容易遗漏路径。
例如，用遍历的方法列举以下路径，你还能完全列举出来吗？
学习活动
活动3：用分段用时寻找最短路径
三
学习活动
三、用分段用时寻找最短路径
下面把计算整个地图最短路径的用时，转变为计算到具体一个点的最短路径的用时。用圆圈中的数表示从起点到该点的最短用时。
学习活动
三、用分段用时寻找最短路径
转变思路后，到一个点的用时最多有两个来源。
一是：上方节点用时 + 上方路径用时
二是：左方节点用时 + 左方路径用时
如果一个点有两个来源，那么选其中用时较少的一个。
学习活动
三、用分段用时寻找最短路径
具体步骤如下：
第 1 步：计算第一个局部，A、B、D、E 四个点。
（1）起点A的用时记为0
（2）B点只能从A点向右，最短路径用时为：
左边A点的用时+A点到B点的用时
可以表示为：A +（A→B）= 0 + 3 = 3
学习活动
三、用分段用时寻找最短路径
（3）D 点只能从 A 点向下，最短路径用时为：
　　 A +（A → D）= 0 + 2 = 2
（4）E 点可以从 B 点向下，也可以从 D 点向右，分别表示为：
　　 B +（B → E）= 3 + 1 = 4
　　 D +（D → E）= 2 + 3 = 5
选较短的路径用时：B +（B → E）= 3 + 1 = 4
学习活动
三、用分段用时寻找最短路径
第 2 步：计算第二个局部 C 点和 F 点。
（1） C 点只能从 B 点向右，最短路径用时为： B +（B → C）= 3 + 2 = 5
（2）F 点可以从 C 点向下，也可以从 E 点向右，分别表示为：
　 C +（C → F）= 5 + 2 = 7
　 E +（E → F）= 4 + 2 = 6
学习活动
三、用分段用时寻找最短路径
第 3 步：计算第三个局部 G 点和 H 点。
（1）G点只能从D点向下，最短路径用时为： D +（D→G） = 2 + 3 = 5
（2）H点可以从E点向下，也可以从G点向右，分别表示为：
　　E +（E→H） = 4 + 1 = 5
　 G +（G→H） = 5 + 3 = 8
选较短的路径用时： E +（E→H）= 4 + 1 = 5
学习活动
三、用分段用时寻找最短路径
第 4 步： 计算第四个局部，只剩下 I 点。
I 点可以从 F 点向下或者从 H 点向右。
　　 　F +（F → I）= 6 + 1 = 7
　　　 H +（H → I）= 5 + 3 = 8
选较短的路径用时：F +（F → I）= 6 + 1 = 7
学习活动
三、用分段用时寻找最短路径
最后获得结果，从起点到终点最短用时为 7 分钟，路径为：
A → B → E → F → I
知识拓展
路径规划算法在现实生活中有广泛的应用，举例如下：
导航系统：路径规划算法可以帮助导航系统找到两个地点之间的最短路径，并标注相应的路线，从而提供导航服务。
物流配送：在物流配送过程中，路径规划算法可以帮助物流人员确定最优的配送路线，从而节约时间和成本；还可以帮助物流企业规划仓库的位置，让仓库与客户的距离更近，提高配送效率。
电力网络：电力网络中的电线杆和变电站可以看作是节点，它们之间的电线可以看作是路径，路径规划算法可以帮助确定节点之间的最短电线布局，从而降低电力损耗和成本。
【知识链接】
课堂小结
2
用枚举法寻找最短路径
3
用分段用时寻找最短路径
1
学习探究
1. 用枚举法遍历所有可能的路径
2. 用枚举法存在的问题
计算从起点走到终点的最短时间
拓展-提升
篮球赛中重要的就是队员互相配合。现在知道对方球队有著名的三人组，这三个人之间配合相当默契。
假设三人分别为球员 A、球员 B、球员 C，在进攻时他们组成三角形进攻。请帮助我方球队分析，如果在一轮进攻中，球员 A 拿到球，然后把球传给球员 B 或球员 C，三人之间一共有 10 次传球，那么第 10 次传球仍然能传到球员 A 手中的可能性有多少种？
https://www.21cnjy.com/recruitment/home/fine

展开更多......

收起↑