天津科技大學(xué)算法設(shè)計與分析第7章貪心法

《天津科技大學(xué)算法設(shè)計與分析第7章貪心法》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、第7章貪心法7.1概述7.2圖問題中的貪心法7.3組合問題中的貪心法8/4/20211算法設(shè)計與分析--貪心法7.1概述7.1.1貪心法的設(shè)計思想7.1.2貪心法的求解過程8/4/20212算法設(shè)計與分析--貪心法貪心法只根據(jù)當(dāng)前已有的信息就做出選擇，而且一旦做出了選擇，不管將來有什么結(jié)果，這個選擇都不會改變。7.1.1貪心法的設(shè)計思想換言之，貪心法并不是從整體最優(yōu)考慮，它所做出的選擇只是在某種意義上的局部最優(yōu)。這種局部最優(yōu)選擇并不總能獲得整體最優(yōu)解（OptimalSolution），但通常能獲得近似最優(yōu)解（Near-OptimalSolution）。8/4/20213算法設(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張貨幣。面值改為3元、1元、8角、5角、1角的貨幣如何?8/4/20214算法設(shè)計與分析--貪心法在付款問題每一步的貪心選擇中，在不超過應(yīng)付款金額的條件下，只選擇面值最大的貨幣，而不去考慮在后面看來這種選擇是否合理，而且

3、它還不會改變決定：一旦選出了一張貨幣，就永遠(yuǎn)選定。付款問題的貪心選擇策略是盡可能使付出的貨幣最快地滿足支付要求，其目的是使付出的貨幣張數(shù)最慢地增加，這正體現(xiàn)了貪心法的設(shè)計思想。8/4/20215算法設(shè)計與分析--貪心法貪心法求解的問題的特征：動態(tài)規(guī)劃法通常以自底向上的方式求解各個子問題，而貪心法則通常以自頂向下的方式做出一系列的貪心選擇。（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)的選擇，即貪心選擇來得到。8/4/20216算法設(shè)計與

4、分析--貪心法7.1.2貪心法的求解過程用貪心法求解問題應(yīng)該考慮如下幾個方面：（1）候選集合C：為了構(gòu)造問題的解決方案，有一個候選集合C作為問題的可能解，即問題的最終解均取自于候選集合C。例如，在付款問題中，各種面值的貨幣構(gòu)成候選集合。（2）解集合S：隨著貪心選擇的進行，解集合S不斷擴展，直到構(gòu)成一個滿足問題的完整解。例如，在付款問題中，已付出的貨幣構(gòu)成解集合。8/4/20217算法設(shè)計與分析--貪心法（3）解決函數(shù)solution：檢查解集合S是否構(gòu)成問題的完整解。例如，在付款問題中，解決函數(shù)是已付出的貨幣金額恰好等于應(yīng)付款。（4）選擇函數(shù)select：即貪心策略，這是貪心法的

5、關(guān)鍵，它指出哪個候選對象最有希望構(gòu)成問題的解，選擇函數(shù)通常和目標(biāo)函數(shù)有關(guān)。例如，在付款問題中，貪心策略就是在候選集合中選擇面值最大的貨幣。（5）可行函數(shù)feasible：檢查解集合中加入一個候選對象是否可行，即解集合擴展后是否滿足約束條件。例如，在付款問題中，可行函數(shù)是每一步選擇的貨幣和已付出的貨幣相加不超過應(yīng)付款。8/4/20218算法設(shè)計與分析--貪心法貪心法的一般過程Greedy(C)//C是問題的輸入集合即候選集合{S={};//初始解集合為空集while(notsolution(S))//集合S沒有構(gòu)成問題的一個解{x=select(C);//在候選集合C中做貪心選擇i

6、ffeasible(S,x)//判斷集合S中加入x后的解是否可行S=S+{x};C=C-{x};}returnS;}8/4/20219算法設(shè)計與分析--貪心法7.2圖問題中的貪心法7.2.1TSP問題7.2.2圖著色問題7.2.3最小生成樹問題8/4/202110算法設(shè)計與分析--貪心法7.2.1TSP問題求解TSP問題至少有兩種貪心策略是合理的：（1）最近鄰點策略：從任意城市出發(fā)，每次在沒有到過的城市中選擇最近的一個，直到經(jīng)過了所有的城市，最后回到出發(fā)城市。8/4/202111算法設(shè)計與分析--貪心法(d)城市3→城市5(e)城市5→城市2(f)城市2→城市1最近鄰點貪心策略求

7、解TSP問題的過程25221543225221543232522154327363215432233215432C=∞33263∞73237∞25232∞36253∞(a)5城市的代價矩陣(b)城市1→城市4(c)城市4→城市38/4/202112算法設(shè)計與分析--貪心法算法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