計(jì)算機(jī)算法設(shè)計(jì)與分析第1頁(yè)1.1算法定義和特征1)什么是算法？

算法是求解某一特定問(wèn)題一組有窮規(guī)則集合，它是由若干條指令組成有窮符號(hào)串。2）

算法五個(gè)主要特征

確定性、可實(shí)現(xiàn)性、輸入、輸出、有窮性3）

算法設(shè)計(jì)質(zhì)量指標(biāo)

正確性，可讀性，健壯性，效率與存放量第2頁(yè)算法和程序區(qū)分程序：一個(gè)計(jì)算機(jī)程序是對(duì)一個(gè)算法使用某種程序設(shè)計(jì)語(yǔ)言詳細(xì)實(shí)現(xiàn)任何一個(gè)程序設(shè)計(jì)語(yǔ)言都能夠?qū)崿F(xiàn)任何一個(gè)算法算法有窮性意味著不是全部計(jì)算機(jī)程序都是算法第3頁(yè)問(wèn)題求解(ProblemSolving)證實(shí)正確性分析算法設(shè)計(jì)程序了解問(wèn)題準(zhǔn)確解或近似解選擇數(shù)據(jù)結(jié)構(gòu)算法設(shè)計(jì)策略設(shè)計(jì)算法第4頁(yè)

普通只考慮三種情況下時(shí)間性:最壞情況、最好情況和平均情況下復(fù)雜性，分別記為Tmax(n)、Tmin(n)和Tavg(n)算法復(fù)雜性=算法所需要計(jì)算機(jī)資源=時(shí)間復(fù)雜性+空間復(fù)雜性第5頁(yè)算法漸近復(fù)雜性第6頁(yè)1）上界函數(shù)定義1假如存在兩個(gè)正常數(shù)c和n0，對(duì)于全部n≥n0，有|f(n)|≤c|g(n)|則記作f(n)=Ο(g(n))含義：假如算法用n值不變同一類數(shù)據(jù)在某臺(tái)機(jī)器上運(yùn)行時(shí)，所用時(shí)間總是小于|g(n)|一個(gè)常數(shù)倍。所以g(n)是計(jì)算時(shí)間f(n)一個(gè)上界函數(shù)。f(n)數(shù)量級(jí)就是g(n)。f(n)增加最多像g(n)增加那樣快試圖求出最小g(n)，使得f(n)=Ο(g(n))。第7頁(yè)第8頁(yè)算法分類（計(jì)算時(shí)間）多項(xiàng)式時(shí)間算法：可用多項(xiàng)式（函數(shù)）對(duì)其計(jì)算時(shí)間限界算法。

常見(jiàn)多項(xiàng)式限界函數(shù)有：

Ο(1)<Ο(logn)<Ο(n)<Ο(nlogn)<Ο(n2)<Ο(n3)指數(shù)時(shí)間算法：計(jì)算時(shí)間用指數(shù)函數(shù)限界算法。

常見(jiàn)指數(shù)時(shí)間限界函數(shù)：

Ο(2n)<Ο(n！)<Ο(nn)說(shuō)明：當(dāng)n取值較大時(shí)，指數(shù)時(shí)間算法和多項(xiàng)式時(shí)間算法在計(jì)算時(shí)間上非常懸殊。第9頁(yè)經(jīng)典計(jì)算時(shí)間函數(shù)曲線第10頁(yè)定義1.2假如存在兩個(gè)正常數(shù)c和n0，對(duì)于全部n≥n0，有|f(n)|≥c|g(n)|則記作f(n)=Ω(g(n))含義：假如算法用n值不變同一類數(shù)據(jù)在某臺(tái)機(jī)器上運(yùn)行時(shí)，所用時(shí)間總是大于|g(n)|一個(gè)常數(shù)倍。所以g(n)是計(jì)算時(shí)間f(n)一個(gè)下界函數(shù)。f(n)增加最少像g(n)增加那樣快試圖求出“最大”g(n)，使得f(n)=Ω(g(n))。2）下界函數(shù)第11頁(yè)定義1.3假如存在正常數(shù)c1，c2和n0，對(duì)于全部n≥n0，有c1|g(n)|≤|f(n)|≤c2|g(n)|則記作含義：算法在最好和最壞情況下計(jì)算時(shí)間就一個(gè)常數(shù)因子范圍內(nèi)而言是相同。可看作：現(xiàn)有f(n)=Ω(g(n))，又有f(n)=Ο(g(n))記號(hào)表明算法運(yùn)行時(shí)間有一個(gè)較準(zhǔn)確界3）“平均情況”限界函數(shù)第12頁(yè)最優(yōu)算法問(wèn)題計(jì)算時(shí)間下界為(f(n))，則計(jì)算時(shí)間復(fù)雜性為O(f(n))算法是最優(yōu)算法。比如，排序問(wèn)題計(jì)算時(shí)間下界為(nlogn)，計(jì)算時(shí)間復(fù)雜性為O(nlogn)排序算法是最優(yōu)算法。第13頁(yè)第2章遞歸與分治策略第14頁(yè)2.1遞歸概念直接或間接地調(diào)用本身算法稱為遞歸算法。函數(shù)本身給出定義函數(shù)稱為遞歸函數(shù)。

