數(shù)據(jù)結(jié)構(gòu)電子科技第五章算法設(shè)計(jì)

數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)技術(shù)是密切相關(guān)的好的算法需要選擇適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)概括介紹算法設(shè)計(jì)策略分治法貪心法動(dòng)態(tài)規(guī)劃回溯法分支限界法

5.3分治法（DivideandConquer）

討論下面問題的求解方法Storethemaximumsumstartfromtheith(i=0,1,…,N-1)positiontothejth(j=i,…,N-1)positionfork(k=i,i+1,…,j)numbers.Maxsumis0ifalltheintegersarenegative.Tryyourbesttofindmoresolutionsandgiveoutthetimecomplexities.Algorithm1intMaxSubsequenceSum(constintA[],intN){ intThisSum,MaxSum,i,j,k;/*1*/ MaxSum=0;/*initializethemaximumsum*//*2*/

for(i=0;i<N;i++)/*startfromA[i]*//*3*/

for(j=i;j<N;j++){/*endatA[j]*//*4*/ ThisSum=0;/*5*/

for(k=i;k<=j;k++)/*6*/ ThisSum+=A[k];/*sumfromA[i]toA[j]*//*7*/

if(ThisSum>MaxSum)/*8*/ MaxSum=ThisSum;/*updatemaxsum*/ }/*endfor-jandfor-i*//*9*/

returnMaxSum;}T(N)=O(N3)Detailedanalysisisgivenonp.18-19.Storethemaximumsumstartfromtheith(i=0,1,…,N-1)positiontothejth(j=i,…,N-1)positionfork(k=i,i+1,…,j)numbers.Algorithm2§3ComparetheAlgorithmsintMaxSubsequenceSum(constintA[],intN){ intThisSum,MaxSum,i,j;/*1*/ MaxSum=0;/*initializethemaximumsum*//*2*/

for(i=0;i<N;i++){/*startfromA[i]*//*3*/ ThisSum=0;/*4*/

for(j=i;j<N;j++){/*endatA[j]*//*5*/ ThisSum+=A[j];/*sumfromA[i]toA[j]*//*6*/

if(ThisSum>MaxSum)/*7*/ MaxSum=ThisSum;/*updatemaxsum*/

}/*endfor-j*/ }/*endfor-i*//*8*/

returnMaxSum;}T(N)=O(N2)Improvement:storetheresultofandaddAjtothenewsumof§3ComparetheAlgorithmsAlgorithm3DivideandConquer43521262conquerdivide45626811T(N/2)T(N/2)O(N)T(N)=2T(N/2)+cN,T(1)=O(1)=2[2T(N/22)+cN/2]+cN=2kO(1)+ckNwhereN/2k=1=O(NlogN)AlsotrueforN

