资源简介

(共23张PPT)
义务教育信息科技（2024）五年级　　　　　　　　　　
第1课时
第七单元　了解更多的算法
五年级下册
第26课　寻找最短的路径
1
2
进一步了解规划算法的思想，体会把全局问
题分解为局部问题的过程。
通过寻找最短路径的算法描述，初步了解路
径规划算法的应用。
学习目标
第26课　寻找最短路径
日常生活中，人们出门时，常常用导航软件查询线路并选择到达目的地的方式。本课通过在一个简单地图上寻找最短的路径，体会相关的算法。
第26课　课堂导入
问题情境
有一个街道地图，共有9个地点，路线正好能形成2行2列的网格。其中，每个点可以对应到不同地点。例如，起点是家，终点是学校，中间有超市、体育馆、公园、书店、博物馆等。
要求：这些道路都是单行线，在图上只能从左往右走或者从上往下走，不能反方向走。
求解：计算从起点走到终点的最短时间。
学习活动
一 用枚举法寻找最短路径
二 用分段用时寻找最短路径
第26课　学习活动
每条边上的数代表走这条路需要用的时间，如3代表3分钟。
一共有两类描述对象：一类是代表所需时间的边，另一类是用边连接的点，也就是地点。边一共有12条，点共有9个。　　
从起点出发到终点结束，只能走下方或者右侧的边。
一、用枚举法寻找最短路径
任务分析
第26课　学习活动
根据给定的图形，你能够列举出所有可能的路径吗？
能找出用时最少的路径吗？
解决问题的关键点是什么呢？
分析思考
第26课　学习活动
一、用枚举法寻找最短路径
1．解决任务最简单的方法就是列举出所有的行走方法，计算时间后，找到用时最少的路径。
这样做存在的问题：种类多，容易有遗漏。
2．将全局问题转化为局部问题。
计算从起点到每个点的最少时间就是小问题。最终求得到终点的最少时间，即是全局问题的解决。
方法突破
第26课　学习活动
一、用枚举法寻找最短路径
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分钟。
遍历所有路径
第26课　学习活动
一、用枚举法寻找最短路径
因此，要用一个计算次数尽可能少，且确保不会遗漏路径的算法。
　　人工用枚举法遍历寻找路径时，随着地点的增加，路径数量会迅速增加，逐个枚举就会很耗费时间，而且很容易遗漏一些路径。例如，要枚举右图所示的路径，操作起来就非常困难。
枚举法的局限
第26课　学习活动
一、用枚举法寻找最短路径
思考：用枚举法遍历存在什么问题呢？
　　把计算整个地图最短路径的用时，转变为计算到具体一个点的最短路径的用时。
到一个点的用时最多有两个来源。
　　一是：上方节点用时+上方路径用时
　　二是：左方节点用时+左方路径用时
　　如果一个点有两个来源，那么选用时较少的一个。
问题分解
第26课　学习活动
二、用分段用时寻找最短路径
在圆圈中填写到该点的最短用时
起点A的用时记为0
B点只能从A点向右，最短路径用时为：
　左边A点的用时+A点到B点的用时
　表示为：A +( A→B) = 0 + 3 = 3
D点只能从A点向下，最短路径用时表示为：
　 A + (A→D) = 0 + 2 = 2
E点可以从B点向下，也可以从D点向右，表示为：
　 B +(B→E) = 3 + 1 = 4，D +(D →E) = 2 + 3 = 5
　 选较短的路径用时：B + (B→E) = 3 + 1 = 4
这样，局部的四个点的最短距离得以解决。
第1步：计算第一个局部。
局部问题解决
第26课　学习活动
二、用分段用时寻找最短路径
第二个局部只需计算两个点C和F。
C点只能从B点向右，表示为：
　 B + (B→C) = 3 + 2 = 5
F点可以从C点向下，也可以从E点向右，表示为：
　 C + (C→F) = 5 + 2 = 7
　 E +( E→F) = 4 + 2 = 6
　 选较短的路径用时，F点的最短路径用时为：
　 E + (E→F) = 4 + 2 = 6
第2步：计算第二个局部。
局部问题解决
第26课　学习活动
二、用分段用时寻找最短路径
至此，六个点的路径距离得以解决，局部进一步扩大。
第三个局部也只需计算两个点G和H。
G点只能从D点向下，表示为：
　 D + (D→G) = 2 + 3 = 5
D点只能从A点向下，表示为：
　 A + (A→D) = 0 + 2 = 2
H点可以从E点向下，也可以从G点向右，表示为：
　E + (E→H) = 4 + 1 = 5
　G + (G→H) = 5 + 3 = 8
选较短的路径用时：E + (E→H) = 4 + 1 = 5
第3步：计算第三个局部。
局部问题解决
第26课　学习活动
二、用分段用时寻找最短路径
第四个局部只剩下一个点I。
J点可以从F点向下或者从H点向右。
　F + (F→I) = 6 + 1 = 7
　H + (H→I) = 5 + 3 = 8
　选较短的路径用时，I点的最短路径用时为：
　F + (F→J) = 6 + 1 = 7
第4步：计算第四个局部。
局部问题解决
第26课　学习活动
二、用分段用时寻找最短路径
　获得到I点的最短路径用时为7，全局问题得以解决。
　 F + (F→J) = 6 + 1 = 7
局部问题解决
第26课　学习活动
二、用分段用时寻找最短路径
问题解决过程
第26课　学习活动
二、用分段用时寻找最短路径
导航系统
路径规划算法可以帮助导航系统找到两个地点之间的最短路径，并标注相应的路线，从而提供导航服务。
物流配送
在物流配送过程中，路径规划算法可以帮助物流人员确定最优的配送路线，从而节约时间和成本。还可以帮助物流企业规划仓库的位置，让仓库与客户的距离更近，提高配送效率。
最短路径算法的应用
第26课　学习活动
二、用分段用时寻找最短路径
电力网络
　　电力网络中的电线杆和变电站可以看作是节点，它们之间的电线可以看作是路径，路径规划算法可以帮助确定节点之间的最短电线布局，从而降低电力损耗和成本。
　　此外，路径规划算法还常用于城市规划、交通网络优化、通信网络设计等领域，帮助人们找到最优的路径，从而优化资源分配、提高系统效率。
最短路径算法的应用
第26课　学习活动
二、用分段用时寻找最短路径
　　
1．动态规划是将全局问题转化为局部问题，随着局部问题的解决逐渐扩大到全局问题的解决。
2．在解决局部问题时，可能会出现多个选择，需要抓住局部问题的关键特征，深入思考，进行局部的最优选择。
3．在现实生活中，路径规划算法应用广泛，它与我们的生活、工作和学习已经息息相关。
第26课　课堂总结
　　篮球赛中重要的就是队员互相配合。现在知道对方球队有著名的三人组，这三个人之间配合相当默契。假设三人分别为球员A、球员 B、球员C，在进攻时他们组成三角形进攻。请帮助我方球队分析，如果在一轮进攻中，球员A拿到球，然后把球传给球员 B或球员C，三人之间一共有10次传球，那么第10次传球仍然能传到球员A手中的可能性有多少种？　　
第26课　拓展与提升
打开配套资源中的程序，依据程序的提示，观察、运行程序，分析程序与算法的关系，感受利用算法求解问题的过程。
下课啦！

展开更多......

收起↑