資源描述：
《算法設(shè)計與分析_王紅梅_第7章 貪心法.ppt》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、第7章貪心法7.1概述7.2圖問題中的貪心法7.3組合問題中的貪心法7.4實驗項目——哈夫曼編碼7.1概述7.1.1貪心法的設(shè)計思想7.1.2貪心法的求解過程貪心法在解決問題的策略上目光短淺，只根據(jù)當(dāng)前已有的信息就做出選擇，而且一旦做出了選擇，不管將來有什么結(jié)果，這個選擇都不會改變。換言之，貪心法并不是從整體最優(yōu)考慮，它所做出的選擇只是在某種意義上的局部最優(yōu)。這種局部最優(yōu)選擇并不總能獲得整體最優(yōu)解（OptimalSolution），但通常能獲得近似最優(yōu)解（Near-OptimalSolution）。7.1.1貪心法的設(shè)計思想
2、例：用貪心法求解付款問題。假設(shè)有面值為5元、2元、1元、5角、2角、1角的貨幣，需要找給顧客4元6角現(xiàn)金，為使付出的貨幣的數(shù)量最少，首先選出1張面值不超過4元6角的最大面值的貨幣，即2元，再選出1張面值不超過2元6角的最大面值的貨幣，即2元，再選出1張面值不超過6角的最大面值的貨幣，即5角，再選出1張面值不超過1角的最大面值的貨幣，即1角，總共付出4張貨幣。在付款問題每一步的貪心選擇中，在不超過應(yīng)付款金額的條件下，只選擇面值最大的貨幣，而不去考慮在后面看來這種選擇是否合理，而且它還不會改變決定：一旦選出了一張貨幣，就永遠(yuǎn)選定
3、。付款問題的貪心選擇策略是盡可能使付出的貨幣最快地滿足支付要求，其目的是使付出的貨幣張數(shù)最慢地增加，這正體現(xiàn)了貪心法的設(shè)計思想。貪心法求解的問題的特征：（1）最優(yōu)子結(jié)構(gòu)性質(zhì)當(dāng)一個問題的最優(yōu)解包含其子問題的最優(yōu)解時，稱此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，也稱此問題滿足最優(yōu)性原理。（2）貪心選擇性質(zhì)所謂貪心選擇性質(zhì)是指問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來得到。動態(tài)規(guī)劃法通常以自底向上的方式求解各個子問題，而貪心法則通常以自頂向下的方式做出一系列的貪心選擇。7.1.2貪心法的求解過程用貪心法求解問題應(yīng)該考慮如下幾個方面
4、：（1）候選集合C：為了構(gòu)造問題的解決方案，有一個候選集合C作為問題的可能解，即問題的最終解均取自于候選集合C。例如，在付款問題中，各種面值的貨幣構(gòu)成候選集合。（2）解集合S：隨著貪心選擇的進(jìn)行，解集合S不斷擴(kuò)展，直到構(gòu)成一個滿足問題的完整解。例如，在付款問題中，已付出的貨幣構(gòu)成解集合。（3）解決函數(shù)solution：檢查解集合S是否構(gòu)成問題的完整解。例如，在付款問題中，解決函數(shù)是已付出的貨幣金額恰好等于應(yīng)付款。（4）選擇函數(shù)select：即貪心策略，這是貪心法的關(guān)鍵，它指出哪個候選對象最有希望構(gòu)成問題的解，選擇函數(shù)通常和目
5、標(biāo)函數(shù)有關(guān)。例如，在付款問題中，貪心策略就是在候選集合中選擇面值最大的貨幣。（5）可行函數(shù)feasible：檢查解集合中加入一個候選對象是否可行，即解集合擴(kuò)展后是否滿足約束條件。例如，在付款問題中，可行函數(shù)是每一步選擇的貨幣和已付出的貨幣相加不超過應(yīng)付款。貪心法的一般過程Greedy(C)//C是問題的輸入集合即候選集合{S={};//初始解集合為空集while(notsolution(S))//集合S沒有構(gòu)成問題的一個解{x=select(C);//在候選集合C中做貪心選擇iffeasible(S,x)//判斷集合S中加入
6、x后的解是否可行S=S+{x};C=C-{x};}returnS;}7.2圖問題中的貪心法7.2.1TSP問題7.2.2圖著色問題7.2.3最小生成樹問題7.2.1TSP問題求解TSP問題至少有兩種貪心策略是合理的：（1）最近鄰點策略：從任意城市出發(fā)，每次在沒有到過的城市中選擇最近的一個，直到經(jīng)過了所有的城市，最后回到出發(fā)城市。(d)城市3→城市5(e)城市5→城市2(f)城市2→城市1最近鄰點貪心策略求解TSP問題的過程25221543225221543232522154327363215432233215432C=∞33
7、263∞73237∞25232∞36253∞(a)5城市的代價矩陣(b)城市1→城市4(c)城市4→城市3算法7.1——最近鄰點策略求解TSP問題1．P={};2．V=V-{u0};u=u0;//從頂點u0出發(fā)3．循環(huán)直到集合P中包含n-1條邊3.1查找與頂點u鄰接的最小代價邊(u,v)并且v屬于集合V；3.2P=P+{(u,v)};3.3V=V-{v};3.4u=v;//從頂點v出發(fā)繼續(xù)求解偽代碼設(shè)圖G有n個頂點，邊上的代價存儲在二維數(shù)組w[n][n]中，集合V存儲圖的頂點，集合P存儲經(jīng)過的邊，最近鄰點策略求解TSP問題的
8、算法如下：算法7.1的時間性能為O(n2)，因為共進(jìn)行n-1次貪心選擇，每一次選擇都需要查找滿足貪心條件的最短邊。用最近鄰點貪心策略求解TSP問題所得的結(jié)果不一定是最優(yōu)解，圖7.1(a)中從城市1出發(fā)的最優(yōu)解是1→2→5→4→3→1，總代價只有13。當(dāng)圖中頂點個數(shù)較多并且各邊的代價值分布比