2kstaticintMaxSubSum(constintA[],intleft,intright){ intMaxLeftSum,MaxRightSum; intMaxLeftBorderSum,MaxRightBorderSum; intLeftBorderSum,RightBorderSum; intCenter,i; if(left==right) if(A[left]>0) returnA[left]; else return0; Center=(left+right)/2; MaxLeftSum=MaxSubSum(A,left,Center); MaxRightSum=MaxSumSum(A,Center+1,right);

MaxLeftBorderSum=0;LeftBorderSum=0; for(i=Center;i>=left;i--) { LeftBorderSum+=A[i]; if(LeftBorderSum>MaxLeftBorderSum) MaxLeftBorderSum=LeftBorderSum; } MaxRightBorderSum=0;RightBorderSum=0; for(i=Center+1;i<=Right;i++) { RightBorderSum+=A[i]; if(RightBorderSum>MaxRightBorderSum) MaxRightBorderSum=RightBorderSum; } returnMax3(MaxLeftSum,MaxRightSum, MaxLeftBorderSum+MaxRightBorderSum);§3ComparetheAlgorithmsAlgorithm4On-lineAlgorithm1324616113246Atanypointintime,MaxSubsequenceSum(constintA[],intN){ intThisSum,MaxSum,j;/*1*/ ThisSum=MaxSum=0;/*2*/

for(j=0;j<N;j++){/*3*/ ThisSum+=A[j];/*4*/

if(ThisSum>MaxSum)/*5*/ MaxSum=ThisSum;/*6*/

else

if(ThisSum<0)/*7*/ ThisSum=0; }/*endfor-j*//*8*/

returnMaxSum;}T(N)=O(N

)A[]isscannedonceonly.5.3.1分治法的基本思想任何一個(gè)可以用計(jì)算機(jī)求解的問題所需的計(jì)算時(shí)間都與其規(guī)模有關(guān)。問題的規(guī)模越小，越容易直接求解，解題所需的計(jì)算時(shí)間也越少。例如，對(duì)于n個(gè)元素的排序問題，當(dāng)n=1時(shí)，不需任何計(jì)算。n=2時(shí)，只要作一次比較即可排好序。n=3時(shí)只要作3次比較即可，…。而當(dāng)n較大時(shí)，問題就不那么容易處理了。要想直接解決一個(gè)規(guī)模較大的問題，有時(shí)是相當(dāng)困難的。5.3.1分治法的基本思想分治法的基本思想是：將一個(gè)難以直接解決的大問題，分割成一些規(guī)模較小的相同問題，以便各個(gè)擊破，分而治之。如果原問題可分割成k個(gè)子問題，1<k≤n，且這些子問題都可解，并可利用這些子問題的解求出原問題的解，那么這種分治法就是可行的。反復(fù)應(yīng)用分治手段，可以使子問題與原問題類型一致而其規(guī)模卻不斷縮小，最終使子問題縮小到很容易直接求出其解。分治法的求解過程：1.分解：將原問題分解為若干個(gè)規(guī)模較小，相互獨(dú)立，與原問題形式相同的子問題；2.求解：若子問題規(guī)模較小而容易被求解則直接解，否則遞歸地求解各個(gè)子問題；3.合并：將各個(gè)子問題的解合并為原問題的解。算法5.9分治法描述Return_typeDandC(objArrayA[],inti,intj){intm;if(small(A[],i,j)returnsolve(p,i,j);m=divide(A,i,j);Return(combine(DandC(A[],i,m),DandC(A[],m+1,j)));}分治法所能解決的問題一般具有以下幾個(gè)特征：1.該問題的規(guī)?？s小到一定的程度就可以容易地解決；2.該問題可以分解為若干個(gè)規(guī)模較小的相同問題；3.利用該問題分解出的子問題的解可以合并為該問題的解；4.該問題所分解出的各個(gè)子問題是相互獨(dú)立的，即子問題之間不包含公共的子問題。第一條特征是絕大多數(shù)問題都可以滿足的，因?yàn)閱栴}的計(jì)算復(fù)雜性一般是隨著問題規(guī)模的縮小而縮??；第二條特征是應(yīng)用分治法的前提，它也是大多數(shù)問題可以滿足的，此特征反映了遞歸思想的應(yīng)用；第三條特征是關(guān)鍵，能否利用分治法完全取決于問題是否具有第三條特征；第四條特征涉及到分治法的效率，如果各子問題是不獨(dú)立的，則分治法要做許多不必要的工作，重復(fù)地解公共的子問題。思考請(qǐng)同學(xué)們想出盡可能多的可以應(yīng)用分治法解決的問題及解決思路自學(xué):斯特拉森矩陣乘法（1969年提出，用加法代替乘法）二維數(shù)組在數(shù)值和非數(shù)值計(jì)算領(lǐng)域中是一種基本和重要的抽象數(shù)據(jù)結(jié)構(gòu)，矩陣是它的數(shù)學(xué)表示，因此改進(jìn)矩陣運(yùn)算的效率是非常重要的。矩陣A和B的乘積記為C=AB，C也是一個(gè)nn矩陣，C的第i行第j列的元素C（i,j）等于A的第i行和B的第j列對(duì)應(yīng)元素乘積的和，表示為按上面的公式計(jì)算C(i,j)需要做n次乘法和n-1次加法，而乘積矩陣C有n2個(gè)元素，所以，由矩陣乘定義直接產(chǎn)生的算法時(shí)間復(fù)雜度為Ο(n3)矩陣相乘過程中用到了大量的乘法運(yùn)算，而cpu中運(yùn)算單元對(duì)于乘法的效率遠(yuǎn)低于加法運(yùn)算，所以，如果能找到一種用加法來替代乘法的方法實(shí)現(xiàn)矩陣相乘，將能大大提高程序的效率。為得到兩個(gè)矩陣相乘的分治算法，需要：①分解：將一個(gè)乘法運(yùn)算分解為一些小問題②求解：如何求解這些小問題③合并：如何根據(jù)小問題的結(jié)果得到原問題的結(jié)果設(shè)A和B是兩個(gè)nn矩陣的矩陣，其中n可寫成2的冪。將A和B分別等分成4個(gè)小矩陣，此時(shí)如果把A和B都當(dāng)成22矩陣來看，它們的每個(gè)元素就是一個(gè)（n/2）（n/2）矩陣，而A與B的乘積就可以寫成其中為了降低時(shí)間復(fù)雜度，必須減少乘法的次數(shù)。而其關(guān)鍵在于計(jì)算2個(gè)2階方陣的乘積時(shí)所用乘法次數(shù)能否少于8次。為此，Strassen提出了一種只用7次乘法運(yùn)算計(jì)算2階方陣乘積的方法：矩陣m1～m7可以通過7次矩陣乘法、6次矩陣加法和4次矩陣減法計(jì)算得出。前述的4個(gè)小矩陣可以由矩陣m1~m7通過6次矩陣加法和2次矩陣減法得出，方法如下：用上述方案解決n=2的矩陣乘法。將如下矩陣A和B相乘得到結(jié)果C，如下所示：因?yàn)閚>1,所以將A,B矩陣分別劃分為4個(gè)小矩陣，每個(gè)矩陣為11階，僅包含一個(gè)元素。11階矩陣的乘法為小問題，因此可以直接進(jìn)行運(yùn)算，利用計(jì)算m1~m7的公式，得到：根據(jù)以上結(jié)果可得：對(duì)于上面這個(gè)22的例子，使用分而治之的算法需要7次乘法和18次加/減法運(yùn)算；而直接使用公式，則需要8次乘法和7次加/減法。如果要使分治法運(yùn)算快一些，則1次乘法所花費(fèi)的時(shí)間必須比11次加/減法的時(shí)間要長(zhǎng)。斯特拉森矩陣乘法的時(shí)間復(fù)雜度為：Hopcroft和Kerr已經(jīng)證明(1971)，計(jì)算2個(gè)２×２矩陣的乘積，7次乘法是必要的。因此，要想進(jìn)一步改進(jìn)矩陣乘法的時(shí)間復(fù)雜性，就不能再基于計(jì)算2×2矩陣的7次乘法這樣的方法了?；蛟S應(yīng)當(dāng)研究3×3或5×5矩陣的更好算法。