基于歸納法遞歸基于分治法遞歸第15頁(yè)2.1遞歸概念例Fibonacci數(shù)列無(wú)窮數(shù)列1，1，2，3，5，8，13，21，34，55，……，稱為Fibonacci數(shù)列。它能夠遞歸地定義為：邊界條件遞歸方程第n個(gè)Fibonacci數(shù)可遞歸地計(jì)算以下：intfibonacci(intn){

if(n<=1)return1;

return

fibonacci(n-1)+fibonacci(n-2);}第16頁(yè)分治算法總體思想分治法設(shè)計(jì)思想是，將一個(gè)難以直接處理大問(wèn)題，分割成一些規(guī)模較小相同問(wèn)題，方便各個(gè)擊破，分而治之。

第17頁(yè)分治法適用條件分治法所能處理問(wèn)題普通含有以下幾個(gè)特征：該問(wèn)題規(guī)模縮小到一定程度就能夠輕易地處理；該問(wèn)題能夠分解為若干個(gè)規(guī)模較小相同問(wèn)題，即該問(wèn)題含有最優(yōu)子結(jié)構(gòu)性質(zhì)利用該問(wèn)題分解出子問(wèn)題解能夠合并為該問(wèn)題解；該問(wèn)題所分解出各個(gè)子問(wèn)題是相互獨(dú)立，即子問(wèn)題之間不包含公共子問(wèn)題。第18頁(yè)分治法基本步驟

（1）分解：將原問(wèn)題分解為若干個(gè)規(guī)模較小，相互獨(dú)立，與原問(wèn)題形式相同子問(wèn)題；

（2）處理：若子問(wèn)題規(guī)模較小而輕易被處理則直接解，不然遞歸地解各個(gè)子問(wèn)題；

