貪婪算法ppt課件-wenkub
2023-05-18 18:24:58 本頁面
【正文】 。LOGO 2022/5/31 1 第三部分 算法設(shè)計方法 LOGO 2022/5/31 2 相關(guān)章節(jié) ? Chapter13 貪婪算法 ? Chapter14 分而治之算法 ? Chapter15 動態(tài)規(guī)劃 ? Chapter16 回溯 ? Chapter17 分枝定界 LOGO 2022/5/31 3 貪婪算法的特點 ?通過分階段地挑選最優(yōu)解，較快地得到整體的較優(yōu)解 ?示例： Huffman最優(yōu)編碼， Dijkstra最短路徑 ?特點：既可能得到次優(yōu)解，也可能得到最優(yōu)解，依賴于具體問題的特點和貪心策略的選取 ? 多步判斷＋最優(yōu)子結(jié)構(gòu)性質(zhì)＋貪心選擇性質(zhì) LOGO 2022/5/31 4 分而治之算法的特點 ?通過把問題化為較小的問題來解決原問題，從而簡化或減少了原問題的復雜度 ?示例：折半查找、快速排序、歸并排序 ?特點：自頂向下、問題化解 ? 子結(jié)構(gòu)不重復 ? 分、治、合 LOGO 2022/5/31 5 動態(tài)規(guī)劃算法的特點 ?將問題分成子問題來做，從某一集合中選出子集，進行逐項的測試比較逐步達到整個解，通過逐步逼近最優(yōu)解而最終得到滿足條件的解 ?自底向上，利用中間結(jié)果，迅速構(gòu)造問題的解空間樹，以空間換時間 ?示例： Floyd（多源點最短路徑）算法 ?特點：能夠得到最優(yōu)解 ? 多步判斷＋最優(yōu)子結(jié)構(gòu)性質(zhì) LOGO 2022/5/31 6 回溯算法的特點 ?也是從某一集合中選出子集，進行逐項的測試比較逐步達到整個解，通過逐步逼近最優(yōu)解而最終得到滿足條件的解 ?在搜索解空間樹時，能夠跳過無解分枝！ ?示例：迷宮問題、八皇后問題 ?特點：能夠得到最優(yōu)解 ? 最優(yōu)化問題的通法 LOGO 2022/5/31 7 分枝定界算法的特點 ?在系統(tǒng)搜索問題的解空間樹時，加入上下界的條件檢查以達到有效剪枝的目的 ?特點：能夠得到最優(yōu)解 ? 多步判斷＋多米諾性質(zhì) LOGO 2022/5/31 8 Chapter13 貪婪算法 中國地質(zhì)大學信息工程學院 LOGO 2022/5/31 9 內(nèi)容提要 ? 示例問題提出 ? 貪婪算法的思想 ? 貪婪算法的應(yīng)用 ? 貨箱裝船 ? 拓撲排序 ? 單源最短路徑 ? 最小耗費生成樹 LOGO 2022/5/31 10 貪婪算法 是指：在對問題求解時，總是做出在當前看來是最好的選擇。 。當達到某算法中的某一步不能再繼續(xù)前進時，算法停止。 ?在每個階段，都作出一個看上去最優(yōu)的決策（在一定的標準下）。 ?若已經(jīng)至少有一件任務(wù)分配給某臺機器，則稱這臺機器是舊的；若機器非舊則它就是新的。 ?貨箱 7, 3 , 6 , 8 , 4 , 1的總重量為 390個單位且已被裝載，剩下的裝載能力為 10個單位，小于剩下的任何一個貨箱。 } LOGO 2022/5/31 32 templateclass T bool IndirectListT::
教學課件相關(guān)推薦
鄂ICP備17016276號-1