一般的為：在Strassen之后又有許多算法改進(jìn)了矩陣乘法的計(jì)算時(shí)間復(fù)雜性。

目前最好的計(jì)算時(shí)間上界是。是否能找到的算法？目前為止還沒有結(jié)果。5.4貪心法（greedymethod）顧名思義，貪心算法總是作出在當(dāng)前看來最好的選擇。通常用來求最優(yōu)化問題，其基本思想是：從問題的初始解出發(fā)，向求全局最優(yōu)解的目標(biāo)推進(jìn)，在推進(jìn)過程中的每一步都選擇局部最優(yōu)，希望通過一系列局部的最優(yōu)解來得到全局的最優(yōu)解。在有些應(yīng)用中，這些局部最優(yōu)可以得到全局最優(yōu)，如前面介紹的單源最短路經(jīng)、最小生成樹和哈夫曼編碼等算法。而在另外一些情況下，則無法得到全局最優(yōu)，這也是貪心法算法困難所在，即很困難證明通過一系列局部最優(yōu)得到的就是全局最優(yōu)。貪心法的優(yōu)點(diǎn)是每一步的工作很少，且基于少量的信息來逐步構(gòu)建可能的全局最優(yōu)解?？梢杂秘澬乃惴ㄇ蠼獾膯栴}一般具有2個(gè)重要的特性：貪心選擇特性和最優(yōu)子結(jié)構(gòu)特性。1.貪心選擇特性：指所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來達(dá)到。這是貪心算法可行的第一個(gè)基本要素。貪心算法則通常以自頂向下的方式進(jìn)行，以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問題簡(jiǎn)化為規(guī)模更小的子問題。對(duì)于一個(gè)具體問題，要確定它是否具有貪心選擇性質(zhì)，必須證明每一步所作的貪心選擇最終導(dǎo)致問題的整體最優(yōu)解2.最優(yōu)子結(jié)構(gòu)特性當(dāng)一個(gè)問題的最優(yōu)解包含其子問題的最優(yōu)解時(shí)，稱此問題具有最優(yōu)子結(jié)構(gòu)特性。問題的最優(yōu)子結(jié)構(gòu)特性是該問題可用貪心算法求解的關(guān)鍵特征。最優(yōu)化問題：存在著一組限制條件和一個(gè)優(yōu)化函數(shù)（目標(biāo)函數(shù)）符合限制條件的稱為可行解使優(yōu)化函數(shù)取得最佳值的可行解稱為最優(yōu)解貪心算法是求解最優(yōu)化問題的一種方法。5.4貪心法（greedymethod）貪心法首先是選取一種量度標(biāo)準(zhǔn)（優(yōu)化函數(shù)），每一次都按這種量度獲得局部最優(yōu)解。若下一個(gè)數(shù)據(jù)與部分最優(yōu)解連在一起不再是可行解時(shí)，就不把該數(shù)據(jù)添加到部分解中；直到把所有數(shù)據(jù)枚舉完，或者不能再添加為止。例如：Kruskal最小生成樹算法—貪心算法選取當(dāng)前權(quán)值最小邊，從邊集中刪除；（優(yōu)化函數(shù)）若屬不同連通分量，則加入到當(dāng)前最小生成樹T，得到一個(gè)局部最優(yōu)解；（限制條件）若屬于同一連通分量，形成回路，即不是可行解，舍掉貪心法具有多階段決策、無后向性與最優(yōu)化原理的特性。多階段決策：指解決問題過程可以分為若干階段，在每一個(gè)階段都做出相應(yīng)的決策，所有的決策構(gòu)成的決策序列就是問題的解決方案無后向性：指每一階段面臨的問題都是原問題的一個(gè)子問題，并且子問題的解決只與當(dāng)前階段和以后決策有關(guān)，與以前各階段的決策無關(guān)最優(yōu)化原理：指一個(gè)問題的最優(yōu)策略有這樣一個(gè)性質(zhì)，不論以前的決策如何，對(duì)于當(dāng)前的子問題，其余決策一定構(gòu)成最優(yōu)策略算法5.10貪心法的一般描述為：voidGreedy(A,n)/*{A[n]是n個(gè)輸入}*/{solution

空/*將解向量solution初始化為空*/for(i=0;i<n;i++){x=select(A);iffeasible(solution,x)union(solution,x);}returnsolution;}

