資源簡介

(共34張PPT)
第7單元 第2課
最短路徑的算法
（湘科版）五年級
下
1
核心素養目標
3
新知講解
5
拓展延伸
7
板書設計
2
新知導入
4
課堂練習
6
課堂總結
課后作業
8
01
核心素養目標
信息意識
計算思維
數字化學習與創新
信息社會責任
學會在使用算法和處理數據時，考慮到社會責任和道德問題， 探討算法的社會影響，思考怎樣讓技術更好地服務于社會。
編寫程序的過程中，提升數字化技能，探索算法應用的創新可能性，編程完成后，思考其他可以應用這個算法的領域。
學習迪杰斯特拉算法，理解它的步驟，提升解決問題的能力，親自動手解決從一個地方到另一個地方的最短路徑問題。
理解生活中常見問題如何通過算法解決，能把地圖轉成數據表，嘗試用數據去描述一個城市的道路網絡。
02
新知導入
活動背景
在路線相對簡單的情況下，用窮舉法來尋找最短路徑是可行的方法。但如果要在復雜路線中尋找最短路徑，還需要更有效的方法和計算機的幫助。
02
新知導入
活動目標
1、學會用數據表格表示路線圖。
2、了解迪杰斯特拉算法的實現過程。
3、體驗迪杰斯特拉算法的程序實現。
02
新知導入
03
新知講解
一、用數據表格表示路線圖
計算機無法像人一樣直接讀懂圖，為了處理圖的相關問題，需要先將圖轉化為數據表。如左圖所示的路線模型圖，可以轉換為如右圖所示的數據表。
03
新知講解
由于不考慮方向的因素，觀察表格中的數據可以發現，AB與BA之間路線的距離相同,以此類推。所以,表格中黃色部分的數據與藍色部分對稱。數據可以進一步簡化為：
AB=12 AC=3 AD=999 AE=999
BC=5 BD=7 BE=999
CD=999 CE=6
DE=4
03
新知講解
二、迪杰斯特拉算法
要幫助快遞員尋找配送快遞的最短路徑，可以采用迪杰斯特拉算法(Diikstra)，計算從A點出發，去到B、C、D、E各地點配送快遞的最短路徑，具體步驟描述如下。
1、設置初始狀態。設計兩個方框，分別保存已找到的最短路徑和當前發現的路線。從起點A開始，將與起點A相關的路線放入橙框。
03
新知講解
2、尋找第一條最短路徑。
（1）對橙框里的路線排序。
（2）將最短的路線移入藍框。
（3）找到第一條最短路徑。
03
新知講解
3、尋找第二條最短路徑步驟。
步驟1：重新計算路徑長度。計算起點A通過已知最短路徑“AC=3”到達其他點的長度。
03
新知講解
步驟2：比較新路徑與原路徑，用更短的新路徑代替原路徑。
03
新知講解
步驟3：將橙框中的最短路徑移到藍框中。選出第二條最短路徑。
03
新知講解
步驟4：按照同樣的方法，繼續尋找其余最短路徑，直到橙框里的路徑為空。
到此，找到從起點 A到其余四點 B、C、D、E 的最短路徑。
03
新知講解
從起點A到目的點D的最短路徑是A→C→E→D，長度為13。觀察并驗證這個結論。
探究實踐
03
新知講解
用迪杰斯特拉算法尋找最短路徑的過程可以概括為:
03
新知講解
嘗試求解下圖中從A點到其余各點的最短路徑。
探究實踐
03
新知講解
嘗試求解下圖中從A點到其余各點的最短路徑。
探究實踐
目標節點 最短路徑 總距離
A A 0
B A → C → B 8
C A → C 3
D A → C → E → D 13
E A → C → E 9
03
新知講解
三、迪杰斯特拉算法的程序實現
人工推算最短路徑的方法效率低，易出錯。通過計算機編程實現算法可以快速運算出結果，極大地提高效率，解決更復雜的路徑查找問題。
03
新知講解
使用計算軟件尋找最短路徑。
步驟1：將路線圖用數據表格表示。
探究實踐
03
新知講解
步驟2：將數據輸入計算機，計算最短路徑。
探究實踐
步驟3：在路線圖上驗證答案。
04
課堂練習
一、選擇題
1、簡化后的數據表格中，AB=12，BA=12，這是因為（ ）
A. 路線是單向的 B. 路線是雙向的
C. 表格填寫錯誤 D. 需要對稱美觀
2、迪杰斯特拉算法中，初始步驟需要將哪個點的相關路線放入橙框？（ ）
A. 終點 B. 起點
C. 中間點 D. 任意點
3、在迪杰斯特拉算法中，橙框中的路線排序規則是（ ）
A. 從長到短 B. 從短到長
C. 隨機排序 D. 按字母順序
B
B
B
04
課堂練習
4、重新計算路徑長度時，需要基于（ ）
A. 所有可能的路線 B. 已找到的最短路徑
C. 未探索的路線 D. 隨機選擇的路線
5、迪杰斯特拉算法特別適合解決（ ）
A. 簡單路線問題 B. 復雜路線的最短路徑
C. 路線顏色標記 D. 快遞包裹重量
二、判斷題
數據表格簡化后，可以隨意刪除任意一半的數據。（ ）
B
×
B
04
課堂練習
三、操作題
路徑轉化
將下圖路線模型轉化為數據表格：
A—B=5, A—C=2, B—D=8, C—D=4
A B C D
A 0 5 2 999
B 5 0 999 8
C 2 999 0 4
D 999 8 4 0
05
拓展延伸
常見最短路徑算法
除了迪杰斯特拉算法之外，還有很多類似的最短路徑算法，如:弗洛伊德算法、貝爾曼-福特算法(Bellman-Ford)和 SPFA 算法等。這些算法各有特點，可滿足不同的需要。在現實生活中，最短路徑算法的應用非常廣泛，比如手機導航、城市道路規劃和網絡通信等。
05
拓展延伸
生活中的導航小助手
手機地圖如何幫你找到最近的路？它其實用了類似迪杰斯特拉的算法，實時計算道路距離和擁堵情況，像一位隱形向導幫你規劃最優路線！
05
拓展延伸
迷宮游戲的秘密路徑
玩迷宮時如何快速找到出口？試試“貼墻法”或“最短步數法”，這和計算機尋找最短路徑的思路很像，都是通過不斷嘗試和排除錯誤選項。
出口
入口
05
拓展延伸
快遞小哥的智慧派送
快遞公司如何安排送貨順序？他們用算法計算最短路線，減少時間和油耗，下次收到快遞時，可以想想背后的“數學魔法”哦！
05
拓展延伸
算法背后的科學家故事
迪杰斯特拉算法的發明者艾茲赫爾·戴克斯特拉（Edsger Dijkstra）是一位荷蘭計算機科學家，他最初設計這個算法是為了解決鐵路網絡的優化問題。
06
課堂總結
1
引入新知內容
最短路徑的算法
2
用數據表格表示路線圖
3
迪杰斯特拉算法
4
迪杰斯特拉算法的程序實現
5
進行相關知識拓展
1
2
3
4
5
07
板書設計
最短路徑的算法
1、進行新知引入
2、用數據表格表示路線圖
3、迪杰斯特拉算法
4、迪杰斯特拉算法的程序實現
5、進行知識拓展
課后作業。
1、上網查找資料，了解用弗洛伊德算法(Floyd)求解最短路徑的基本過程。
08
課后作業
1、如果兩點間用一個很大的數來表示路線長度，說明 。
2、上網查找資料，了解用弗洛伊德算法(Floyd)求解最短路徑的基本過程。
用弗洛伊德算法找最短路徑的過程，就像玩一個“找近路”的游戲，分三步走：
（1）畫表格：記錄所有路線的長度 。先畫一個表格，寫下每個點到其他點的直接距離（比如：A到B是5，沒直接路就寫∞）。
（2）選中間人：試試“繞道走”會不會更近。比如，現在選一個中間點C，看看：從A到B，是直接走快？還是先到C，再從C到B更快？如果繞道更近，就更新表格里的距離！
（3）重復換中間人，直到試完所有人。
表示道路封閉或不可通行
https://www.21cnjy.com/recruitment/home/fine

展開更多......

收起↑