資源簡介

(共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課　拓展與提升
打開配套資源中的程序，依據程序的提示，觀察、運行程序，分析程序與算法的關系，感受利用算法求解問題的過程。
下課啦！

展開更多......

收起↑