小学义务教育版（2024）第七单元 了解更多的算法第26课 寻找最短的路径授课课件ppt

这是一份小学义务教育版（2024）第七单元 了解更多的算法第26课 寻找最短的路径授课课件ppt，共12页。PPT课件主要包含了学习目标，问题情境，学习活动，任务分析，分析思考，方法突破，遍历所有路径，枚举法的局限，问题分解，局部问题解决等内容，欢迎下载使用。

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