义务教育版（2024）五年级全一册第26课《寻找最短的路径》课件.pptxVIP

义务教育信息科技（2024）五年级第1课时第七单元了解更多的算法五年级下册第26课寻找最短的路径

12进一步了解规划算法的思想，体会把全局问题分解为局部问题的过程。通过寻找最短路径的算法描述，初步了解路径规划算法的应用。学习目标

第26课寻找最短路径日常生活中，人们出门时，常常用导航软件查询线路并选择到达目的地的方式。本课通过在一个简单地图上寻找最短的路径，体会相关的算法。

第26课课堂导入问题情境有一个街道地图，共有9个地点，路线正好能形成2行2列的网格。其中，每个点可以对应到不同地点。例如，起点是家，终点是学校，中间有超市、体育馆、公园、书店、博物馆等。要求：这些道路都是单行线，在图上只能从左往右走或者从上往下走，不能反方向走。求解：计算从起点走到终点的最短时间。

学习活动一用枚举法寻找最短路径二用分段用时寻找最短路径第26课学习活动

每条边上的数代表走这条路需要用的时间，如3代表3分钟。一共有两类描述对象：一类是代表所需时间的边，另一类是用边连接的点，也就是地点。边一共有12条，点共有9个。从起点出发到终点结束，只能走下方或者右侧的边。一、用枚举法寻找最短路径任务分析第26课学习活动

根据给定的图形，你能够列举出所有可能的路径吗？能找出用时最少的路径吗？解决问题的关键点是什么呢？分析思考第26课学习活动一、用枚举法寻找最短路径

1．解决任务最简单的方法就是列举出所有的行走方法，计算时间后，找到用时最少的路径。这样做存在的问题：种类多，容易有遗漏。2．将全局问题转化为局部问题。计算从起点到每个点的最少时间就是小问题。最终求得到终点的最少时间，即是全局问题的解决。方法突破第26课学习活动一、用枚举法寻找最短路径

A→B→C→F→I 3+2+2+1=8A→B→E→F→I 3+1+2+1=7A→B→E→H→I 3+1+1+3=8A→D→E→F→I 2+3+2+1=8A→D→E→H→I 2+3+1+3=9A→D→G→H→I 2+3+3+3=11最短路径是A→B→E→F→I，用时7分钟。遍历所有路径第26课学习活动一、用枚举法寻找最短路径

因此，要用一个计算次数尽可能少，且确保不会遗漏路径的算法。人工用枚举法遍历寻找路径时，随着地点的增加，路径数量会迅速增加，逐个枚举就会很耗费时间，而且很容易遗漏一些路径。例如，要枚举右图所示的路径，操作起来就非常困难。枚举法的局限第26课学习活动一、用枚举法寻找最短路径思考：用枚举法遍历存在什么问题呢？

把计算整个地图最短路径的用时，转变为计算到具体一个点的最短路径的用时。到一个点的用时最多有两个来源。一是：上方节点用时+上方路径用时二是：左方节点用时+左方路径用时如果一个点有两个来源，那么选用时较少的一个。问题分解第26课学习活动二、用分段用时寻找最短路径在圆圈中填写到该点的最短用时

起点A的用时记为0B点只能从A点向右，最短路径用时为：左边A点的用时+A点到B点的用时表示为：A+(A→B)=0+3=3D点只能从A点向下，最短路径用时表示为：A+(A→D)=0+2=2E点可以从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=5F点可以从C点向下，也可以从E点向右，表示为：C+(C→F)=5+2=7E+(E→F)=4+2=6选较短的路径用时，F点的最短路径用时为：E+(E→F)=4+2=6第2步：计算第二个局部。局部问题解决第26课学习活动二、用分段用时寻找最短路径至此，六个点的路径距离得以解决，局部进一步扩大。

第三个局部也只需计算两个点G和H。G点只能从D点向下，表示为：D+(D→G)=2+3=5D点只能从A点向下，表示为：A+(A→D)=0+2=2H点可以从E点向下，也可以从G点向右，表示为：E+(E→H)=4+1=5G+(G→H)=5+3=8选较短的路径用时：E+(E→H)=4+1=5第3步：计算第三个局部。局部问题解决第26课学习活动二、用分段用时寻