（3）合并：將各個(gè)子問(wèn)題解合并為原問(wèn)題解。第19頁(yè)分治法復(fù)雜性分析一個(gè)分治法將規(guī)模為n問(wèn)題分成k個(gè)規(guī)模為n／k子問(wèn)題去解。設(shè)分解閥值n0=1，且adhoc解規(guī)模為1問(wèn)題花費(fèi)1個(gè)單位時(shí)間。再設(shè)將原問(wèn)題分解為k個(gè)子問(wèn)題以及用merge將k個(gè)子問(wèn)題解合并為原問(wèn)題解需用f(n)個(gè)單位時(shí)間。用T(n)表示該分治法解規(guī)模為|P|=n問(wèn)題所需計(jì)算時(shí)間，則有：經(jīng)過(guò)迭代法求得方程解：第20頁(yè)二分搜索技術(shù)給定已按升序排好序n個(gè)元素a[0:n-1]，現(xiàn)要在這n個(gè)元素中找出一特定元素x。據(jù)此輕易設(shè)計(jì)出二分搜索算法：template<classType>intBinarySearch(Typea[],constType&x,intl,intr){while(r>=l){intm=(l+r)/2;if(x==a[m])returnm;if(x<a[m])r=m-1;elsel=m+1;}return-1;}算法復(fù)雜度分析：每執(zhí)行一次算法while循環(huán)，待搜索數(shù)組大小降低二分之一。所以，在最壞情況下，while循環(huán)被執(zhí)行了O(logn)次。循環(huán)體內(nèi)運(yùn)算需要O(1)時(shí)間，所以整個(gè)算法在最壞情況下計(jì)算時(shí)間復(fù)雜性為O(logn)。第21頁(yè)合并排序基本思想：將待排序元素分成大小大致相同2個(gè)子集合，分別對(duì)2個(gè)子集合進(jìn)行排序，最終將排好序子集合合并成為所要求排好序集合。publicstaticvoidmergeSort(Comparablea[],intleft,intright){

if(left<right){//最少有2個(gè)元素inti=(left+right)/2;//取中點(diǎn)

mergeSort(a,left,i);

mergeSort(a,i+1,right);

merge(a,b,left,i,right);//合并到數(shù)組b

copy(a,b,left,right);//復(fù)制回?cái)?shù)組a}}復(fù)雜度分析T(n)=O(nlogn)漸進(jìn)意義下最優(yōu)算法第22頁(yè)算法消去遞歸合并排序算法輸入：含有個(gè)元素?cái)?shù)組A[]輸出：按遞增次序排序數(shù)組A[]1.template<classType>2.voidmerge_sort(TypeA[],intn)3.{4.inti,s,t=1;5.while(t<n){6.s=t; t=2*s; i=0;7.while(i+t<n){8.merge(A,i,i+s-1,i+t-1,t);9.i=i+t;10.}11.if(i+s<n)12.merge(A,i,i+s-1,n-1,n-i);13.}14.}第23頁(yè)合并排序算法mergeSort遞歸過(guò)程能夠消去。初始序列[49][38][65][97][76][13][27][3849][6597][1376][27]第一步第二步[38496597][132776]第三步[13273849657697]第24頁(yè)快速排序privatestaticvoidqSort(intp,intr){

if(p<r){intq=partition(p,r);//以a[p]為基準(zhǔn)元素將a[p:r]劃分成3段a[p:q-1],a[q]和a[q+1:r]，使得a[p:q-1]中任何元素小于等于a[q]，a[q+1:r]中任何元素大于等于a[q]。下標(biāo)q在劃分過(guò)程中確定。

qSort(p,q-1);//對(duì)左半段排序

qSort(q+1,r);//對(duì)右半段排序}}第25頁(yè)template<classType>intPartition(Typea[],intp,intr){inti=p,j=r+1;Typex=a[p];while(true){while(a[++i]<x&&i<r);//將<x元素交換到左邊區(qū)域while(a[--j>x);//將>x元素交換到右邊區(qū)域if(i>=j)break;Swap(a[i],a[j]);;}a[p]=a[j];a[j]=x;returnj;}快速排序第26頁(yè)線性時(shí)間選擇問(wèn)題問(wèn)題描述：給定線性集中n個(gè)元素和一個(gè)整數(shù)k,要求找出這n個(gè)元素中第k小元素，即假如將這n個(gè)元素依其線性序排列時(shí)，排在第k個(gè)位置元素即為我們要找元素。當(dāng)k=1時(shí)，即找最小元素；當(dāng)k=n時(shí)，即找最大元素；當(dāng)k=(n+1)/2時(shí)，稱為找中位數(shù)。第27頁(yè)線性時(shí)間選擇template<classType>TypeRandomizedSelect(Typea[],intp,intr,intk){if(p==r)returna[p];inti=RandomizedPartition(a,p,r),j=i-p+1;if(k<=j)returnRandomizedSelect(a,p,i,k);elsereturnRandomizedSelect(a,i+1,r,k-j);}第28頁(yè)線性時(shí)間選擇問(wèn)題算法上述Partition算法可用來(lái)求選擇問(wèn)題有效解。假如劃分元素v測(cè)定在A（j）位置上，則有j-1個(gè)元素小于或等于A(j),且有n-j個(gè)元素大于或等于A(j)。所以，若k<j,則第k小元素在A（1：j-1)中，再對(duì)之深入劃分。若k=j,則A(j)就是第k小元素若k>j,則第k小元素在A（j+1:n)中，再對(duì)之深入劃分。在最壞情況下，算法randomizedSelect需要O(n2)計(jì)算時(shí)間但能夠證實(shí)，算法randomizedSelect能夠在O(n)平均時(shí)間內(nèi)找出n個(gè)輸入元素中第k小元素。第29頁(yè)將n個(gè)輸入元素劃分成n/5個(gè)組，每組5個(gè)元素，只可能有一個(gè)組不是5個(gè)元素。用任意一個(gè)排序算法，將每組中元素排好序，并取出每組中位數(shù)，共n/5個(gè)。遞歸調(diào)用select來(lái)找出這n/5個(gè)元素中位數(shù)。假如n/5是偶數(shù)，就找它2個(gè)中位數(shù)中較大一個(gè)。以這個(gè)元素作為劃分基準(zhǔn)。線性時(shí)間選擇第30頁(yè)TypeSelect(Typea[],intp,intr,intk){if(r-p<75){用某個(gè)簡(jiǎn)單排序算法對(duì)數(shù)組a[p:r]排序;returna[p+k-1];};for(inti=0;i<=(r-p-4)/5;i++)將a[p+5*i]至a[p+5*i+4]第3小元素與a[p+i]交換位置;//找中位數(shù)中位數(shù)，r-p-4即上面所說(shuō)n-5Typex=Select(a,p,p+(r-p-4)/5,(r-p-4)/10);inti=Partition(a,p,r,x),j=i-p+1;if(k<=j)returnSelect(a,p,i,k);elsereturnSelect(a,i+1,r,k-j);}復(fù)雜度分析T(n)=O(n)第31頁(yè)32基本思想：

把求解問(wèn)題分成許多階段或多個(gè)子問(wèn)題，然后按次序求解各個(gè)子問(wèn)題。前一個(gè)子問(wèn)題解為后一個(gè)子問(wèn)題求解提供了有用信息。在求解任何一子問(wèn)題時(shí)，列出各種可能局部解，經(jīng)過(guò)決議保留那些有可能到達(dá)最優(yōu)局部解，丟棄其它局部解，依次處理各子問(wèn)題，最終一個(gè)子問(wèn)題就是問(wèn)題解。動(dòng)態(tài)規(guī)劃算法第32頁(yè)動(dòng)態(tài)規(guī)劃算法兩個(gè)基本要素對(duì)于一個(gè)多階段過(guò)程問(wèn)題，最優(yōu)決議是否存在，不但依賴于該問(wèn)題是否有最優(yōu)子結(jié)構(gòu)性質(zhì)，而能否采取動(dòng)態(tài)規(guī)劃方法，還要看該問(wèn)題子問(wèn)題是否含有重合性質(zhì)。最優(yōu)子結(jié)構(gòu)性質(zhì)：原問(wèn)題最優(yōu)解包含了其子問(wèn)題最優(yōu)解。子問(wèn)題重合性質(zhì)：每次產(chǎn)生子問(wèn)題并不總是新問(wèn)題，有些子問(wèn)題被重復(fù)計(jì)算屢次。

第33頁(yè)34動(dòng)態(tài)規(guī)劃基本步驟找出最優(yōu)解性質(zhì)，并刻劃其結(jié)構(gòu)特征。遞歸地定義最優(yōu)值。以自底向上方式計(jì)算出最優(yōu)值。依據(jù)計(jì)算最優(yōu)值時(shí)得到信息，結(jié)構(gòu)最優(yōu)解。第34頁(yè)35矩陣連乘問(wèn)題窮舉法動(dòng)態(tài)規(guī)劃將矩陣連乘積簡(jiǎn)記為A[i:j]，這里i≤j

考查計(jì)算A[i:j]最優(yōu)計(jì)算次序。設(shè)這個(gè)計(jì)算次序在矩陣Ak和Ak+1之間將矩陣鏈斷開，i≤k<j，則其對(duì)應(yīng)完全加括號(hào)方式為計(jì)算量：A[i:k]計(jì)算量加上A[k+1:j]計(jì)算量，再加上A[i:k]和A[k+1:j]相乘計(jì)算量第35頁(yè)建立遞歸關(guān)系令m[i][j],1≤i,j≤n，為計(jì)算A[i,j]最少數(shù)乘次數(shù)，則原問(wèn)題為m[1][n]。當(dāng)i=j時(shí)，A[i,j]為單一矩陣，m[i][j]=0；當(dāng)i＜j時(shí)，利用最優(yōu)子結(jié)構(gòu)性質(zhì)有：m[i][j]=min{m[i][k]+m[k+1][j]+pi–1pkpj}i≤k＜j其中矩陣Ai，1≤i≤n，維數(shù)為pi–1×pi。依據(jù)此遞歸式就能夠直接用遞歸程序來(lái)實(shí)現(xiàn)。第36頁(yè)消除重復(fù)矩陣連乘算法VoidMatrixChain(intp,intn,int**m,int**s){for(inti=1;i<=n;i++)m[i][i]=0;//將對(duì)角線元素賦值為零，即單個(gè)矩陣計(jì)算量為0for(intr=2;r<=n;r++)for(inti=1;i<=n–r+1;i++){intj=i+r–1;(5)m[i][j]=m[i+1][j]+p[i–1]*p[i]*p[j];

//計(jì)算A[i,j]=A[i:i]A[i+1:j]s[i][j]=i;//記下斷點(diǎn)i(7)for(intk=i+1;k<j;k++){intt=m[i][k]+m[k+1][j]+p[i–1]*p[k]*p[j];

//對(duì)i<k<j,逐一計(jì)算A[i,j]=A[i:k]A[k+1:j]if(t<m[i][j]){m[i][j]=t;s[i][j]=k;}

//記下較小m[i][j]及對(duì)應(yīng)斷點(diǎn)k

}}}算法時(shí)間復(fù)雜性上界為O(n3)第37頁(yè)第38頁(yè)39子問(wèn)題遞歸結(jié)構(gòu)由最長(zhǎng)公共子序列問(wèn)題最優(yōu)子結(jié)構(gòu)性質(zhì)建立子問(wèn)題最優(yōu)值遞歸關(guān)系。用c[i][j]統(tǒng)計(jì)序列和最長(zhǎng)公共子序列長(zhǎng)度。其中，和當(dāng)i=0或j=0時(shí)，空序列是A和B最長(zhǎng)公共子序列。故此時(shí)C[i][j]=0。其它情況下，由最優(yōu)子結(jié)構(gòu)性質(zhì)可建立遞歸關(guān)系以下：第39頁(yè)40計(jì)算最優(yōu)值因?yàn)樵谒紤]子問(wèn)題空間中，總共有θ(mn)個(gè)不一樣子問(wèn)題，所以，用動(dòng)態(tài)規(guī)劃算法自底向上地計(jì)算最優(yōu)值能提升算法效率。voidLCSLength(intm，intn，char*x，char*y，int**c，int**b){inti，j;for(i=1;i<=m;i++)c[i][0]=0;for(i=1;i<=n;i++)c[0][i]=0;for(i=1;i<=m;i++)for(j=1;j<=n;j++){if(x[i]==y[j]){c[i][j]=c[i-1][j-1]+1;b[i][j]=1;}elseif(c[i-1][j]>=c[i][j-1]){c[i][j]=c[i-1][j];b[i][j]=2;}else{c[i][j]=c[i][j-1];b[i][j]=3;}}}結(jié)構(gòu)最長(zhǎng)公共子序列voidLCS(inti，intj，char*x，int**b){if(i==0||j==0)return;if(b[i][j]==1){LCS(i-1，j-1，x，b);cout<<x[i];}elseif(b[i][j]==2)LCS(i-1，j，x，b);elseLCS(i，j-1，x，b);}第40頁(yè)410-1背包問(wèn)題給定n種物品和一背包。物品i重量是wi，其價(jià)值為vi，背包容量為C。問(wèn)應(yīng)怎樣選擇裝入背包物品，使得裝入背包中物品總價(jià)值最大?0-1背包問(wèn)題是一個(gè)特殊整數(shù)規(guī)劃問(wèn)題。第41頁(yè)420-1背包問(wèn)題設(shè)所給0-1背包問(wèn)題子問(wèn)題最優(yōu)值為m(i，j)，即m(i，j)是背包容量為j，可選擇物品為i，i+1，…，n時(shí)0-1背包問(wèn)題最優(yōu)值。由0-1背包問(wèn)題最優(yōu)子結(jié)構(gòu)性質(zhì)，能夠建立計(jì)算m(i，j)遞歸式以下。第42頁(yè)43template<classType>voidKnapsack(Typev,intw,intc,intn,Type**m){intjMax=min(w[n]-1,c);for(intj=0;j<=jMax;j++)m[n][j]=0;for(intj=w[n];j<=c;j++)n[n][j]=v[n];for(inti=n-1;i<1;i--){jMax=min(w[i]-1,c);for(intj=0;j<=jMax;j++)m[i][j]=m[i+1][j];for(intj=w[i];j<=c;j++)m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]);}m[1][c]=m[2][c];if(c>=w[1])m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]);}第43頁(yè)貪心算法貪心算法總是作出在當(dāng)前看來(lái)最好選擇，即所作選擇只是局部最優(yōu)選擇。希望從局部最優(yōu)選擇得到整體最優(yōu)解。采取逐步結(jié)構(gòu)最優(yōu)解方法。在每個(gè)階段，都作出一個(gè)看上去最優(yōu)決議（在一定標(biāo)準(zhǔn)下）。決議一旦作出，就不可再更改。第44頁(yè)貪心方法描述量度標(biāo)準(zhǔn)A(1)A(2)…A(n)A'(1)A'(2)…A'(n)S(1)S(2)…這種量度意義下部分最優(yōu)解原問(wèn)題n個(gè)輸入排序后n個(gè)輸入A'(j)貪心算法基本要素第45頁(yè)貪心算法基本要素可用貪心算法求解問(wèn)題基本要素

