計(jì)算機(jī)算法設(shè)計(jì)和分析總復(fù)習(xí)市公開課金獎市賽課一等獎?wù)n件

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

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

算法五個主要特征

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

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

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

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

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

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

常見指數(shù)時間限界函數(shù)：

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

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

if(n<=1)return1;

return

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

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

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

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

（3）合并：將各個子問題解合并為原問題解。第19頁分治法復(fù)雜性分析一個分治法將規(guī)模為n問題分成k個規(guī)模為n／k子問題去解。設(shè)分解閥值n0=1，且adhoc解規(guī)模為1問題花費(fèi)1個單位時間。再設(shè)將原問題分解為k個子問題以及用merge將k個子問題解合并為原問題解需用f(n)個單位時間。用T(n)表示該分治法解規(guī)模為|P|=n問題所需計(jì)算時間，則有：經(jīng)過迭代法求得方程解：第20頁二分搜索技術(shù)給定已按升序排好序n個元素a[0:n-1]，現(xiàn)要在這n個元素中找出一特定元素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)時間，所以整個算法在最壞情況下計(jì)算時間復(fù)雜性為O(logn)。第21頁合并排序基本思想：將待排序元素分成大小大致相同2個子集合，分別對2個子集合進(jìn)行排序，最終將排好序子集合合并成為所要求排好序集合。publicstaticvoidmergeSort(Comparablea[],intleft,intright){

if(left<right){//最少有2個元素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頁算法消去遞歸合并排序算法輸入：含有個元素?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頁合并排序算法mergeSort遞歸過程能夠消去。初始序列[49][38][65][97][76][13][27][3849][6597][1376][27]第一步第二步[38496597][132776]第三步[13273849657697]第24頁快速排序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在劃分過程中確定。

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

qSort(q+1,r);//對右半段排序}}第25頁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頁線性時間選擇問題問題描述：給定線性集中n個元素和一個整數(shù)k,要求找出這n個元素中第k小元素，即假如將這n個元素依其線性序排列時，排在第k個位置元素即為我們要找元素。當(dāng)k=1時，即找最小元素；當(dāng)k=n時，即找最大元素；當(dāng)k=(n+1)/2時，稱為找中位數(shù)。第27頁線性時間選擇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頁線性時間選擇問題算法上述Partition算法可用來求選擇問題有效解。假如劃分元素v測定在A（j）位置上，則有j-1個元素小于或等于A(j),且有n-j個元素大于或等于A(j)。所以，若k<j,則第k小元素在A（1：j-1)中，再對之深入劃分。若k=j,則A(j)就是第k小元素若k>j,則第k小元素在A（j+1:n)中，再對之深入劃分。在最壞情況下，算法randomizedSelect需要O(n2)計(jì)算時間但能夠證實(shí)，算法randomizedSelect能夠在O(n)平均時間內(nèi)找出n個輸入元素中第k小元素。第29頁將n個輸入元素劃分成n/5個組，每組5個元素，只可能有一個組不是5個元素。用任意一個排序算法，將每組中元素排好序，并取出每組中位數(shù)，共n/5個。遞歸調(diào)用select來找出這n/5個元素中位數(shù)。假如n/5是偶數(shù)，就找它2個中位數(shù)中較大一個。以這個元素作為劃分基準(zhǔn)。線性時間選擇第30頁TypeSelect(Typea[],intp,intr,intk){if(r-p<75){用某個簡單排序算法對數(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即上面所說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頁32基本思想：

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

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

考查計(jì)算A[i:j]最優(yōu)計(jì)算次序。設(shè)這個計(jì)算次序在矩陣Ak和Ak+1之間將矩陣鏈斷開，i≤k<j，則其對應(yīng)完全加括號方式為計(jì)算量：A[i:k]計(jì)算量加上A[k+1:j]計(jì)算量，再加上A[i:k]和A[k+1:j]相乘計(jì)算量第35頁建立遞歸關(guān)系令m[i][j],1≤i,j≤n，為計(jì)算A[i,j]最少數(shù)乘次數(shù)，則原問題為m[1][n]。當(dāng)i=j時，A[i,j]為單一矩陣，m[i][j]=0；當(dāng)i＜j時，利用最優(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ù)此遞歸式就能夠直接用遞歸程序來實(shí)現(xiàn)。第36頁消除重復(fù)矩陣連乘算法VoidMatrixChain(intp,intn,int**m,int**s){for(inti=1;i<=n;i++)m[i][i]=0;//將對角線元素賦值為零，即單個矩陣計(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];

//對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]及對應(yīng)斷點(diǎn)k

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

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

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

fj或者sj≥

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

陰影長條表示活動是已選入集合A活動，而空白長條表示活動是當(dāng)前正在檢驗(yàn)相容性活動。第51頁52活動安排問題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;}下面給出解活動安排問題貪心算法GreedySelector:各活動起始時間和結(jié)束時間存放于數(shù)組s和f中且按結(jié)束時間非減序排列

第52頁530-1背包問題：

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

在選擇裝入背包物品時，對每種物品i只有2種選擇，即裝入背包或不裝入背包。不能將物品i裝入背包屢次，也不能只裝入部分物品i。第53頁54背包問題：

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

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

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

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

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

voidKnapsack(intn,floatM,floatv[],floatw[],floatx[]){Sort(n,v,w);//將各種物品按單位重量價值排序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頁算法復(fù)雜度該算法主要計(jì)算時間在于將各種物品依其單位重量價值從大到小次序。所以算法計(jì)算時間上界為O(nlogn)。第57頁58單源最短路徑

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

1、Dijkstra算法基本思想

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

詳細(xì)而言：初始時，S中僅含有源。設(shè)u是G某一個頂點(diǎn)，把從源到u且中間只經(jīng)過S中頂點(diǎn)路徑稱為從源到u特殊路徑，并用數(shù)組dist統(tǒng)計(jì)當(dāng)前每個頂點(diǎn)所對應(yīng)最短特殊路徑長度。Dijkstra算法每次從V-S中取出含有最短特殊路長度頂點(diǎn)u添加到S中，同時依據(jù)S中頂點(diǎn)最短路徑對數(shù)組dist作必要修改。一旦S包含了V中全部頂點(diǎn)，則dist就統(tǒng)計(jì)了從源到其它全部頂點(diǎn)最短路徑長度。清華大學(xué)出版社第59頁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)來結(jié)點(diǎn)修改能夠修改路徑，并選擇最短第60頁61最小生成樹

設(shè)G=(V,E)是無向連通帶權(quán)圖，即一個網(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頁62最小生成樹1、最小生成樹性質(zhì) 用貪心算法設(shè)計(jì)策略能夠設(shè)計(jì)出結(jié)構(gòu)最小生成樹有效算法。本節(jié)介紹結(jié)構(gòu)最小生成樹Prim算法和Kruskal算法都能夠看作是應(yīng)用貪心算法設(shè)計(jì)策略例子。盡管這2個算法做貪心選擇方式不一樣，它們都利用了下面最小生成樹性質(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)為其中一條邊。這個性質(zhì)有時也稱為MST性質(zhì)。

證實(shí)略。第62頁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中。這個過程一直進(jìn)行到S=V時為止。 在這個過程中選取到全部邊恰好組成G一棵最小生成樹。清華大學(xué)出版社第63頁64最小生成樹 利用最小生成樹性質(zhì)和數(shù)學(xué)歸納法輕易證實(shí)，上述算法中邊集合T一直包含G某棵最小生成樹中邊。所以，在算法結(jié)束時，T中全部邊組成G一棵最小生成樹。

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

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

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

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

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

當(dāng)所給問題是從n個元素集合S中找出滿足某種性質(zhì)排列時，解空間為排列樹。第72頁遍歷子集樹需O(2n)計(jì)算時間遍歷排列樹需要O(n!)計(jì)算時間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)前第一個元素和下面交換

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

第73頁裝載問題問題定義有一批共n個集裝箱要裝上2艘載重量分別為c1和c2輪船，其中集裝箱i重量為wi，且∑wi≤c1+c2裝載問題要求確定是否有一個合理裝載方案可將這n個集裝箱裝上這2艘輪船。假如有，找出一個裝載方案。第74頁問題分析假如一個給定裝載問題有解，則采取下面策略可得到最優(yōu)裝載方案：(1)首先將第一艘輪船盡可能裝滿；(2)將剩下集裝箱裝上第二艘輪船。將第一艘輪船盡可能裝滿等價于選取全體集裝箱一個子集，使該子集中集裝箱重量之和最靠近c(diǎn)1。由此可知，裝載問題等價于以下特殊0-1背包問題。第75頁算法設(shè)計(jì)解空間：子集樹可行性約束函數(shù)(選擇當(dāng)前元素)：上界函數(shù)(不選擇當(dāng)前元素)：當(dāng)前載重量cw+剩下集裝箱重量r>當(dāng)前最優(yōu)載重量bestw101111000不滿足約束函數(shù)1不滿足上界函數(shù)001第76頁裝載問題算法描述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頁引入上界函數(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);