貪心法解決問題的三個(gè)步驟：（1）分解：將原問題分解為若干相對(duì)獨(dú)立的階段；（2）解決：采用自頂向下的方法，對(duì)每一個(gè)階段求局部的最優(yōu)解；（3）合并：將各個(gè)階段的解合并為原問題的解。5.4.2背包問題給定n種物品和一個(gè)背包。物品i的重量是Wi，其價(jià)值為Vi，背包的容量為m。應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大？1.0-1背包問題：在選擇裝入背包的物品時(shí)，對(duì)每種物品i只有2種選擇，即裝入背包或不裝入背包。不能將物品i裝入背包多次，也不能只裝入部分的物品i。2.背包問題:在選擇物品i裝入背包時(shí)，可以選擇物品i的一部分，而不一定要全部裝入背包，1≤i≤n。這2類問題都具有最優(yōu)子結(jié)構(gòu)性質(zhì)，極為相似。但背包問題可以用貪心算法求解，而0-1背包問題卻不能用貪心算法求解。5.4.2背包問題已知容量大小為m的背包和n種物品，物品i的重量為wi，將物品i的一部分xi放入背包能得到收益為pixi，0xi1,pi>0。用怎樣的裝包方法才會(huì)使裝入背包物品的總效益最大？由于背包容量是m,因此，要求所有選中要裝入背包的物品總重量不能超過m。如果這n件物品的總重量不超過m，把所有物品裝入背包自然獲得最大效益。如果這些物品重量的和大于m，則在這種情況下該如何裝包？考慮下列情況下的背包問題：n=3,m=20,(p1,p2,p3)=(25,24,15),(w1,w2,w3)=(18,15,10)。其中的四個(gè)可行解是：(x1,x2,x3)①(1/2,1/3,1/4)16.524.25②(1,2/15,0)2028.2③(0,2/3,1)2031④(0,1,1/2)2031.5問題可以描述如下：但不是最優(yōu)解，背包還沒有裝滿，還可以裝入物體得到更大的價(jià)值。?。▁1,x2,x3）=（1/2,1/3,1/4）是一個(gè)可行解，因?yàn)椋?）用最大可能效益值增量作為度量標(biāo)準(zhǔn)按照效益值Pi的非增次序（降序）將物品一件件放到背包中。如果當(dāng)前選取的物品放不進(jìn)去，則可只取其一部分來裝滿背包。按最大pi的最大量裝對(duì)于求背包問題，有3個(gè)貪心策略（貪心選擇特性）可供選擇：例中：p1=25效益值最大,選物品1一件放入背包。獲得25的效益。W1=18，背包容量=20-18。物品2的效益值第二大(p2=24),w2=15,用x2=2/15正好裝滿背包，得到24×2/15=3.2收益。這樣裝入背包的物體的總效益為28.2，它是一個(gè)次優(yōu)解，由此可知，按物品效益值的非增次序裝包不能得到最優(yōu)解。（2）用背包容量作為度量標(biāo)準(zhǔn)讓背包容量盡可能慢地被消耗，這就要求按物品重量的非降次序（升序）來把物品放入背包。上例中，取x3=1,獲收益p3*x3=15;背包還剩余容量=20-10，裝入2/3的次重物體正好裝滿背包，獲收益p2*x2=242/3=16?？偸找?15+16=31，它仍是一個(gè)次優(yōu)解。原因在于背包容量雖然慢慢地被消耗，但效益增加也很慢。（3）單位容量的效益值作為度量標(biāo)準(zhǔn)考慮采用在效益值的增長(zhǎng)速率和容量的消耗速率之間取得平衡的度量標(biāo)準(zhǔn)，即每次裝入的物品應(yīng)使它占用的每一單位容量獲得當(dāng)前最大的單位效益。按照比值的pi/wi的非增次序來考慮。上例中，所以，選?。?，1，1/2）,總收益為：24+25*1/2=31.5(最大)，，