最優(yōu)子結(jié)構(gòu)性質(zhì)貪心選擇性質(zhì)。

貪心算法基本要素第46頁(yè)貪心算法與動(dòng)態(tài)規(guī)劃算法差異相同點(diǎn)：都含有最優(yōu)子結(jié)構(gòu)性質(zhì)區(qū)分：動(dòng)態(tài)規(guī)劃算法每步所作選擇往往依賴于相關(guān)子問(wèn)題解。只有解出相關(guān)子問(wèn)題才能作出選擇。貪心算法僅在當(dāng)前狀態(tài)下作出最好選擇，即局部最優(yōu)選擇，但不依賴于子問(wèn)題解貪心：自頂向下動(dòng)態(tài)規(guī)劃：自底向上貪心算法基本要素第47頁(yè)活動(dòng)安排問(wèn)題已知n個(gè)活動(dòng)E={1,2,…,n}要求使用同一資源，第k個(gè)活動(dòng)要求開始和結(jié)束時(shí)間為sk,fk,其中sk<fk,k=1,2,…,n。活動(dòng)k與活動(dòng)j稱為相容假如sk≥

fj或者sj≥

fk。活動(dòng)安排問(wèn)題就是要在所給活動(dòng)集合中選出最大相容活動(dòng)子集。問(wèn)題提出：第48頁(yè)基本思緒在安排時(shí)應(yīng)該將結(jié)束時(shí)間早活動(dòng)盡可能往前安排，好給后面活動(dòng)安排留出更多空間，從而到達(dá)安排最多活動(dòng)目標(biāo)。貪心準(zhǔn)則應(yīng)該是：在未安排活動(dòng)中挑選結(jié)束時(shí)間最早活動(dòng)安排。活動(dòng)安排問(wèn)題第49頁(yè)首先將安排11個(gè)活動(dòng)開始時(shí)間和結(jié)束時(shí)間按結(jié)束時(shí)間非減次序排列以下：k1234567891011s[k]130535688212f[k]4567891011121314活動(dòng)安排問(wèn)題第50頁(yè)012345678910111213141isifi11423530645753865976108811981210213111214√21314141461471481489148101481114811√√√活動(dòng)安排問(wèn)題5

