四、貪心算法

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

1、2．3貪心法(GreedyApproach)一、基本思想適用問(wèn)題：組合優(yōu)化問(wèn)題，適合優(yōu)化原則。設(shè)計(jì)方法：多步判斷。在每步判斷時(shí)在滿足約束條件的情況下根據(jù)某個(gè)局部的優(yōu)化測(cè)度(可能是目標(biāo)函數(shù),也可能不是)考慮部分解中一個(gè)變量的選擇。使用貪心法要解決的問(wèn)題:是否可以得到最優(yōu)解?不能得到最優(yōu)解,解與最優(yōu)解的誤差估計(jì)。例1活動(dòng)選擇問(wèn)題S={1,2,…,n}為n項(xiàng)活動(dòng)的集合。si,fi分別為活動(dòng)i的開始和結(jié)束時(shí)間?；顒?dòng)i與j相容當(dāng)且僅當(dāng)si≥fj,或fi≥sj,求最大的兩兩相容的活動(dòng)集。解：按照結(jié)束時(shí)間的遞增順序?qū)⒒?/p>

2、動(dòng)排列為1,2,…,n,使得f1≤f2≤…≤fn算法GreedySelect1.n←length[S];2.A←{1};3.j←1;4.fori←2ton5.doifsi≥fj6.thenA←A∪{i};7.j←i;8.returnA.最后完成時(shí)間為max{fk:k∈A}.例如下述輸入I1234567891011si130535688212fi4567891011121314解為A={1,4,8,11}t=14下面證明貪心法得到最優(yōu)解。定理1算法Select執(zhí)行到第k步,選擇k項(xiàng)活動(dòng)i1=1,i2,…,i

3、k,那么存在最優(yōu)解A包含i1=1,i2,…,ik證明：對(duì)k歸納。k=1,設(shè)S={1,2,…,n}是活動(dòng)集，活動(dòng)按截止時(shí)間遞增順序排序，則存在最優(yōu)解含有活動(dòng)1。任取最優(yōu)解A,A中的活動(dòng)按照截止時(shí)間遞增的順序排列。如果A的第一個(gè)活動(dòng)為j，j≠1,令A(yù)’=(A?{j})∪{1},由于f1≤fj,A’也是最優(yōu)解，且含有1.假設(shè)命題對(duì)k為真。算法執(zhí)行到第k步,選擇了活動(dòng)i1=1,i2,…,ik,根據(jù)歸納假設(shè)存在最優(yōu)解A包含i1=1,i2,…,ik,A中剩下的活動(dòng)選自集合S’={i

4、i∈S,si≥fk}。且B=A-{

5、i1,i2,…,ik}是S’的最優(yōu)解。若不然，S’的最優(yōu)解為B’，B’的活動(dòng)比B多，那么B’∪{1,i2,…,ik}是S的最優(yōu)解，且比A的活動(dòng)多，與A的最優(yōu)性矛盾。根據(jù)歸納基礎(chǔ)，存在S’的最優(yōu)解B含有S’中的第一個(gè)活動(dòng)，設(shè)為ik+1,則{i,i,...,i}∪B={i,i,...i,i}∪(B?{i})12k12kk+1k+1包含了算法k+1步的選擇，也是原問(wèn)題的最優(yōu)解，命題對(duì)k+1為真。二、貪心算法的設(shè)計(jì)：1.貪心算法的設(shè)計(jì)要素z適用于滿足優(yōu)化原則的組合優(yōu)化問(wèn)題，將問(wèn)題表示成多步判斷。整個(gè)判斷序列對(duì)應(yīng)問(wèn)

6、題的最優(yōu)解；而它的子序列對(duì)應(yīng)子問(wèn)題的最優(yōu)解。z確定一個(gè)優(yōu)化測(cè)度（不考慮以前各步的選擇，只與當(dāng)前狀態(tài)有關(guān)），以優(yōu)化測(cè)度的極大(或極小)作為貪心選擇的依據(jù)z確定是否滿足貪心選擇性質(zhì)——每步貪心選擇都導(dǎo)致最優(yōu)解。一般采用歸納法加以證明z自頂向下計(jì)算，通過(guò)貪心選擇，將原問(wèn)題規(guī)約為子問(wèn)題。動(dòng)態(tài)規(guī)劃和貪心法比較：性質(zhì)動(dòng)態(tài)規(guī)劃貪心法適用問(wèn)題組合優(yōu)化組合優(yōu)化求解過(guò)程多步判斷多步判斷使用條件優(yōu)化原則優(yōu)化原則解的性質(zhì)最優(yōu)解有貪心選擇性質(zhì)下得到最優(yōu)解否則為近似解求解關(guān)鍵列遞推方程貪心選擇性質(zhì)的證明子問(wèn)題形成先解子問(wèn)題然后選擇先

7、選擇然后構(gòu)成子問(wèn)題求解順序自底向上自頂向下數(shù)據(jù)結(jié)構(gòu)數(shù)值表記錄優(yōu)化函數(shù)值無(wú)特殊要求標(biāo)記表記錄子問(wèn)題劃分時(shí)間復(fù)雜性依賴子問(wèn)題重疊程度不高空間復(fù)雜性高不高2．貪心算法的正確性證明不是所有優(yōu)化問(wèn)題都具有貪心選擇性質(zhì)，證明貪心選擇性質(zhì)的方法---數(shù)學(xué)歸納法，可以對(duì)算法步數(shù)或問(wèn)題規(guī)模進(jìn)行歸納。例2部分裝入背包問(wèn)題(FractionalKnapsackProblem)一個(gè)旅行者準(zhǔn)備隨身攜帶一個(gè)背包.可以放入背包的物品有n個(gè),每個(gè)物品的重量和價(jià)值分別為wj,vj.j=1,2,…,n,旅行者可以選擇物品i的全部，也可以選擇

8、物品i的xi部分，0≤xi≤1。如果背包的最大重量限制是c,怎樣選擇放入背包的物品以使得背包的價(jià)值最大?輸入：c>0,wi>0,vi>0,i=1,…n.輸出：nmax∑vixii=1n∑wixi≤ci=10≤x≤1i=1,2,...,ni設(shè)計(jì)貪心法如下：按照單位重量的價(jià)值從高到低對(duì)物品排序，盡量裝入單位重量?jī)r(jià)值最高的物品，直到不能裝入一個(gè)整物品為止，最后根據(jù)背包重量極限裝入部分物品。通過(guò)對(duì)步數(shù)歸納可以證明部分裝入背包問(wèn)題滿足貪心選擇性質(zhì)，且時(shí)間為T(n)=O(nlogn)。一般背包

9、問(wèn)題不具有貪心選擇性質(zhì)，不能使用貪心法，因?yàn)閷?duì)于某些輸入不能得到最優(yōu)解。0-1背包問(wèn)題也不具有貪心選擇性質(zhì)。下面是0-1背包問(wèn)題的描述。nmax∑vixii=1n∑wixi≤ci=1x=0,1,i=1,2,...,ni例3最優(yōu)裝載n個(gè)集裝箱1,2,…,n裝上輪船，集裝箱i的重量wi,輪船裝載重量限制為c，無(wú)體積限制。問(wèn)如何裝使得上船的集裝箱最多？不妨設(shè)wi≤c.nmax∑xii=1n∑wixi≤ci=1x=0,1i=1,2,.