資源描述：
《四、貪心算法》由會員上傳分享，免費在線閱讀，更多相關內容在教育資源-天天文庫。
1、2．3貪心法(GreedyApproach)一、基本思想適用問題：組合優(yōu)化問題，適合優(yōu)化原則。設計方法：多步判斷。在每步判斷時在滿足約束條件的情況下根據某個局部的優(yōu)化測度(可能是目標函數,也可能不是)考慮部分解中一個變量的選擇。使用貪心法要解決的問題:是否可以得到最優(yōu)解?不能得到最優(yōu)解,解與最優(yōu)解的誤差估計。例1活動選擇問題S={1,2,…,n}為n項活動的集合。si,fi分別為活動i的開始和結束時間。活動i與j相容當且僅當si≥fj,或fi≥sj,求最大的兩兩相容的活動集。解：按照結束時間的遞增順序將活
2、動排列為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.最后完成時間為max{fk:k∈A}.例如下述輸入I1234567891011si130535688212fi4567891011121314解為A={1,4,8,11}t=14下面證明貪心法得到最優(yōu)解。定理1算法Select執(zhí)行到第k步,選擇k項活動i1=1,i2,…,i
3、k,那么存在最優(yōu)解A包含i1=1,i2,…,ik證明：對k歸納。k=1,設S={1,2,…,n}是活動集，活動按截止時間遞增順序排序，則存在最優(yōu)解含有活動1。任取最優(yōu)解A,A中的活動按照截止時間遞增的順序排列。如果A的第一個活動為j，j≠1,令A’=(A?{j})∪{1},由于f1≤fj,A’也是最優(yōu)解，且含有1.假設命題對k為真。算法執(zhí)行到第k步,選擇了活動i1=1,i2,…,ik,根據歸納假設存在最優(yōu)解A包含i1=1,i2,…,ik,A中剩下的活動選自集合S’={i
4、i∈S,si≥fk}。且B=A-{
5、i1,i2,…,ik}是S’的最優(yōu)解。若不然，S’的最優(yōu)解為B’，B’的活動比B多，那么B’∪{1,i2,…,ik}是S的最優(yōu)解，且比A的活動多，與A的最優(yōu)性矛盾。根據歸納基礎，存在S’的最優(yōu)解B含有S’中的第一個活動，設為ik+1,則{i,i,...,i}∪B={i,i,...i,i}∪(B?{i})12k12kk+1k+1包含了算法k+1步的選擇，也是原問題的最優(yōu)解，命題對k+1為真。二、貪心算法的設計：1.貪心算法的設計要素z適用于滿足優(yōu)化原則的組合優(yōu)化問題，將問題表示成多步判斷。整個判斷序列對應問
6、題的最優(yōu)解；而它的子序列對應子問題的最優(yōu)解。z確定一個優(yōu)化測度（不考慮以前各步的選擇，只與當前狀態(tài)有關），以優(yōu)化測度的極大(或極小)作為貪心選擇的依據z確定是否滿足貪心選擇性質——每步貪心選擇都導致最優(yōu)解。一般采用歸納法加以證明z自頂向下計算，通過貪心選擇，將原問題規(guī)約為子問題。動態(tài)規(guī)劃和貪心法比較：性質動態(tài)規(guī)劃貪心法適用問題組合優(yōu)化組合優(yōu)化求解過程多步判斷多步判斷使用條件優(yōu)化原則優(yōu)化原則解的性質最優(yōu)解有貪心選擇性質下得到最優(yōu)解否則為近似解求解關鍵列遞推方程貪心選擇性質的證明子問題形成先解子問題然后選擇先
7、選擇然后構成子問題求解順序自底向上自頂向下數據結構數值表記錄優(yōu)化函數值無特殊要求標記表記錄子問題劃分時間復雜性依賴子問題重疊程度不高空間復雜性高不高2．貪心算法的正確性證明不是所有優(yōu)化問題都具有貪心選擇性質，證明貪心選擇性質的方法---數學歸納法，可以對算法步數或問題規(guī)模進行歸納。例2部分裝入背包問題(FractionalKnapsackProblem)一個旅行者準備隨身攜帶一個背包.可以放入背包的物品有n個,每個物品的重量和價值分別為wj,vj.j=1,2,…,n,旅行者可以選擇物品i的全部，也可以選擇
8、物品i的xi部分，0≤xi≤1。如果背包的最大重量限制是c,怎樣選擇放入背包的物品以使得背包的價值最大?輸入：c>0,wi>0,vi>0,i=1,…n.輸出：nmax∑vixii=1n∑wixi≤ci=10≤x≤1i=1,2,...,ni設計貪心法如下：按照單位重量的價值從高到低對物品排序，盡量裝入單位重量價值最高的物品，直到不能裝入一個整物品為止，最后根據背包重量極限裝入部分物品。通過對步數歸納可以證明部分裝入背包問題滿足貪心選擇性質，且時間為T(n)=O(nlogn)。一般背包
9、問題不具有貪心選擇性質，不能使用貪心法，因為對于某些輸入不能得到最優(yōu)解。0-1背包問題也不具有貪心選擇性質。下面是0-1背包問題的描述。nmax∑vixii=1n∑wixi≤ci=1x=0,1,i=1,2,...,ni例3最優(yōu)裝載n個集裝箱1,2,…,n裝上輪船，集裝箱i的重量wi,輪船裝載重量限制為c，無體積限制。問如何裝使得上船的集裝箱最多？不妨設wi≤c.nmax∑xii=1n∑wixi≤ci=1x=0,1i=1,2,.
