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

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

1、第7章貪心法7.1概述7.2圖問(wèn)題中的貪心法7.3組合問(wèn)題中的貪心法8/4/20211算法設(shè)計(jì)與分析--貪心法7.1概述7.1.1貪心法的設(shè)計(jì)思想7.1.2貪心法的求解過(guò)程8/4/20212算法設(shè)計(jì)與分析--貪心法貪心法只根據(jù)當(dāng)前已有的信息就做出選擇，而且一旦做出了選擇，不管將來(lái)有什么結(jié)果，這個(gè)選擇都不會(huì)改變。7.1.1貪心法的設(shè)計(jì)思想換言之，貪心法并不是從整體最優(yōu)考慮，它所做出的選擇只是在某種意義上的局部最優(yōu)。這種局部最優(yōu)選擇并不總能獲得整體最優(yōu)解（OptimalSolution），但通常能獲得近似最優(yōu)解（Near-OptimalSolution）。8/4/20213算法設(shè)計(jì)與

2、分析--貪心法例：用貪心法求解付款問(wèn)題。假設(shè)有面值為5元、2元、1元、5角、2角、1角的貨幣，需要找給顧客4元6角現(xiàn)金，為使付出的貨幣的數(shù)量最少，首先選出1張面值不超過(guò)4元6角的最大面值的貨幣，即2元，再選出1張面值不超過(guò)2元6角的最大面值的貨幣，即2元，再選出1張面值不超過(guò)6角的最大面值的貨幣，即5角，再選出1張面值不超過(guò)1角的最大面值的貨幣，即1角，總共付出4張貨幣。面值改為3元、1元、8角、5角、1角的貨幣如何?8/4/20214算法設(shè)計(jì)與分析--貪心法在付款問(wèn)題每一步的貪心選擇中，在不超過(guò)應(yīng)付款金額的條件下，只選擇面值最大的貨幣，而不去考慮在后面看來(lái)這種選擇是否合理，而且

3、它還不會(huì)改變決定：一旦選出了一張貨幣，就永遠(yuǎn)選定。付款問(wèn)題的貪心選擇策略是盡可能使付出的貨幣最快地滿足支付要求，其目的是使付出的貨幣張數(shù)最慢地增加，這正體現(xiàn)了貪心法的設(shè)計(jì)思想。8/4/20215算法設(shè)計(jì)與分析--貪心法貪心法求解的問(wèn)題的特征：動(dòng)態(tài)規(guī)劃法通常以自底向上的方式求解各個(gè)子問(wèn)題，而貪心法則通常以自頂向下的方式做出一系列的貪心選擇。（1）最優(yōu)子結(jié)構(gòu)性質(zhì)當(dāng)一個(gè)問(wèn)題的最優(yōu)解包含其子問(wèn)題的最優(yōu)解時(shí)，稱此問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，也稱此問(wèn)題滿足最優(yōu)性原理。（2）貪心選擇性質(zhì)所謂貪心選擇性質(zhì)是指問(wèn)題的整體最優(yōu)解可以通過(guò)一系列局部最優(yōu)的選擇，即貪心選擇來(lái)得到。8/4/20216算法設(shè)計(jì)與

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

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

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

7、解TSP問(wèn)題的過(guò)程25221543225221543232522154327363215432233215432C=∞33263∞73237∞25232∞36253∞(a)5城市的代價(jià)矩陣(b)城市1→城市4(c)城市4→城市38/4/202112算法設(shè)計(jì)與分析--貪心法算法7.1——最近鄰點(diǎn)策略求解TSP問(wèn)題1．P={};2．V=V-{u0};u=u0;//從頂點(diǎn)u0出發(fā)3．循環(huán)直到集合P中包含n-1條邊3.1查找與頂點(diǎn)u鄰接的最小代價(jià)邊(u,v)并且v屬于集合V；3.2P=P