陰影長(zhǎng)條表示活動(dòng)是已選入集合A活動(dòng)，而空白長(zhǎng)條表示活動(dòng)是當(dāng)前正在檢驗(yàn)相容性活動(dòng)。第51頁(yè)52活動(dòng)安排問(wèn)題PublicstaticvoidgreedySelector(int[]s,intf[],booleana[]){intn=s.length-1;a[0]=true;intj=0;intcount=1;for(inti=1;i<=n;i++){if(s[i]>=f[j]){a[i]=true;j=i;count++;}elsea[i]=false;}returncount;}下面給出解活動(dòng)安排問(wèn)題貪心算法GreedySelector:各活動(dòng)起始時(shí)間和結(jié)束時(shí)間存放于數(shù)組s和f中且按結(jié)束時(shí)間非減序排列

第52頁(yè)530-1背包問(wèn)題：

給定n種物品和一個(gè)背包。物品i重量是Wi，其價(jià)值為Vi，背包容量為C。應(yīng)怎樣選擇裝入背包物品，使得裝入背包中物品總價(jià)值最大?

在選擇裝入背包物品時(shí)，對(duì)每種物品i只有2種選擇，即裝入背包或不裝入背包。不能將物品i裝入背包屢次，也不能只裝入部分物品i。第53頁(yè)54背包問(wèn)題：

與0-1背包問(wèn)題類似，所不一樣是在選擇物品i裝入背包時(shí)，能夠選擇物品i一部分，而不一定要全部裝入背包，1≤i≤n。形式化描述為：

這2類問(wèn)題都含有最優(yōu)子結(jié)構(gòu)性質(zhì)，極為相同，但背包問(wèn)題能夠用貪心算法求解，而0-1背包問(wèn)題卻不能用貪心算法求解。

