算法分析與設(shè)計(jì)[貪心法].ppt

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

1、第三章貪心方法什么是貪心方法背包問題帶有期限的作業(yè)排序最優(yōu)歸并模式最小生成樹單源點(diǎn)最短路徑3.1什么是貪心方法A(1)A(2)…A(n-1)A(n)某一問題的n個(gè)輸入B1(1)B1(2)…B1(m)該問題的一種解（可行解）是A的一個(gè)子集滿足一定的條件約束條件Bk(1)Bk(2)…Bk(m)…目標(biāo)函數(shù)取極值最優(yōu)解3.1什么是貪心方法根據(jù)題意，選取一種量度標(biāo)準(zhǔn)，然后按量度標(biāo)準(zhǔn)對(duì)n個(gè)輸入排序，按順序一次輸入一個(gè)量。如果這個(gè)輸入和當(dāng)前已構(gòu)成在這種量度意義下的部分最優(yōu)解加在一起不能產(chǎn)生一個(gè)可行解，則不把此輸入加到這部分解中，這種能夠得到某種量度意義下的最優(yōu)解的分級(jí)處理方法就是貪

2、心方法。量度標(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個(gè)輸入排序后的n個(gè)輸入A’(j)貪心方法的抽象化控制ProcedureGREEDY(A,n)solution?Фfori?1tondox?SELECT(A)ifFEASIBLE(solution,x)thensolution?UNION(solution,x)endifrepeatreturn(solution)EndGREEDY按某種最優(yōu)量度標(biāo)準(zhǔn)從A中選擇一個(gè)輸入賦給x，并從A中除去判斷x是否可以包含在解向量中將x與解向量合并并修改目標(biāo)函數(shù)

3、3.2背包問題問題描述已知有n種物品和一個(gè)可容納M重量的背包，每種物品i的重量為wi，假定將物品i的某一部分xi放入背包就會(huì)得到pixi的效益(0≤xi≤1,pi>0)，采用怎樣的裝包方法才會(huì)使裝入背包物品的總效益為最大呢？問題的形式描述極大化∑pixi約束條件∑wixi≤M0≤xi≤1,pi>0,wi>0,1≤i≤n1≤i≤n1≤i≤n目標(biāo)函數(shù)背包問題實(shí)例考慮下列情況的背包問題n=3,M=20,(p1,p2,p3)=(25,24,15),(w1,w2,w3)=(18,15,10)其中的4個(gè)可行解是：(x1,x2,x3)∑wixi∑pixi①(1/2,1/3,1/4)

4、16.524.25②(1,2/15,0)2028.2③(0,2/3,1)2031④(0,1,1/2)2031.5貪心方法的數(shù)據(jù)選擇策略(1)用貪心策略求解背包問題時(shí)，首先要選出最優(yōu)的度量標(biāo)準(zhǔn)?？梢赃x取目標(biāo)函數(shù)為量度標(biāo)準(zhǔn)，每裝入一件物品就使背包獲得最大可能的效益值增量。在這種量度標(biāo)準(zhǔn)下的貪心方法就是按效益值的非增次序?qū)⑽锲芬患诺奖嘲?。如上面的?shí)例所示，可將物品按效益量非增次序排序：(p1,p2,p3)=(25,24,15)。先裝入物品1重量為18，即x1=1；然后再裝物品2，由于約束條為∑wixi≤M=20，所以物品2只能裝入重量為2的一小部分，即x2=2/15。

5、貪心方法的數(shù)據(jù)選擇策略(2)按上述的數(shù)據(jù)選擇策略，裝入順序是按照物品的效益值從大到小的輸入，由剛才的方法可得這種情況下的總效益值為∑pixi=25+24*2/15=28.2，顯然是一個(gè)次優(yōu)解，原因是背包容量消耗過快。2.若以容量作為量度，可讓背包容量盡可能慢地被消耗。這就要求按物品重量的非降次序來把物品放入背包，即(w3,w2,w1)=(10,15,18)。貪心方法的數(shù)據(jù)選擇策略(2)先裝入物品3,x3=1,p3x3=15，再裝入重量為10的物品2，∑pixi=15+24*10/15=31。由剛才的方法可得這種情況下的總效益值為31，仍是一個(gè)次優(yōu)解，原因是容量在慢慢消

6、耗的過程中，效益值卻沒有迅速的增加。貪心方法的數(shù)據(jù)選擇策略(3)3.采用在效益值的增長(zhǎng)速率和容量的消耗速率之間取得平衡的量度標(biāo)準(zhǔn)。即每一次裝入的物品應(yīng)使它占用的每一單位容量獲得當(dāng)前最大的單位效益。這就需使物品的裝入次序按pi/wi比值的非增次序來考慮。這種策略下的量度是已裝入物品的累計(jì)效益值與所用容量之比。(p2/w2,p3/w3,p1/w1)=(24/15,15/10,25/18)。先裝入重量為15的物品2，在裝入重量為5的物品3，∑pixi=24+15*5/10=31.5。此結(jié)果為最優(yōu)解。背包問題的貪心算法ProcedureGREEDY-KNAPSACK(P,W,

7、M,X,n)realP(1:n),W(1:n),X(1:n),M,cu;integeri,n;X?0;cu?Mfori?1tondoifW(i)>cuthenexitendifX(i)?1;cu?cu-W(i)repeatifi≤nthenX(i)?cu/W(i)endifEndGREEDY-KNAPSACK將解向量X初始化為0Cu為背包的剩余容量只放物品i的一部分預(yù)先將物品按pi/wi比值的非增次序排序最優(yōu)解的證明基本思想把這個(gè)貪心解與任一最優(yōu)解相比較，如果這兩個(gè)解不同，就去找開始不同的第一個(gè)xi，然后設(shè)法用貪心解的這個(gè)xi去代換最優(yōu)解的那個(gè)xi，