算法5.11背包問題最優(yōu)解的貪心算法floatgreedy-knapsack(float*p,float*w,float*m,float*x,float*n){/*p[n]和w[n]為按排序的n件物品的效益值和重量。

M是背包的容量大小，而x[n]是解向量*/inti;floatcu,sum=0;for(i=0;i<n;i++)x[i]=0;/*將解向量初始化為零*/cu=m;/*cu是背包剩余容量*/for(i=0;i<n;i++){ifw[i]>cubreak;

x[i]=1;

cu-=w[i];

sum+=p[i];

}if(i<n&&cu>0){

x[i]=cu/w[i];

sum+=p[i]*cu/w[i];

}return(sum);}活動(dòng)安排問題：在所給的活動(dòng)集合中選出最大的相容活動(dòng)子集合，該問題要求高效地安排一系列爭(zhēng)用某一公共資源的活動(dòng)。貪心算法提供了一個(gè)簡(jiǎn)單的方法使得盡可能多的活動(dòng)能兼容地使用公共資源。設(shè)有n個(gè)活動(dòng)的集合E={1,2,…,n}，其中每個(gè)活動(dòng)都要求使用同一資源，如演講會(huì)場(chǎng)等，而在同一時(shí)間內(nèi)只有一個(gè)活動(dòng)能使用這一資源。每個(gè)活動(dòng)i都有一個(gè)要求使用該資源的起始時(shí)間si和一個(gè)結(jié)束時(shí)間fi,且si<fi。如果選擇了活動(dòng)i，則它在半開時(shí)間區(qū)間[si,fi)內(nèi)占用資源。若區(qū)間[si,fi)與區(qū)間[sj,fj)不相交，則稱活動(dòng)i與活動(dòng)j是相容的。也就是說，當(dāng)si≥f