其中C>0為背包容量，wi>0,vi>0，(x1,x2,…,xn)為最優(yōu)解。第54頁(yè)55

首先計(jì)算每種物品單位重量?jī)r(jià)值vi/wi，然后，依貪心選擇策略，將盡可能多單位重量?jī)r(jià)值最高(即vi/wi盡可大)物品裝入背包。若將這種物品全部裝入背包后，背包內(nèi)物品總重量未超出C，則選擇單位重量?jī)r(jià)值次高物品并盡可能多地裝入背包。依此策略一直地進(jìn)行下去，直到背包裝滿為止。若最終一個(gè)物品不能全部裝入時(shí)，僅裝其一部分使背包裝滿即可。 詳細(xì)算法可描述以下頁(yè)：

用貪心算法解背包問(wèn)題基本思想：第55頁(yè)貪心解背包問(wèn)題首先計(jì)算每種物品單位重量?jī)r(jià)值vi/wi，然后，將盡可能多單位重量?jī)r(jià)值最高物品裝入背包。

voidKnapsack(intn,floatM,floatv[],floatw[],floatx[]){Sort(n,v,w);//將各種物品按單位重量?jī)r(jià)值排序inti;for(i=1;i<=n;i++)x[i]=0;//將解向量初始化為零floatc=M;//是背包剩下容量初始化為Mfor(i=1;i<=n;i++){if()break;x[i]=1;c;}if(i<=n);

}w[i]>c-=w[i]x[i]=c/w[i]第56頁(yè)算法復(fù)雜度該算法主要計(jì)算時(shí)間在于將各種物品依其單位重量?jī)r(jià)值從大到小次序。所以算法計(jì)算時(shí)間上界為O(nlogn)。第57頁(yè)58單源最短路徑

給定帶權(quán)有向圖G=(V,E)，其中每條邊權(quán)是非負(fù)實(shí)數(shù)。另外，還給定V中一個(gè)頂點(diǎn)，稱為源。現(xiàn)在要計(jì)算從源到全部其它各頂點(diǎn)最短路徑長(zhǎng)度。這里徑路長(zhǎng)度是指路徑上各邊權(quán)之和。這個(gè)問(wèn)題通常稱為單源最短路徑問(wèn)題。

1、Dijkstra算法基本思想

Dijkstra算法是解單源最短路徑問(wèn)題貪心算法。其基本思想是:設(shè)置頂點(diǎn)集合S(初始僅含源)并不停地作貪心選擇清華大學(xué)出版社第58頁(yè)59單源最短路徑 來(lái)擴(kuò)充這個(gè)集合；一個(gè)頂點(diǎn)屬于集合S當(dāng)且僅當(dāng)從源到該頂點(diǎn)最短路徑長(zhǎng)度已知。

詳細(xì)而言：初始時(shí)，S中僅含有源。設(shè)u是G某一個(gè)頂點(diǎn)，把從源到u且中間只經(jīng)過(guò)S中頂點(diǎn)路徑稱為從源到u特殊路徑，并用數(shù)組dist統(tǒng)計(jì)當(dāng)前每個(gè)頂點(diǎn)所對(duì)應(yīng)最短特殊路徑長(zhǎng)度。Dijkstra算法每次從V-S中取出含有最短特殊路長(zhǎng)度頂點(diǎn)u添加到S中，同時(shí)依據(jù)S中頂點(diǎn)最短路徑對(duì)數(shù)組dist作必要修改。一旦S包含了V中全部頂點(diǎn)，則dist就統(tǒng)計(jì)了從源到其它全部頂點(diǎn)最短路徑長(zhǎng)度。清華大學(xué)出版社第59頁(yè)v0v2v1v3v4v5204550101515201035303迭代選取結(jié)點(diǎn)SDIST(1)(2)(3)(4)(5)置初值--05010∞45∞120,250102545∞230,2,345102545∞310,2,3,145102545∞440,2,3,1,445102545∞550,2,3,1,4,545102545∞考慮需要哪些存放結(jié)構(gòu)？算法怎樣實(shí)現(xiàn)？循環(huán)需要幾次？每次循環(huán)做什么工作？首先為第一行賦初值；循環(huán)n-1次；每次依據(jù)新加進(jìn)來(lái)結(jié)點(diǎn)修改能夠修改路徑，并選擇最短第60頁(yè)61最小生成樹

設(shè)G=(V,E)是無(wú)向連通帶權(quán)圖，即一個(gè)網(wǎng)絡(luò)。E中每條邊(v,w)權(quán)為c[v][w]。假如G子圖G’是一棵包含G全部頂點(diǎn)樹，則稱G’為G生成樹。生成樹上各邊權(quán)總和稱為該生成樹花費(fèi)。在G全部生成樹中，花費(fèi)最小生成樹稱為G最小生成樹。

第61頁(yè)62最小生成樹1、最小生成樹性質(zhì) 用貪心算法設(shè)計(jì)策略能夠設(shè)計(jì)出結(jié)構(gòu)最小生成樹有效算法。本節(jié)介紹結(jié)構(gòu)最小生成樹Prim算法和Kruskal算法都能夠看作是應(yīng)用貪心算法設(shè)計(jì)策略例子。盡管這2個(gè)算法做貪心選擇方式不一樣，它們都利用了下面最小生成樹性質(zhì)： 設(shè)G=(V,E)是連通帶權(quán)圖，U是V非空真子集。假如(u,v)E，且uU，vV-U，且在全部這么邊中(即斷集中)，(u,v)權(quán)c[u][v]最小，那么一定存在G一棵最小生成樹，它以(u,v)為其中一條邊。這個(gè)性質(zhì)有時(shí)也稱為MST性質(zhì)。

