資源簡介

(共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. 用枚舉法存在的問題
計算從起點走到終點的最短時間
拓展-提升
籃球賽中重要的就是隊員互相配合?，F在知道對方球隊有著名的三人組，這三個人之間配合相當默契。
假設三人分別為球員 A、球員 B、球員 C，在進攻時他們組成三角形進攻。請幫助我方球隊分析，如果在一輪進攻中，球員 A 拿到球，然后把球傳給球員 B 或球員 C，三人之間一共有 10 次傳球，那么第 10 次傳球仍然能傳到球員 A 手中的可能性有多少種？
https://www.21cnjy.com/recruitment/home/fine

展開更多......

收起↑