算法分析與設(shè)計[4].ppt

《算法分析與設(shè)計[4].ppt》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、第四章貪心方法什么是貪心方法背包問題單源點最短路徑最優(yōu)歸并模式活動安排問題實例:找硬幣假設(shè)有三種硬幣,面值分別為5分,2分和1分,給顧客找零錢時希望拿出的硬幣個數(shù)最少找零1角2分:2個5分,1個2分2個5分,2個1分6個2分找零算法:先找出一個面值不超過1角2分的最大硬幣(5分)從1角2分中減去5分,剩7分再找出一個面值不超過7分的最大硬幣(5分)從7分中減去5分,剩2分最后找出一個面值不超過2分的最大硬幣(2分)貪心算法的思想:貪心算法總是作出在當(dāng)前看來最好的選擇。貪心算法并不從整體最優(yōu)考慮,因

2、此它所作出的選擇是在某種意義上的局部最優(yōu)選擇貪心算法通常包含一個用以尋找局部最優(yōu)解的迭代過程對于某些實例,這些局部最優(yōu)解轉(zhuǎn)變?yōu)槿肿顑?yōu)解而對于另外一些實例,貪心算法不能找到全局最優(yōu)解貪心算法求解問題的速度比較快,因為算法的每一步都是在少量信息的基礎(chǔ)上考慮局部最優(yōu)解,這樣使得每一步的計算量比較小,所以算法效率比較高4.1什么是貪心方法A(1)A(2)…A(n-1)A(n)某一問題的n個輸入B1(1)B1(2)…B1(m)該問題的一種解（可行解）是A的一個子集滿足一定的條件約束條件Bk(1)Bk(2)

3、…Bk(m)…目標(biāo)函數(shù)取極值最優(yōu)解4.1什么是貪心方法根據(jù)題意，選取一種量度標(biāo)準(zhǔn)，然后按量度標(biāo)準(zhǔn)對n個輸入排序，按順序一次輸入一個量。如果這個輸入和當(dāng)前已構(gòu)成在這種量度意義下的部分最優(yōu)解加在一起不能產(chǎn)生一個可行解，則不把此輸入加到這部分解中，這種能夠得到某種量度意義下的最優(yōu)解的分級處理方法就是貪心方法。量度標(biāo)準(zhǔn)A(1)A(2)…A(n)A’(1)A’(2)…A’(n)S(1)S(2)…量度標(biāo)準(zhǔn)意義下的部分最優(yōu)解原問題的n個輸入排序后的n個輸入A’(j)貪心方法的抽象化控制int*GREEDY(in

4、t*A,intn){solution=Ф;for(i=1;i<=n;i++){x=SELECT(A)if(FEASIBLE(solution,x)==1)solution=UNION(solution,x);}return(solution);}按某種最優(yōu)量度標(biāo)準(zhǔn)從集合A中選擇一個輸入賦給x，并從A中除去判斷x是否可以包含在解向量中將x與解集合合并并修改目標(biāo)函數(shù)4.1背包問題的貪心算法問題描述已知有n種物品和一個可容納M重量的背包，每種物品i的重量為wi，假定將物品i的某一部分xi放入背包就會得到

5、pixi的效益(0≤xi≤1,pi>0)，采用怎樣的裝包方法才會使裝入背包物品的總效益為最大呢？問題的形式描述極大化∑pixi約束條件∑wixi≤M0≤xi≤1,pi>0,wi>0,1≤i≤n1≤i≤n1≤i≤n目標(biāo)函數(shù)背包問題實例(x1,x2,x3)∑wixi∑vixi①(1,2/15,0)2028.2②(1,0,1/5)2028③(0,2/3,1)2031④(0,1,1/2)2031.5其中的4個可行解：有3個物品,即n=3,背包能容納的最大重量為20,即c=20物品的價值和重量:(v1,v2

6、,v3)=(25,24,15),(w1,w2,w3)=(18,15,10)最優(yōu)解貪心算法求解背包問題確定貪心選擇策略①選擇價值高的物品放入背包將物品按價值的降序排列:(v1,v2,v3)=(25,24,15)按該次序?qū)⑽锲芬患诺奖嘲?先裝物品1,即x1=1,w1=18,v1x1=25;再裝物品2,因約束條件為∑wixi≤c=20,所以物品2只能裝入重量為2的一小部分,即x2=2/15;最后得到總價值為∑vixi=25+24*2/15=28.2實例：n=3,c=20(v1,v2,v3)=(25

7、,24,15)(w1,w2,w3)=(18,15,10)這是一個次優(yōu)解，原因是背包容量消耗的過快確定貪心選擇策略②選擇重量輕的物品放入背包將物品按重量的升序排列:(w3,w2,w1)=(10,15,18)按該次序?qū)⑽锲贩诺奖嘲?讓容量盡可能慢的被消耗先裝物品3,即x3=1,w3=10,v3x3=15;再裝入物品2,因約束條件為∑wixi≤c=20,所以物品2只能裝入重量為10的一部分,即x2=10/15=2/3;最后得到總價值為∑vixi=15+24*2/3=31這仍是一個次優(yōu)解,原因是容量在慢

8、慢消耗的過程中,效益值卻沒有迅速的增加實例：n=3,c=20(v1,v2,v3)=(25,24,15)(w1,w2,w3)=(18,15,10)③選擇單位重量價值高的物品放入背包將物品按vi/wi比值的降序排列:(v2/w2,v3/w3,v1/w1)=(24/15,15/10,25/18)即每一次裝入的物品使它占用的單位重量獲得當(dāng)前最大的單位價值先裝入物品2,即x2=1,w2=15,v2x2=24;再裝入物品3,因約束條件為∑wixi≤c=20,所以物品3只能裝入重量為5的一部分,