證實(shí)略。第62頁(yè)63最小生成樹Prim算法

設(shè)G=(V,E)是連通帶權(quán)圖，V={1,2,…,n}。 結(jié)構(gòu)G最小生成樹Prim算法基本思想是：首先置S={1}，然后，只要S是V真子集，就作以下貪心選擇：選取滿足條件iS，jV-S，且c[i][j]最小邊，將頂點(diǎn)j添加到S中。這個(gè)過(guò)程一直進(jìn)行到S=V時(shí)為止。 在這個(gè)過(guò)程中選取到全部邊恰好組成G一棵最小生成樹。清華大學(xué)出版社第63頁(yè)64最小生成樹 利用最小生成樹性質(zhì)和數(shù)學(xué)歸納法輕易證實(shí)，上述算法中邊集合T一直包含G某棵最小生成樹中邊。所以，在算法結(jié)束時(shí)，T中全部邊組成G一棵最小生成樹。

比如，對(duì)于右圖中帶權(quán)圖，按Prim算法選取邊過(guò)程以下頁(yè)圖所表示。清華大學(xué)出版社第64頁(yè)654.6最小生成樹清華大學(xué)出版社第65頁(yè)66最小生成樹3、Kruskal算法

Kruskal算法結(jié)構(gòu)G最小生成樹基本思想是，首先將Gn個(gè)頂點(diǎn)看成n個(gè)孤立連通分支。將全部邊按權(quán)從小到大排序。然后從第一條邊開始，依邊權(quán)遞增次序查看每一條邊，并按下述方法連接2個(gè)不一樣連通分支：當(dāng)查看到第k條邊(v,w)時(shí)，假如端點(diǎn)v和w分別是當(dāng)前2個(gè)不一樣連通分支T1和T2中頂點(diǎn)時(shí)，就用邊(v,w)將T1和T2連接成一個(gè)連通分支，然后繼續(xù)查看第k+1條邊；假如端點(diǎn)v和w在當(dāng)前同一個(gè)連通分支中，就直接再查看第k+1條邊。這個(gè)過(guò)程一直進(jìn)行到只剩下一個(gè)連通分支時(shí)為止。

清華大學(xué)出版社第66頁(yè)67最小生成樹

比如，對(duì)前面連通帶權(quán)圖，按Kruskal算法次序得到最小生成樹上邊以下列圖所表示。清華大學(xué)出版社第67頁(yè)問(wèn)題解向量：一個(gè)n元式(x1,x2,…,xn)形式。顯約束：對(duì)分量xi取值限定。隱約束：為滿足問(wèn)題解而對(duì)不一樣分量之間施加約束。解空間：?jiǎn)栴}解空間普通用解空間樹（SolutionSpaceTrees,也稱狀態(tài)空間樹）方式組織，其中，樹根結(jié)點(diǎn)位于第1層，表示搜索初始狀態(tài)，第2層結(jié)點(diǎn)表示對(duì)解向量第一個(gè)分量做出選擇后抵達(dá)狀態(tài)，第1層到第2層邊上標(biāo)出對(duì)第一個(gè)分量選擇結(jié)果，依這類推，從樹根結(jié)點(diǎn)到葉子結(jié)點(diǎn)路徑就組成了解空間一個(gè)可能解。回溯法第68頁(yè)回溯法基本思想

