貪婪算法ppt課件-文庫(kù)吧資料
2025-05-09 18:24本頁(yè)面
【正文】 3. 對(duì)每一子問(wèn)題求解，得到子問(wèn)題的局部最優(yōu)解 4. 把子問(wèn)題的解局部最優(yōu)解合成原來(lái)解問(wèn)題的一個(gè)解 貪婪算法思想（續(xù) 1） LOGO 2022/5/31 21 ?實(shí)現(xiàn)該算法的過(guò)程： 從問(wèn)題的某一初始解出發(fā)； while 能朝給定總目標(biāo)前進(jìn)一步 do 求出可行解的一個(gè)解元素； 由所有解元素組合成問(wèn)題的一個(gè)可行解； 貪婪算法思想（續(xù) 2） LOGO 2022/5/31 22 例 134 找零錢問(wèn)題 LOGO 2022/5/31 23 ?貪婪算法有一種 直覺(jué) 的傾向， ?例如：在找零錢時(shí)，直覺(jué)告訴我們應(yīng)使找出的硬幣數(shù)目最少（至少是接近最少的數(shù)目） LOGO 2022/5/31 24 例 135 機(jī)器調(diào)度問(wèn)題 使用 7臺(tái)機(jī)器 使用 5臺(tái)機(jī)器 LOGO 2022/5/31 25 ?一種獲取最有分配的貪婪方法是逐步分配任務(wù)。 ?在每個(gè)階段，都作出一個(gè)看上去最優(yōu)的決策（在一定的標(biāo)準(zhǔn)下）。 LOGO 2022/5/31 12 最優(yōu)化問(wèn)題的幾個(gè)概念 ?每個(gè)最優(yōu)化問(wèn)題包含一組 限制條件 和一個(gè)優(yōu)化函數(shù) ?可行解 ：符合限制條件的問(wèn)題求解方案 ?最優(yōu)解 ：使優(yōu)化函數(shù)取得最佳解的可行解 ?例如： Huffman樹(shù)，從可用的二叉樹(shù)中選取權(quán)重最小的兩棵子樹(shù)，進(jìn)行合并 LOGO 2022/5/31 13 例 131 渴嬰問(wèn)題 LOGO 2022/5/31 14 求解： 設(shè)各種飲料的滿意度已知。當(dāng)達(dá)到某算法中的某一步不能再繼續(xù)前進(jìn)時(shí)，算法停止。 。 。 貪婪算法 不是對(duì)所有問(wèn)題都能得到整體最優(yōu)解，但對(duì)范圍相當(dāng)廣泛的許多問(wèn)題 ， 他能產(chǎn)生整體最優(yōu)解或者是整體最優(yōu)解的近似解。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) ?通過(guò)分階段地挑選最優(yōu)解，較快地得到整體的較優(yōu)解 ?示例： Huffman最優(yōu)編碼， Dijkstra最短路徑 ?特點(diǎn)：既可能得到次優(yōu)解，也可能得到最優(yōu)解，依賴于具體問(wèn)題的特點(diǎn)和貪心策略的選取 ? 多步判斷＋最優(yōu)子結(jié)構(gòu)性質(zhì)＋貪心選擇性質(zhì) LOGO 2022/5/31 4 分而治之算法的特點(diǎn) ?通過(guò)把問(wèn)題化為較小的問(wèn)題來(lái)解決原問(wèn)題，從而簡(jiǎn)化或減少了原問(wèn)題的復(fù)雜度 ?示例：折半查找、快速排序、歸并排序 ?特點(diǎn)：自頂向下、問(wèn)題化解 ? 子結(jié)構(gòu)不重復(fù) ? 分、治、合 LOGO 2022/5/31 5 動(dòng)態(tài)規(guī)劃算法的特點(diǎn) ?將問(wèn)題分成子問(wèn)題來(lái)做，從某一集合中選出子集，進(jìn)行逐項(xiàng)的測(cè)試比較逐步達(dá)到整個(gè)解，通過(guò)逐步逼近最優(yōu)解而最終得到滿足條件的解 ?自底向上，利用中間結(jié)果，迅速構(gòu)造問(wèn)題的解空間樹(shù)，
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1