人教版信息科技五年級全一冊 第26課 尋找最短的路徑 課件

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

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

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