回溯法從根結(jié)點(diǎn)出發(fā)，按照深度優(yōu)先策略搜索（遍歷）解空間樹，搜索滿足約束條件解。初始時(shí)，根結(jié)點(diǎn)成為一個(gè)活結(jié)點(diǎn)，同時(shí)也稱為當(dāng)前擴(kuò)展結(jié)點(diǎn)。在當(dāng)前擴(kuò)展結(jié)點(diǎn)處，搜索向縱深方向移至一個(gè)新結(jié)點(diǎn)。這個(gè)新結(jié)點(diǎn)成為一個(gè)新活結(jié)點(diǎn)，并成為當(dāng)前擴(kuò)展結(jié)點(diǎn)。假如在當(dāng)前擴(kuò)展結(jié)點(diǎn)處不能再向縱深方向移動(dòng)，則當(dāng)前擴(kuò)展結(jié)點(diǎn)就成為一個(gè)死結(jié)點(diǎn)（即不再是一個(gè)活節(jié)點(diǎn)）。此時(shí)，應(yīng)往回移動(dòng)（回溯）至最近一個(gè)活結(jié)點(diǎn)處，并使這個(gè)活結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)。第69頁(yè)回溯法求解過(guò)程(1)針對(duì)所給問(wèn)題，定義問(wèn)題解空間；(2)確定易于搜索解空間結(jié)構(gòu)；(3)深度優(yōu)先搜索解空間，并在搜索中用剪枝函數(shù)防止無(wú)效搜索。需要注意是，問(wèn)題解空間樹是虛擬，并不需要在算法運(yùn)行時(shí)結(jié)構(gòu)一棵真正樹結(jié)構(gòu)。在任何時(shí)刻，算法只保留從根結(jié)點(diǎn)到當(dāng)前擴(kuò)展結(jié)點(diǎn)路徑。假如解空間樹中從根結(jié)點(diǎn)到葉結(jié)點(diǎn)最長(zhǎng)路徑長(zhǎng)度為h(n)，則回溯法所需計(jì)算空間通常為O(h(n))。而顯式地存放整個(gè)解空間則需要O(2h(n))或O(h(n)!)內(nèi)存空間。第70頁(yè)回溯法基本思想在搜索過(guò)程中，通常采取兩種策略防止無(wú)效搜索：（1）用約束條件剪去得不到可行解子樹；（2）用限界函數(shù)剪去得不到最優(yōu)解子樹。這兩類函數(shù)統(tǒng)稱為剪枝函數(shù)（PruningFunction）。在搜索至樹中任一結(jié)點(diǎn)時(shí)，先判斷該結(jié)點(diǎn)對(duì)應(yīng)部分解是否滿足約束條件，或者是否超出限界函數(shù)界，也就是判斷該結(jié)點(diǎn)是否包含問(wèn)題（最優(yōu)）解，假如必定不包含，則跳過(guò)對(duì)以該結(jié)點(diǎn)為根子樹搜索，即所謂剪枝（Pruning）；不然，進(jìn)入以該結(jié)點(diǎn)為根子樹，繼續(xù)按照深度優(yōu)先策略搜索。第71頁(yè)子集樹與排列樹當(dāng)所給問(wèn)題是從n個(gè)元素集合S中找出滿足某種性質(zhì)子集時(shí)，解空間為子集樹。

當(dāng)所給問(wèn)題是從n個(gè)元素集合S中找出滿足某種性質(zhì)排列時(shí)，解空間為排列樹。第72頁(yè)遍歷子集樹需O(2n)計(jì)算時(shí)間遍歷排列樹需要O(n!)計(jì)算時(shí)間voidbacktrack(intt){if(t>n)output(x);elsefor(inti=0;i<=1;i++){x[t]=i;if(constraint(t)&&bound(t))backtrack(t+1);}}voidbacktrack(intt){if(t>n)output(x);elsefor(inti=t;i<=n;i++){swap(x[t],x[i]);if(constraint(t)&&bound(t))

backtrack(t+1);swap(x[t],x[i]);}}5.1.5子集樹與排列樹//更換排列次序

當(dāng)前第一個(gè)元素和下面交換

//搜索完成后恢復(fù)

第73頁(yè)裝載問(wèn)題問(wèn)題定義有一批共n個(gè)集裝箱要裝上2艘載重量分別為c1和c2輪船，其中集裝箱i重量為wi，且∑wi≤c1+c2裝載問(wèn)題要求確定是否有一個(gè)合理裝載方案可將這n個(gè)集裝箱裝上這2艘輪船。假如有，找出一個(gè)裝載方案。第74頁(yè)問(wèn)題分析假如一個(gè)給定裝載問(wèn)題有解，則采取下面策略可得到最優(yōu)裝載方案：(1)首先將第一艘輪船盡可能裝滿；(2)將剩下集裝箱裝上第二艘輪船。將第一艘輪船盡可能裝滿等價(jià)于選取全體集裝箱一個(gè)子集，使該子集中集裝箱重量之和最靠近c(diǎn)1。由此可知，裝載問(wèn)題等價(jià)于以下特殊0-1背包問(wèn)題。第75頁(yè)算法設(shè)計(jì)解空間：子集樹可行性約束函數(shù)(選擇當(dāng)前元素)：上界函數(shù)(不選擇當(dāng)前元素)：當(dāng)前載重量cw+剩下集裝箱重量r>當(dāng)前最優(yōu)載重量bestw101111000不滿足約束函數(shù)1不滿足上界函數(shù)001第76頁(yè)裝載問(wèn)題算法描述n集裝箱數(shù)；w[]集裝箱重量數(shù)組；c第一艘輪船載重量；cw在遍歷結(jié)點(diǎn)處當(dāng)前載重量bsetw當(dāng)前最優(yōu)載重量privatestaticvoidbacktrack(inti){//搜索第i層結(jié)點(diǎn)if(i>n)//抵達(dá)葉結(jié)點(diǎn){if(cw>bestw)bestw=cw;return;}if(cw+w[i]<=c){//搜索左子樹x[i]=1;cw+=w[i];backtrack(i+1);cw-=w[i];}x[i]=0;//搜索右子樹backtrack(i+1);}}解空間：子集樹可行性約束函數(shù)(選擇當(dāng)前元素)：第77頁(yè)引入上界函數(shù)算法描述

當(dāng)前載重量cw+剩下集裝箱重量r當(dāng)前最優(yōu)載重量bestwvoidbacktrack(inti){//搜索第i層結(jié)點(diǎn)if(i>n)//抵達(dá)葉結(jié)點(diǎn)更新最優(yōu)解bestx,bestw;return;r-=w[i];if(cw+w[i]<=c)//搜索左子樹{x[i]=1;cw+=w[i];backtrack(i+1);cw-=w[i];}if(cw+r>bestw)//搜索右子樹{x[i]=0;backtrack(i+1);