貪婪算法ppt課件(已修改)
2025-05-15 18:24 本頁面
【正文】 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 貪婪算法的特點(diǎn) ?通過分階段地挑選最優(yōu)解，較快地得到整體的較優(yōu)解 ?示例： Huffman最優(yōu)編碼， Dijkstra最短路徑 ?特點(diǎn)：既可能得到次優(yōu)解，也可能得到最優(yōu)解，依賴于具體問題的特點(diǎn)和貪心策略的選取 ? 多步判斷＋最優(yōu)子結(jié)構(gòu)性質(zhì)＋貪心選擇性質(zhì) LOGO 2022/5/31 4 分而治之算法的特點(diǎn) ?通過把問題化為較小的問題來解決原問題，從而簡化或減少了原問題的復(fù)雜度 ?示例：折半查找、快速排序、歸并排序 ?特點(diǎn)：自頂向下、問題化解 ? 子結(jié)構(gòu)不重復(fù) ? 分、治、合 LOGO 2022/5/31 5 動態(tài)規(guī)劃算法的特點(diǎn) ?將問題分成子問題來做，從某一集合中選出子集，進(jìn)行逐項的測試比較逐步達(dá)到整個解，通過逐步逼近最優(yōu)解而最終得到滿足條件的解 ?自底向上，利用中間結(jié)果，迅速構(gòu)造問題的解空間樹，以空間換時間 ?示例： Floyd（多源點(diǎn)最短路徑）算法 ?特點(diǎn)：能夠得到最優(yōu)解 ? 多步判斷＋最優(yōu)子結(jié)構(gòu)性質(zhì) LOGO 2022/5/31 6 回溯算法的特點(diǎn) ?也是從某一集合中選出子集，進(jìn)行逐項的測試比較逐步達(dá)到整個解，通過逐步逼近最優(yōu)解而最終得到滿足條件的解 ?在搜索解空間樹時，能夠跳過無解分枝！ ?示例：迷宮問題、八皇后問題 ?特點(diǎn)：能夠得到最優(yōu)解 ? 最優(yōu)化問題的通法 LOGO 2022/5/31 7 分枝定界算法的特點(diǎn) ?在系統(tǒng)搜索問題的解空間樹時，加入上下界的條件檢查以達(dá)到有效剪枝的目的 ?特點(diǎn)：能夠得到最優(yōu)解 ? 多步判斷＋多米諾性質(zhì) LOGO 2022/5/31 8 Chapter13 貪婪算法 中國地質(zhì)大學(xué)信息工程學(xué)院 LOGO 2022/5/31 9 內(nèi)容提要 ? 示例問題提出 ? 貪婪算法的思想 ? 貪婪算法的應(yīng)用 ? 貨箱裝船 ? 拓?fù)渑判? ? 單源最短路徑 ? 最小耗費(fèi)生成樹 LOGO 2022/5/31 10 貪婪算法 是指：在對問題求解時，總是做出在當(dāng)前看來是最好的選擇。也就是說，不從整體最優(yōu)上加以考慮，他所做出的僅是在某種意義上的局部最優(yōu)解。 貪婪算法 不是對所有問題都能得到整體最優(yōu)解，但對范圍相當(dāng)廣泛的許多問題 ， 他能產(chǎn)生整體最優(yōu)解或者是整體最優(yōu)解的近似解。 貪婪算法的基本思路如下： 。 。 ，得到子問題的局部最優(yōu)解。 。 LOGO 2022/5/31 11 算法的基本思路 ?從問題的某一個初始解出發(fā)逐步逼近給定的目標(biāo)，以盡可能快的地求得更好的解。當(dāng)達(dá)到某算法中的某一步不能再繼續(xù)前進(jìn)時，算法停止。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1