义务教育版（2024）五年级信息科技 第26课 寻找最短的路径 课件.pptxVIP

（义务教育版）五年级

全一册

第26课

寻找最短的路径

单元主题

单元名称

课名称

核心内容

第七单元

了解更多的算法

第24课

多人过河巧安排

规划算法的应用，把大问题分解成小问题解决。

第25课

有趣的七桥问题

抽取问题中的关键要素并进行简化来解决问题，实现一笔画的判断方法。

第26课

寻找最短的路径

把全局问题分解成局部问题解决，寻找最小路径的算法描述。

第27课

网页排名有策略

网页排名算法的作用，提升网页价值的意义，网络使用的规范及其存在的风险。

学习目标

进一步了解规划算法的思想。

体会把全局问题分解为局部问题的过程。

通过寻找最短路径的算法描述，初步了解路径规划算法的应用。

激趣导入

【生活情境】

比如在一个陌生的城市里，司机叔叔要开车去一个地方，他打开导航软件，输入起点和终点后，导航软件很快就为他规划出了一条最短的路线。

激趣导入

【想一想】

你们知道导航软件是怎么做到的吗？它背后运用了什么神奇的算法呢？

学习活动

一、学习探究

二、用枚举法寻找最短路径

三、用分段用时寻找最短路径

学习活动

学习活动

一、学习探究

有一个街道地图，共有9个地点，路线正好能形成2行2列的网格。其中，每个点可以对应到不同地点。例如，起点是家，终点是学校，中间有超市、体育馆、公园、书店、博物馆等。

每条边上的数代表走这条路需要用的时间，如3代表3分钟。

这些道路都是单行线，在图上只能从左往右走或者从上往下走，不能反方向走。

思考-讨论

一、学习探究

【试一试】

计算从起点走到终点的最短时间。

学习活动

学习活动

二、用枚举法寻找最短路径

先来尝试用枚举法遍历所有可能的路径。

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分钟。

思考-讨论

一、用枚举法寻找最短路径

【想一想】

这样的解法有没有问题呢？

思考-讨论

一、用枚举法寻找最短路径

【想一想】

问题比较明显：随着地点的增加，路径的数量会快速地增长，如果人工用这种方法操作，就会很耗费时间，而且容易遗漏路径。

例如，用遍历的方法列举以下路径，你还能完全列举出来吗？

学习活动

学习活动

三、用分段用时寻找最短路径

下面把计算整个地图最短路径的用时，转变为计算到具体一个点的最短路径的用时。用圆圈中的数表示从起点到该点的最短用时。

学习活动

三、用分段用时寻找最短路径

转变思路后，到一个点的用时最多有两个来源。

一是：上方节点用时+上方路径用时

二是：左方节点用时+左方路径用时

如果一个点有两个来源，那么选其中用时较少的一个。

学习活动

三、用分段用时寻找最短路径

具体步骤如下：

第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