（義務教育版）五年級全一冊第26課

尋找最短的路徑學習目標激趣導入學習活動學習探究思考-討論課堂小結拓展-提升單元主題單元主題單元名稱課名稱核心內容第七單元了解更多的算法第24課多人過河巧安排規劃算法的應用，把大問題分解成小問題解決。第25課有趣的七橋問題抽取問題中的關鍵要素并進行簡化來解決問題，實現一筆畫的判斷方法。第26課尋找最短的路徑把全局問題分解成局部問題解決，尋找最小路徑的算法描述。第27課

網頁排名有策略網頁排名算法的作用，提升網頁價值的意義，網絡使用的規范及其存在的風險。學習目標進一步了解規劃算法的思想。體會把全局問題分解為局部問題的過程。通過尋找最短路徑的算法描述，初步了解路徑規劃算法的應用。激趣導入【生活情境】比如在一個陌生的城市里，司機叔叔要開車去一個地方，他打開導航軟件，輸入起點和終點后，導航軟件很快就為他規劃出了一條最短的路線。激趣導入【想一想】你們知道導航軟件是怎么做到的嗎？它背后運用了什么神奇的算法呢？學習活動一、學習探究二、用枚舉法尋找最短路徑三、用分段用時尋找最短路徑學習活動活動1：學習探究一學習活動一、學習探究有一個街道地圖，共有9個地點，路線正好能形成2行2列的網格。其中，每個點可以對應到不同地點。例如，起點是家，終點是學校，中間有超市、體育館、公園、書店、博物館等。每條邊上的數代表走這條路需要用的時間，如3代表3分鐘。這些道路都是單行線，在圖上只能從左往右走或者從上往下走，不能反方向走。思考-討論一、學習探究【試一試】計算從起點走到終點的最短時間。學習活動活動2：用枚舉法尋找最短路徑二學習活動二、用枚舉法尋找最短路徑先來嘗試用枚舉法遍歷所有可能的路徑。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分鐘。思考-討論一、用枚舉法尋找最短路徑【想一想】這樣的解法有沒有問題呢？思考-討論一、用枚舉法尋找最短路徑【想一想】問題比較明顯：隨著地點的增加，路徑的數量會快速地增長，如果人工用這種方法操作，就會很耗費時間，而且容易遺漏路徑。例如，用遍歷的方法列舉以下路徑，你還能完全列舉出來嗎？學習活動活動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=4D+（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=7H+（H→I）=5+3=8選較短的路徑用時：F+（F→I）=6+1=7學習活動三、用分段用時尋找最短路徑最后獲得結果，從起點到終點最短用時為7分鐘，路徑為：A→B→E→F→I知識拓展路徑規劃算法在現實生活中有廣泛的應用，舉例如下：導航系統：路徑規劃算法可以幫助導航系統找到兩個地點之間的最短路徑，并標注相應的路線，從而提供導航服務。物流配送：在物流配送過程中，路徑規劃算法可以幫助物流人員確定最優的配送路線，從而節約時間和成本；還可以幫助物流企業規劃倉庫的位置，讓倉庫與客戶的距離更近，提高配送效率。電力網絡：電力網絡中的電線桿和變電站可以看作是節點，它們之間的電線可以看作是路徑，路徑規劃算法可以幫助確定節點之間的最短電線布局，從而降低電力損耗和成本。【知識鏈接】課堂小結2用枚舉法尋找最短路徑3用分段用時尋找最短路徑1學習探究1.用枚舉法遍歷所有可能的路徑2.用枚舉法存在的問題計算從起點走到終點的最短時間拓展-提升籃球賽中重要的就是隊員互相配合。現在知道對方球隊有著名的三人