《貪婪算法》PPT課件

《《貪婪算法》PPT課件》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、2021/7/191第三部分算法設(shè)計(jì)方法2021/7/192相關(guān)章節(jié)Chapter13貪婪算法Chapter14分而治之算法Chapter15動(dòng)態(tài)規(guī)劃Chapter16回溯Chapter17分枝定界2021/7/193貪婪算法的特點(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ì)2021/7/194分而治之算法的特點(diǎn)通過把問題化為較小的問題來解決

2、原問題，從而簡化或減少了原問題的復(fù)雜度示例：折半查找、快速排序、歸并排序特點(diǎn)：自頂向下、問題化解子結(jié)構(gòu)不重復(fù)分、治、合2021/7/195動(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ì)2021/7/196回溯算法的特點(diǎn)也是從某一集合中選出子集，進(jìn)行逐項(xiàng)的測試比較逐步達(dá)到整個(gè)解，通過逐

3、步逼近最優(yōu)解而最終得到滿足條件的解在搜索解空間樹時(shí)，能夠跳過無解分枝！示例：迷宮問題、八皇后問題特點(diǎn)：能夠得到最優(yōu)解最優(yōu)化問題的通法2021/7/197分枝定界算法的特點(diǎn)在系統(tǒng)搜索問題的解空間樹時(shí)，加入上下界的條件檢查以達(dá)到有效剪枝的目的特點(diǎn)：能夠得到最優(yōu)解多步判斷＋多米諾性質(zhì)2021/7/198Chapter13貪婪算法中國地質(zhì)大學(xué)信息工程學(xué)院2021/7/199內(nèi)容提要13.1示例問題提出13.2貪婪算法的思想13.3貪婪算法的應(yīng)用貨箱裝船拓?fù)渑判騿卧醋疃搪窂阶钚『馁M(fèi)生成樹2021/7/1910貪婪算法是指

4、：在對問題求解時(shí)，總是做出在當(dāng)前看來是最好的選擇。也就是說，不從整體最優(yōu)上加以考慮，他所做出的僅是在某種意義上的局部最優(yōu)解。貪婪算法不是對所有問題都能得到整體最優(yōu)解，但對范圍相當(dāng)廣泛的許多問題，他能產(chǎn)生整體最優(yōu)解或者是整體最優(yōu)解的近似解。貪婪算法的基本思路如下：1.建立數(shù)學(xué)模型來描述問題。2.把求解的問題分成若干個(gè)子問題。3.對每一子問題求解，得到子問題的局部最優(yōu)解。4.把子問題的解局部最優(yōu)解合成原來解問題的一個(gè)解。2021/7/1911算法的基本思路從問題的某一個(gè)初始解出發(fā)逐步逼近給定的目標(biāo)，以盡可能快的地求

5、得更好的解。當(dāng)達(dá)到某算法中的某一步不能再繼續(xù)前進(jìn)時(shí)，算法停止。存在問題：1.不能保證求得的最后解是最佳的；2.不能用來求最大或最小解問題；3.只能求滿足某些約束條件的可行解的范圍。2021/7/1912最優(yōu)化問題的幾個(gè)概念每個(gè)最優(yōu)化問題包含一組限制條件和一個(gè)優(yōu)化函數(shù)可行解：符合限制條件的問題求解方案最優(yōu)解：使優(yōu)化函數(shù)取得最佳解的可行解例如：Huffman樹，從可用的二叉樹中選取權(quán)重最小的兩棵子樹，進(jìn)行合并2021/7/1913例13-1渴嬰問題2021/7/1914求解：設(shè)各種飲料的滿意度已知。令Xi為嬰兒將要

6、引用的第i種飲料的量，需要解決的問題是：找到一組實(shí)數(shù)Xi（1<=i<=n）使?jié)M足限制條件：優(yōu)化函數(shù)：注意：可行解、優(yōu)化解、無解的情況2021/7/1915例13-2裝載問題2021/7/1916裝載問題求解：找到一組變量Xi，其可能取值為0或1，使它滿足限制條件：優(yōu)化函數(shù)：2021/7/1917例13-3最小代價(jià)通訊網(wǎng)絡(luò)最小耗費(fèi)生成樹2021/7/1918最小代價(jià)生成網(wǎng)絡(luò)求解：選擇一個(gè)無向圖中的邊集合的子集這個(gè)子集必須具備如下：限制條件：所有的邊構(gòu)成一個(gè)生成樹優(yōu)化函數(shù)：子集中所有邊的權(quán)值之和2021/7/191

7、9在貪婪算法（greedymethod）中采用逐步構(gòu)造最優(yōu)解的方法。在每個(gè)階段，都作出一個(gè)看上去最優(yōu)的決策（在一定的標(biāo)準(zhǔn)下）。決策一旦作出，就不再可更改。作出貪婪決策的依據(jù)成為貪婪準(zhǔn)則2、貪婪算法思想2021/7/1920貪心算法的基本思路如下：1.建立數(shù)學(xué)模型來描述問題2.把求解的問題分成若干個(gè)子問題3.對每一子問題求解，得到子問題的局部最優(yōu)解4.把子問題的解局部最優(yōu)解合成原來解問題的一個(gè)解貪婪算法思想（續(xù)1）2021/7/1921實(shí)現(xiàn)該算法的過程：從問題的某一初始解出發(fā)；while能朝給定總目標(biāo)前進(jìn)一步d

8、o求出可行解的一個(gè)解元素；由所有解元素組合成問題的一個(gè)可行解；貪婪算法思想（續(xù)2）2021/7/1922例13-4找零錢問題2021/7/1923貪婪算法有一種直覺的傾向，例如：在找零錢時(shí)，直覺告訴我們應(yīng)使找出的硬幣數(shù)目最少（至少是接近最少的數(shù)目）2021/7/1924例13-5機(jī)器調(diào)度問題使用7臺機(jī)器使用5臺機(jī)器2021/7/1925一種獲取最有分配的貪婪方法是逐步分配任務(wù)。每步分