貪婪算法ppt課件-wenkub
2023-05-18 18:24:58 本頁面
【正文】 。LOGO 2022/5/31 1 第三部分 算法設(shè)計(jì)方法 LOGO 2022/5/31 2 相關(guān)章節(jié) ? Chapter13 貪婪算法 ? Chapter14 分而治之算法 ? Chapter15 動(dòng)態(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 動(dòng)態(tài)規(guī)劃算法的特點(diǎn) ?將問題分成子問題來做，從某一集合中選出子集，進(jìn)行逐項(xiàng)的測試比較逐步達(dá)到整個(gè)解，通過逐步逼近最優(yōu)解而最終得到滿足條件的解 ?自底向上，利用中間結(jié)果，迅速構(gòu)造問題的解空間樹，以空間換時(shí)間 ?示例： Floyd（多源點(diǎn)最短路徑）算法 ?特點(diǎn)：能夠得到最優(yōu)解 ? 多步判斷＋最優(yōu)子結(jié)構(gòu)性質(zhì) LOGO 2022/5/31 6 回溯算法的特點(diǎn) ?也是從某一集合中選出子集，進(jìn)行逐項(xiàng)的測試比較逐步達(dá)到整個(gè)解，通過逐步逼近最優(yōu)解而最終得到滿足條件的解 ?在搜索解空間樹時(shí)，能夠跳過無解分枝！ ?示例：迷宮問題、八皇后問題 ?特點(diǎn)：能夠得到最優(yōu)解 ? 最優(yōu)化問題的通法 LOGO 2022/5/31 7 分枝定界算法的特點(diǎn) ?在系統(tǒng)搜索問題的解空間樹時(shí)，加入上下界的條件檢查以達(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 貪婪算法 是指：在對問題求解時(shí)，總是做出在當(dāng)前看來是最好的選擇。 。當(dāng)達(dá)到某算法中的某一步不能再繼續(xù)前進(jìn)時(shí)，算法停止。 ?在每個(gè)階段，都作出一個(gè)看上去最優(yōu)的決策（在一定的標(biāo)準(zhǔn)下）。 ?若已經(jīng)至少有一件任務(wù)分配給某臺機(jī)器，則稱這臺機(jī)器是舊的；若機(jī)器非舊則它就是新的。 ?貨箱 7, 3 , 6 , 8 , 4 , 1的總重量為 390個(gè)單位且已被裝載，剩下的裝載能力為 10個(gè)單位，小于剩下的任何一個(gè)貨箱。 } LOGO 2022/5/31 32 templateclass T bool IndirectListT::
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1