計算理論與算法分析設(shè)計：總復(fù)習(xí)

計算理論與算法總復(fù)習(xí)成績計算方法平時成績30%上機題目平時作業(yè)平時考勤期末成績70%算法題中，嚴格按照題目要求給出算法代碼、算法思想、測試用例的求解過程。如果題目沒有明確要求給出算法代碼，那么不需要給出。2考題類型判斷題：10分.5個填空題：30分.10個大題：60分.5個左右3CH1算法概述算法的五個特征1）有窮性2）確定性3）輸入4）輸出5）可行性算法的定義:Informally,analgorithmisanywell-definedcomputationalprocedurethattakessomevalue,orsetofvalues,asinputandproducessomevalue,orsetofvalues,asoutput.Analgorithmisthusasequenceofcomputationalstepsthattransformtheinputintotheoutput.

5O、o、、、第一種理解方法設(shè)f和g是定義域為自然數(shù)N上的函數(shù)f(n)=O(g(n))

漸近上界記號O

若存在正數(shù)c和n0使得對一切n

n0

有0f(n)cg(n)f(n)=(g(n))

漸近下界記號

若存在正數(shù)c和n0使得對一切n

n0有0cg(n)f(n)f(n)=o(g(n))

非緊上界記號o

若對任意正數(shù)c存在n0使得對一切n

n0有0f(n)<cg(n)f(n)=(g(n))

非緊下界記號

若對任意正數(shù)c存在n0使得對一切n

n0有0cg(n)<f(n)f(n)=(g(n))

緊漸近界記號

f(n)=O(g(n))且f(n)=(g(n))6漸近分析中函數(shù)比較f(n)=O(g(n))

ab;f(n)=

(g(n))

ab;f(n)=

(g(n))

a=b;f(n)=o(g(n))

a<b;f(n)=

(g(n))

a>b.O、o、、、第二種理解方法求復(fù)雜性函數(shù)階的極限方法例如，f(n)=n2/4,g(n)=n2,則n2/4=θ(n2)f(n)=logn,g(n)=n,則logn=o(n)8標(biāo)準(zhǔn)復(fù)雜性函數(shù)的比較O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)<O(2n)<O(n!)<O(nn)多項式時間階指數(shù)時間階一個算法的時間復(fù)雜性如果是O(nk)(k為有理數(shù)），則稱此算法需要多項式時間。有效算法以多項式時間為限界的算法稱為有效算法9標(biāo)準(zhǔn)復(fù)雜性函數(shù)的比較O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)<O(2n)<O(n!)<O(nn)注意：1）不能劃等號2）以下若無特殊聲明，log是以2為底的對數(shù)3）上式只有在n較大的時候成立O(1)的含義？計算時間由一個常數(shù)（零次多項式）來限界多項式時間階指數(shù)時間階10TimetoFinishInputSize(n)O(nx)O(n)O(1)O(lgn)O(an)O(n

lgn)11例例：算法A1,A2的時間復(fù)雜性分別是n,2n,設(shè)100μs是一個單位時間，求A1,A2在1s內(nèi)能處理的問題規(guī)模。已知lg2=0.301T(n)=nT(n)*10-4=1即n*10-4=1所以n=

104

12例假設(shè)某算法在輸入規(guī)模為n的時間復(fù)雜性為T(n)=3*2n。在某臺計算機上實現(xiàn)并完成該算法的時間為t秒?，F(xiàn)在另一計算機，其運行速度為第一臺的64倍，那么在這臺新機器上用同一算法在t秒內(nèi)能解輸入規(guī)模為多大的問題？13例解：設(shè)新機器用同一算法內(nèi)能解輸入規(guī)模為n1的問題，那么有3*2n=3*2n1/64，解得n1=n+6.14CH2分治法

基本思想：將問題分解成若干個子問題，然后求解子問題，由此得到原問題的解。即“分而治之”

divide-and-conquer

把輸入分成與原問題類型相同的多個子問題16分治法是一個遞歸地求解問題的過程分治法在每一層遞歸上有三個步驟分解:通過某種方法,將原問題分解成若干個規(guī)模較小,相互獨立,與原問題形式相同的子問題解決:若子問題規(guī)模小到可以直接解決(稱為基本問題),則直接解決,否則把子問題進一步分解，遞歸求解合并:通過某種方法,將子問題的解合并為原問題的解17分治法的抽象過程divide-and-conquer(S){if(small(S))return(adhoc(S));divideSintosmallersubsetS1,S2,…,Si,…Sk;for(i=1;i<=k;i++)yi

←divide-and-conquer(Si);returnmerge(y1,y2,…,yi,…,yk);}18例1用分治法求n個元素集合S中的最大、最小元素。假設(shè)n=2m。要求每次平分成2個子集。voidmaxmin(intA[],int&e_max,int&e_min,intlow,inthigh)2.{3.intmid,x1,y1,x2,y2;4.if((high-low<=1)){5.if(A[high]>A[low]){6.e_max=A[high];7.e_min=A[low];8.}9.else{10.e_max=A[low];11.e_min=A[high];12.}13.}1914.else{15.mid=(low+high)/2;16.maxmin(A,&x1,&y1,low,mid);17.maxmin(A,&x2,&y2,mid+1,high);18.e_max=max(x1,x2);19.e_min=min(y1,y2);20.}21.}T(n)=1n=2n>22T(n/2)+220T(n)=2T(n/2)+2=2[2T(n/22)+2]+2=22T(n/22)+2(1+2)=23T(n/23)+2(1+2+22)=…=2m-1T(2)+2(1+2+…n=2m+2m-2)=2m-1+2[1(1-2m-1)/(1-2)]=2m-1+2m-2=3n/2-221

用分治法求n個元素集合S中的最大、最小元素。寫出算法，并分析時間復(fù)雜性（比較次數(shù)）。假設(shè)n=3m。要求每次平分成3個子集。T(n)=n=3n>33T(n/3)+43T(n)=5n/3-2平分成2個子集T(n)

=3n/2-222歸并排序（MergeSort)voidMergeSort(intA[],B[],intl,intr){ if(l==r) return; intm=(l+r)/2; MergeSort(A,l,m); MergeSort(A,m+1,r); Merge(A,B,l,m,r);//合并到數(shù)組B Copy(A,B);//復(fù)制回數(shù)組A}T(n)=n=2n>22T(n/2)+cn123主定理簡化版T(n)=n=2n>2aT(n/c)+bnxdT(n)=a<cx

(nxlogn)

(nx)a=cxa>cxT(n)=n=2n>22T(n/2)+cn1歸并排序

(nlogn)24T(n)=1n=2n>22T(n/2)+2?快排序（QuickSort)快排序—算法思想取序列的一個元素作為軸，利用這個軸把序列分成三段：左段，中段(軸),和右段,使左段中各元素都小于等于軸，右段中各元素都大于等于軸。(這個過程稱做對序列的劃分)左段和右段的元素可以獨立排序,將排好序的三段合并到一起即可上面的過程可以遞歸地執(zhí)行，直到每段的長度為125快排序---劃分過程

3865977613274949lowhighpivot=49

01234567high38659776134927low27389776134965high27389776654913low27381376654997high49=low26大整數(shù)乘法(1962年)由X=A2n/2+B,Y=C2n/2+D則

XY=(A2n/2+B)(C2n/2+D)=AC2n+(AD+BC)2n/2+BD=AC2n+((A-B)(D-C)+AC+BD)2n/2+BD計算成本：3次n/2位乘法，6次不超過n位加減法，2次移位，所有加法和移位共計O(n)次運算。由此可得，T(n)=O(nlog3)=O(n1.59)這種思想同樣可以用于十進制數(shù)的乘法中。1n=13T(n/2)+cnn>1T(n)=27求第k小的元素longSelect(k,S){if(|S|≤38){將S中的元素排成非遞減序；

return(S中的第k小元素);}else

{

將S中的元素劃分成長度等于5的

|S|/5

個子序列；28

由各子序列的中值元素組成非遞減序列M；

m←Select(

|M|/2

，M);

按m將S中的元素劃分成小于m、等于

m和大于m的三個子序列S1，S2和S3;if(|S1|>k)return(Select(k,S1));elseif(|S1|+|S2|≥k)return(m);elsereturn(Select(k-|S1|-|S2|,S3));}}29求第k個小的元素（選擇問題）m中值序列M

從小到大已知小于或者等于m的元素已知大于或者等于m的元素按m將S中的元素劃分成小于m、等于m和大于m的三個子序列S1，S2和S3;從小到大30線性時間選擇問題:定理：算法Select在O(n)時間內(nèi)找出n個元素序列中的第k小的元素。cn≤38T(

n/5

)+T(

3n/4

)+cnn>38T(n)≤T(n)=20cn用線性時間從n個元素中選擇出第k個小的元素31線性時間選擇:中位數(shù)應(yīng)用中位數(shù)原理X軸上有n個點，由左至右依次排列為找一個點xp(不一定是n個點之一)，使xp到各點距離和最小，解為：x1x2xpxnx即解為中位數(shù)或中位數(shù)的平均值。32棋盤覆蓋將2k×2k棋盤分割為4個2k-1×2k-1子棋盤將3個無特殊方格的子棋盤轉(zhuǎn)化為特殊棋盤，可以用一個L型骨牌覆蓋這3個較小棋盤的會合處，從而將原問題轉(zhuǎn)化為4個較小規(guī)模的棋盤覆蓋問題遞歸地使用這種分割，直至棋盤簡化為棋盤1×1。問題分解過程：以k=2時的問題為例，用二分法進行分解，得到如下圖，用雙線劃分的四個k=1的棋盤。①號②號③號④號34循環(huán)賽日程表設(shè)計一個滿足以下要求的比賽日程表：(1)每個選手必須與其他n-1個選手各賽一次；(2)每個選手一天只能賽一次；(3)循環(huán)賽一共進行n-1天。按分治策略，將所有的選手分為兩半，n個選手的比賽日程表就可以通過為n/2個選手設(shè)計的比賽日程表來決定。遞歸地用對選手進行分割，直到只剩下2個選手時，比賽日程表的制定就變得很簡單。這時只要讓這2個選手進行比賽就可以了。35循環(huán)賽日程表加4加2(a)2k(k=1)個選手比賽122112213443344312211234214334124321567865877856876556786587785687651234214334124321(b)2k(k=2)個選手比賽(c)2k(k=3)個選手比賽36循環(huán)賽日程表的推廣設(shè)計一個滿足以下要求的比賽日程表：(1)每個選手必須與其他n-1個選手各賽一次；(2)每個選手一天只能賽一次；(3)n為偶數(shù)時，循環(huán)賽一共進行n-1天。

n為奇數(shù)時，循環(huán)賽一共進行n天。37CH3動歸

方法概述:基本思想動態(tài)規(guī)劃的思想實質(zhì)是分治思想和解決冗余。與分治法類似的是，將原問題分解成若干個子問題，先求解子問題，然后從這些子問題的解得到原問題的解。與分治法不同的是，經(jīng)分解的子問題往往不是互相獨立的。若用分治法來解，有些共同部分（子問題或子子問題）被重復(fù)計算了很多次。如果能夠保存已解決的子問題的答案，在需要時再查找，這樣就可以避免重復(fù)計算、節(jié)省時間。動態(tài)規(guī)劃法用一個表來記錄所有已解的子問題的答案。這就是動態(tài)規(guī)劃法的基本思路。具體的動態(tài)規(guī)劃算法多種多樣，但它們具有相同的填表方式。39方法概述:適用條件

動態(tài)規(guī)劃法的有效性依賴于問題本身所具有的兩個重要性質(zhì)最優(yōu)子結(jié)構(gòu)：當(dāng)問題的最優(yōu)解包含了其子問題的最優(yōu)解時，稱該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。重疊子問題：在用遞歸算法自頂向下解問題時，每次產(chǎn)生的子問題并不總是新問題，有些子問題被反復(fù)計算多次。動態(tài)規(guī)劃算法正是利用了這種子問題的重疊性質(zhì)，對每一個子問題只解一次，而后將其解保存在一個表格中，在以后盡可能多地利用這些子問題的解。40多段圖的最短路問題123456789101112s97324212711118654356425V1V2V3V4V5t41多段圖的最短路問題假設(shè)s,v2,v3,···,vk-1,t是一條從s到t的最短路徑，則由v2到t的最短路徑是v2,v3,···,vk-1,t，否則設(shè)v2,q3,···,qk-1,t是一條由v2到t的更短路徑，則s,v2,q3,···,qk-1,t是一條比路徑s,v2,v3,···,vk-1,t更短的由s到t的路徑，與假設(shè)矛盾，故最優(yōu)化原理成立。42cost(i,j)=min{C(j,r)+cost(i+1,r)}

r∈Vi+1<j,r>∈EjrtViVi+1最短最短向前處理法：設(shè)P(i,j)是從Vi中的點j到t的一條最短路，cost(i,j)是這條路線的耗費。由后向前推算，得到43矩陣鏈乘法矩陣鏈乘問題滿足最優(yōu)性原理記A[i:j]為AiAi+1…Aj鏈乘的一個最優(yōu)括號方案，設(shè)A[i:j]的最優(yōu)次序中含有二個子鏈A[i:k]和A[k+1:n]，則A[i:k]和A[k+1:n]也是最優(yōu)的。（反證可得）44遞歸求解最優(yōu)解的值記m[i][j]為計算A[i:j]的最少乘法數(shù)，則原問題的最優(yōu)值為

m[1][n](AiAi+1…Ak)pi-1×pk×(Ak+1Ak+2…Aj)pk×pj45貨物儲運問題在一個鐵路沿線順序存放著n堆裝滿貨物的集裝箱。貨物儲運公司要將集裝箱有次序地集中成一堆。規(guī)定每次只能選相鄰的2堆集裝箱合并成新的一堆，所需的運輸費用與新的一堆中集裝箱數(shù)成正比。給定各堆的集裝箱數(shù)，試制定一個運輸方案，使總運輸費用最少。5,3,4,1,3,2,3,4設(shè)合并a[i:j]，1≤i≤j≤n，所需的最少費用為m[i,j]，則原問題的最優(yōu)值為m[1，n]。由最優(yōu)子結(jié)構(gòu)性質(zhì)可知，462024/9/29470-1背包問題:遞歸關(guān)系換一種視角遞歸式如下：不取物品i取物品i包含從1到i號物品的最優(yōu)選擇2024/9/29480-1背包問題00000pi–1(j–wi)pi–1(j)0pi(j)0目標(biāo)

0i–1in0j–wi

jM最長公共子序列的結(jié)構(gòu)設(shè)序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最長公共子序列為Z={z1,z2,…,zk}，則(1)若xm=yn，則zk=xm=yn，且z1,z2,…,zk-1是否為x1,x2,…,xm-1和y1,y2,…,yn-1的最長公共子序列。(2)若xm≠yn且zk≠xm，則Z是x1,x2,…,xm-1和Y的最長公共子序列(3)若xm≠yn且zk≠yn，則Z是X和y1,y2,…,yn-1的最長公共子序列49子問題的遞歸結(jié)構(gòu)由最長公共子序列問題的最優(yōu)子結(jié)構(gòu)性質(zhì)建立子問題最優(yōu)值的遞歸關(guān)系。用c[i][j]記錄序列和的最長公共子序列的長度。其中，Xi={x1,x2,…,xi}；Yj={y1,y2,…,yj}。當(dāng)i=0或j=0時，空序列是Xi和Yj的最長公共子序列。故此時C[i][j]=0。其它情況下，由最優(yōu)子結(jié)構(gòu)性質(zhì)可建立遞歸關(guān)系如下：50CH4貪心法貪心算法顧名思義，貪心算法總是作出在當(dāng)前看來最好的選擇貪心算法并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選擇貪心算法不能對所有問題都得到整體最優(yōu)解，但對許多問題它能產(chǎn)生整體最優(yōu)解：如單源最短路徑問題，最小生成樹問題等在一些情況下，即使貪心算法不能得到整體最優(yōu)解，其最終結(jié)果卻是最優(yōu)解的很好近似。524.2貪心算法的基本要素對于一個具體的問題是否可用貪心算法解此問題？能否得到問題的最優(yōu)解呢?從許多可以用貪心算法求解的問題中看到這類問題一般具有2個重要的性質(zhì)：貪心選擇性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì)534.2貪心算法的基本要素貪心選擇性質(zhì)所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來達到貪心算法可行的第一個基本要素與動態(tài)規(guī)劃算法的主要區(qū)別動態(tài)規(guī)劃算法通常以自底向上的方式解各子問題貪心算法則通常以自頂向下的方式進行，以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問題簡化為規(guī)模更小的子問題544.2貪心算法的基本要素最優(yōu)子結(jié)構(gòu)性質(zhì)當(dāng)一個問題的最優(yōu)解包含其子問題的最優(yōu)解時，稱此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題可用動態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征55部分(或者小數(shù))背包問題

已知一個容量大小為M重量的背包和n種物品，物品i的重量為wi,假定物品i的一部分xi放入背包會得到vixi這么大的收益，這里，0≤xi≤1，vi>0。采用怎樣的裝包方法才會使裝入背包的物品總效益最大？例：考慮以下情況下的背包問題

n=3,M=20,(v1,v2,v3)=(25,24,15)

(w1,w2,w3)=(18,15,10)56n=3,M=20,(v1,v2,v3)=(25,24,15)

(w1,w2,w3)=(18,15,10)

按vi/wi的非增次序?qū)⑽锲芬来畏湃氡嘲?/p>

(x1,x2,x3)ΣwixiΣvixi

(0,1,1/2)2031.557活動安排:問題描述有n個活動集E={1,2,…,n}使用同一資源，而同一時間內(nèi)同一資源只能由一個活動使用。每個活動的使用時間為[si,fi)i=1,…,n，si為開始時間，fi為結(jié)束時間，若[si,fi)與[sj,fj)不相交稱活動i和活動j是相容的。問題：選出最大的相容活動子集合。58貪心策略將各活動按結(jié)束時間排序f1≤f2≤…≤fn，先選出活動1，然后按活動編好從小到大的次序依次選擇與當(dāng)前活動相容的活動。59注：這種策略使剩余的可安排時間極大化，以便于安排盡可能多的相容活動。

活動安排:計算示例11個活動已按結(jié)束時間排序，用貪心算法求解：

i1234567891011start_timei130535688212finish_timei456789101112131401234567891011121314timea1a2a3a4a5a6a7a8a9a10a11相容活動：{a3,a9,a11},{a1,a4,a8,a11},{a2,a4,a9,a11}01234567891011121314timea1a2a3a4a5a6a7a8a9a10a1160有限期的任務(wù)安排問題用貪心法求解有限期的任務(wù)安排問題：假設(shè)只能在同一臺機器上加工n個任務(wù)，每個任務(wù)i完成時間均是一個單位時間。又設(shè)每個任務(wù)i都有一個完成期限di>0,當(dāng)且僅當(dāng)任務(wù)i在它的期限截止以前被完成時，任務(wù)i才能獲得pi的效益，每個任務(wù)的期限從整個工序的開工開始計時，問應(yīng)如何安排加工順序，才能獲得最大效益？n=6,(p1,p2,p3,p4,p5,p6)=(5,25,20,30,10,15),(d1,d2,d3,d4,d5,d6)=(1,5,2,3,3,2)61有限期的任務(wù)安排問題

首先按效益非增次序進行排序，然后按照

期限依次對此次序進行調(diào)整，排在后面的

或提前或排除。算法的粗略描述

voidGreedy-Job(D,J,n)

/*任務(wù)按p1≥p2≥···

≥pn

的次序輸入，它們的期限值D[i]≥1,1≤i≤n,n≥1,J是可以在它們的期限截止前完成的任務(wù)的集合*/{

J←{1};

for(i=2;i<=n;i++)

if（J∪{i}

的所有任務(wù)都能在它

們的截止期限前完成）

J←J∪{i};

}定理：算法Greedy-Job對于有期限的任務(wù)

安排問題得到一個最優(yōu)解。

以上過程反復(fù)進行到對第n個任務(wù)處理完畢。所得到的貪心解就是一個最優(yōu)解。

任務(wù)0123456

pi030252015105

di0352231J(1)=3J(2)=4J(3)=1J(4)=2

總效益：9064最優(yōu)裝載654.3最優(yōu)裝載

從剩下的貨箱中，選擇重量最小的貨箱。這種選擇次序可以保證所選的貨箱總重量最小，從而可以裝載更多的貨箱。根據(jù)這種貪婪策略，首先選擇最輕的貨箱，然后選次輕的貨箱，如此下去直到所有貨箱均裝上船或船上不能再容納其他任何一個貨箱。

假設(shè)n=8,[w1,...,w8]=[100,200,50,90,150,50,20,80],c=400。

從剩下的貨箱中，選擇重量最小的貨箱。67利用貪婪算法時，所考察貨箱的順序為7,3,6,8,4,1,5,2。貨箱7,3,6,8,4,1的總重量為390個單位且已被裝載，剩下的裝載能力為10個單位，小于剩下的任何一個貨箱。在這種貪婪解決算法中得到[x1,...,x8]=[1,0,1,1,0,1,1,1]且∑xi=6。排序之車間作業(yè)計劃模型一臺機器、n個零件的排序

目的：使得各加工零件在車間里停留的平均

時間最短。零件加工時間11.822.030.540.951.361.5最短：3,4,5,6,1,2(0.5+1.4+2.7+4.2+6+8)/6=3.868若按此順序：(1.8+3.8+4.3+5.2+6.5+8)/6=4.9CH5回溯法

69回溯法既帶有系統(tǒng)性又帶有跳躍性的搜索算法。在包含問題所有解的解空間樹中，按照深度優(yōu)先的策略，從根結(jié)點出發(fā)搜索解空間樹(系統(tǒng)性)

算法搜索至解空間樹的任一結(jié)點時，判斷該結(jié)點為根的子樹是否包含問題的解(跳躍性)如果肯定不包含，則跳過以該結(jié)點為根的子樹的搜索，逐層向其祖先結(jié)點回溯。否則，進入該子樹，繼續(xù)按深度優(yōu)先的策略進行搜索。

這種以深度優(yōu)先的方式系統(tǒng)地搜索問題的解的算法稱為回溯法，它適用于解一些組合數(shù)較大的問題。70問題的解空間71問題的解向量：回溯法希望一個問題的解能夠表示成一個n元式(x1,x2,…,xn)的形式。顯約束：對分量xi的取值限定。隱約束：為滿足問題的解而對不同分量之間施加的約束。解空間：對于問題的一個實例，解向量滿足顯式約束條件的所有多元組，構(gòu)成了該實例的一個解空間。注意：同一個問題可以有多種表示，有些表示方法更簡單，所需表示的狀態(tài)空間更?。ù鎯α可?，搜索方法簡單）。n=3時的0-1背包問題用完全二叉樹表示的解空間算法的基本步驟1）針對問題，定義問題的解空間（對解進行編碼）；2）確定易于搜索的解空間組織結(jié)構(gòu)（按樹或圖組織解）；3）以深度優(yōu)先方式搜索解空間，搜索過程中裁減掉死結(jié)點的子樹提高搜索效率。72常用剪枝函數(shù)：用約束函數(shù)在擴展結(jié)點處剪去不滿足約束的子樹；用限界函數(shù)剪去得不到最優(yōu)解的子樹。二類常見的解空間樹①子集樹：當(dāng)所給的問題是從n個元素的集合S中找出滿足某種性質(zhì)的子集時，相應(yīng)的解空間樹稱為子集樹葉結(jié)點數(shù)2n，總結(jié)點數(shù)2n+1，遍歷時間為Ω(2n)如0-1背包②排列樹：當(dāng)所給問題是確定n個元素滿足某種性質(zhì)的排列時，相應(yīng)的解空間樹稱為排列樹葉結(jié)點數(shù)n!，遍歷時間為Ω(n!)如TSP問題方法概述73回溯算法的一般框架子集樹回溯算法

voidBacktrack(intt)//搜索到樹的第t層

{//由第t層向第t+1層擴展，確定x[t]的值if(t>n)output(x);//葉結(jié)點是可行解，輸出解

elsewhile(allXt){//Xt為當(dāng)前擴展結(jié)點的所有可能取值集合，例如0和1

x[t]=Xt中第i個值;if(Constraint(t)&&Bound(t))Backtrack(t+1);}}執(zhí)行時：Backtrack(1)//從1擴展并回溯74節(jié)點可行，則探索下一深度當(dāng)前節(jié)點取遍所有可能，即探索樹下一深度回溯算法的一般框架（續(xù)）排列樹回溯算法

voidBacktrack(intt)//搜索到樹的第t層

{//由第t層向第t+1層擴展，確定x[t]的值if(t>n)output(x);//葉結(jié)點是可行解，輸出解

else//已經(jīng)探索到第t個元素，需要調(diào)整后面至n的元素排序fori=tton{//對后續(xù)節(jié)點，每個試一次swap(x[t],x[i]);if(Constraint(t)&&Bound(t))Backtrack(t+1);swap(x[t],x[i]);}}75恢復(fù)到初始排序，便于回溯針對第t個節(jié)點，依次將它與后繼所有節(jié)點進行置換，即遍歷新次序是有價值的4后問題設(shè)有一4*4的棋盤，把4個皇后放在棋盤上，要求滿足下列兩個條件：1）任意兩個皇后不在同一行上和同一列上；2）任意兩個皇后不在同一條對角線上；問有多少種放法？76設(shè)第i行放置第i個皇后，xi表示皇后i所處的列數(shù)，這樣4后問題的全部解向量可以寫成(x1,x2,x3,x4)的形式。12347568109x1=1x2=23424233BBBBB111213141516x1=2BB1341377裝載問題有一批共n個集裝箱要裝上2艘載重量分別為c1和c2的輪船，其中集裝箱i的重量為wi，且裝載問題要求確定是否有一個合理的裝載方案可將這個集裝箱裝上這2艘輪船。如果有，找出一種裝載方案。最優(yōu)裝載方案:(1)首先將第一艘輪船盡可能裝滿；(2)將剩余的集裝箱裝上第二艘輪船。78問題分析將第一艘輪船盡可能裝滿等價于選取全體集裝箱的一個子集，使該子集中集裝箱重量之和最接近C1。由此可知，裝載問題等價于以下特殊的0-1背包問題。79解空間：子集樹對于當(dāng)前擴展節(jié)點Z，對于箱子i，有x[i]=1：左子樹，代表選中x[i]=0：右子樹，代表不選可行性約束函數(shù)(選擇當(dāng)前元素)：記當(dāng)前載重量為cw若cw+w[i]<=c1，左子樹可選擇右子樹總是可以選，因為不增加重量80限界函數(shù)：用于剪去不含最優(yōu)解的子樹，從而提高算法在平均情況下的運行效率。設(shè)Z是解空間樹第i層上的當(dāng)前擴展結(jié)點，cw是當(dāng)前載重量，R是剩余集裝箱的重量，besetW是當(dāng)前最優(yōu)載重量，則當(dāng)

cw+R≤bestW時，剪去Z的右子樹81裝載問題算法描述voidbacktrack(inti){//搜索第i層結(jié)點

if(i>n)//到達葉結(jié)點更新最優(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);}r+=w[i];}82最大團問題給定無向圖G=(V，E)。如果U

V，且對任意u，v

U有(u，v)

E，則稱U是G的完全子圖。G的完全子圖U是G的團當(dāng)且僅當(dāng)U不包含在G的更大的完全子圖中。G的最大團是指G中所含頂點數(shù)最多的團。如果U

V且對任意u，v

U有(u，v)

E，則稱U是G的空子圖。G的空子圖U是G的獨立集當(dāng)且僅當(dāng)U不包含在G的更大的空子圖中。G的最大獨立集是G中所含頂點數(shù)最多的獨立集。對于任一無向圖G=(V，E)其補圖G=(V1，E1)定義為：V1=V，且(u，v)

E1當(dāng)且僅當(dāng)(u，v)

E。U是G的最大團當(dāng)且僅當(dāng)U是G的最大獨立集。124531245383問題分析解空間：子集樹可行性約束函數(shù)：頂點i到已選入的頂點集中每一個頂點都有邊相連。限界函數(shù)：有足夠多的可選擇頂點使得算法有可能找到更大的團。84voidClique::Backtrack(inti)//計算最大團{if(i>n){//到達葉結(jié)點

for(intj=1;j<=n;j++)bestx[j]=x[j];bestn=cn;return;}intOK=1;//檢查頂點i與當(dāng)前團的連接

for(intj=1;j<i;j++)if(x[j]&&a[i][j]==0){//i與j不相連

OK=0;break;}if(OK){//選中后仍滿足團定義，進入左子樹

x[i]=1;cn++;Backtrack(i+1);x[i]=0;cn--;}if(cn+n-i>bestn){//不選仍有可能獲得更優(yōu)解，進入右子樹

x[i]=0;Backtrack(i+1);}}a[][]：記錄G中邊的鄰接矩陣x[]：當(dāng)前解cn：當(dāng)前團中頂點數(shù)bestx[]：當(dāng)前最優(yōu)解bestn：當(dāng)前最優(yōu)團頂點數(shù)85子集和問題問題給定由n個不同正數(shù)組成的集合W={wi}，和正數(shù)M，求W中所有和等于M的子集的集合；例如n=6,M=30,

W={10,13,5,18,12,15}

86子集和問題按照回溯法思想，從狀態(tài)樹的根結(jié)點出發(fā)，做深度優(yōu)先搜索；當(dāng)在某一狀態(tài)A下，依次嘗試加入和不加入正數(shù)wi，若∑A+wi>M，則可停止對該結(jié)點的搜索；若∑A+∑(wi…wn)<M，則也可停止對該結(jié)點的搜索；87背包問題求最大價值解空間：子集樹1走左子樹，0走右子樹可行性約束函數(shù)當(dāng)前載重cw，價值cpcw+w[i]<=c，左子樹可選擇右子樹總是可以選，因為不增加重量限界函數(shù)：假設(shè)物品可拆分，利用貪心思想，求剩余空間裝滿對應(yīng)的最大價值按單位重量價值從大到小排序進行選擇880-1背包問題Bound(inti){//計算價值的上界，故效率更高

intcleft=c-cw;//剩余容量

intb=cp;//以物品單位重量價值遞減序裝入物品

while(i<=n&&w[i]<=cleft){cleft-=w[i];b+=p[i];i++;}//裝滿背包，假設(shè)物品可拆分

if(i<=n)b+=p[i]/w[i]*cleft;returnb;}89voidbacktrack(inti){//搜索第i層結(jié)點

if(i>n)//到達葉結(jié)點更新最優(yōu)解bestx,bestp;return;if(cw+w[i]<=c){//搜索左子樹

x[i]=1;cw+=w[i];cp+=p[i]

backtrack(i+1);cw-=w[i];cp-=p[i];}

if(bound(i+1)>bestp){x[i]=0;//搜索右子樹

backtrack(i+1);}}90有載重量M＝50的背包，物體重量分別為5,15,25,27,30，物體價值分別為12,30,44,46,50。求最優(yōu)裝入背包的物體及價值。91回溯過程的效率用回溯法去處理一實例所要生成的結(jié)點數(shù)，一般是采用在狀態(tài)空間樹中生成一條隨機路徑的方法估計。92CH6分支限界法

93方法概述:與回溯法的區(qū)別求解目標(biāo)不同：一般而言，回溯法的求解目標(biāo)是找出解空間樹中滿足約束條件的所有解，而分支限界法的求解目標(biāo)則是找出滿足約束條件的一個解；搜索方法不同：回溯算法使用深度優(yōu)先方法搜索，而分枝限界一般用寬度優(yōu)先或最小耗費方法來搜索；

94方法概述:與回溯法的區(qū)別對擴展結(jié)點的擴展方式不同：分支限界法中，每一個活結(jié)點只有一次機會成為擴展結(jié)點。活結(jié)點一旦成為擴展結(jié)點，就一次性產(chǎn)生其所有兒子結(jié)點；存儲空間的要求不同：相對而言，分枝限界法的存儲空間比回溯法大得多，因此當(dāng)內(nèi)存容量有限時，回溯法成功的可能性更大；

方法概述:

兩種常見的活結(jié)點擴展方式先進先出隊列（FIFO）:即從活結(jié)點表中取出結(jié)點的順序與加入結(jié)點的順序相同；優(yōu)先隊列:每個結(jié)點都有一個對應(yīng)的耗費或收益。如果查找一個具有最小耗費的解，下一個擴展結(jié)點就是具有最小耗費的活結(jié)點；如果希望搜索一個具有最大收益的解，下一個擴展結(jié)點是具有最大收益的活結(jié)點。96方法概述:示例1示例1（FIFO隊列分枝限界法）問題：0-1背包問題:物品數(shù)n=3,重量w=(20,15,15),價值v=(40,25,25),背包容量c=30,試裝入最大價值之和的物品?求解：①解空間:{(0,0,0),(0,0,1),…,(1,1,1)}②解空間樹:DBHAIEJKFCLMGNO1111111000000097方法概述:示例1③BFS搜索（FIFO隊列）擴展結(jié)點活結(jié)點隊列(可行結(jié)點)可行解(葉結(jié)點)解值

AB,CBCBD,E(D死結(jié)點)CECF,GEFGEJ,K(J死結(jié)點)FGK40FL,MGL,M50,25GN,OφN,O25,0

∴最優(yōu)解為L,即(0,1,1);解值為50DBHAIEJKFCLMGNO11111110000000w=(20,15,15),v=(40,25,25),c=3098方法概述:示例2示例2（優(yōu)先隊列分枝限界法）問題：0-1背包問題:物品數(shù)n=3,重量w=(20,15,15),價值v=(40,25,25),背包容量c=30,試裝入最大價值之和的物品?求解：①解空間:{(0,0,0),(0,0,1),…,(1,1,1)}②解空間樹:DBHAIEJKFCLMGNO1111111000000099方法概述:示例2BFS搜索（優(yōu)先隊列：按價值率優(yōu)先）擴展結(jié)點活結(jié)點堆(可行結(jié)點)可行解(葉結(jié)點)解值

AB,CBD,E(D死結(jié)點)EJ,K(J死結(jié)點)K40CF,G

FL,ML

50(最優(yōu))GN,OφBCECFGCGDBHAIEJKFCLMGNO11111110000000w=(20,15,15),v=(40,25,25),c=30100分配問題分配問題：設(shè)有n個人，每個人都可以完成n種不同的任務(wù)，但所需時間不同。如果只需一人去完成每一項工作，則應(yīng)如何分配n個人并使完成所有n項工作的總時間為最小。101人1234

A21097

B154148

C13141611

D41513922A做1B做1C做1D做1274133243624342831A做2B做2C做2A做3C做3283739B做2C做2D做2A→3,B→2,C→4,D→1,總時間為28例1：用分支限界法求解分配問題102單源最短路徑問題問題描述單源最短路徑問題：在下圖所給的有向圖G中，每一邊都有一個非負邊權(quán)。要求圖G的從源頂點s到目標(biāo)頂點t之間的最短路徑。

103單源最短路徑問題

下圖是用優(yōu)先隊列式分支限界法解有向圖G的單源最短路徑問題產(chǎn)生的解空間樹。其中，每一個結(jié)點旁邊的數(shù)字表示該結(jié)點所對應(yīng)的當(dāng)前路長。1046.2 單源最短路徑問題剪枝策略在算法擴展結(jié)點的過程中，一旦發(fā)現(xiàn)一個結(jié)點的下界不小于當(dāng)前找到的最短路長，則剪去以該結(jié)點為根的子樹利用結(jié)點間的控制關(guān)系進行剪枝。從源頂點s出發(fā)，2條不同路徑到達圖G的同一頂點。由于兩條路徑的路長不同，因此可以將路長大的路徑所對應(yīng)的樹中結(jié)點為根的子樹剪去105路徑(a,e,q)與(c,h)到達同一節(jié)點分別對應(yīng)的費用為5和6。稱搜索樹中節(jié)點A控制了B。因此可將B節(jié)點的子樹剪去ABCH7隨機

106定義：在算法中引入隨機因素,即通過隨機數(shù)選擇算法的下一步操作。特點：簡單、快速一種平衡：隨機算法可以理解為在時間、空間和隨機三大計算資源中的平衡1071、數(shù)值概率算法：用于數(shù)值問題的求解2、Sherwood算法一定能得到問題的正確解常見的四類隨機算法：1083、LasVegas算法或者得到正確的解，或者得不到解。4、MonteCarlo算法一定能得到解，但是得到的解可能不正確，然而這種概率是小的且有界的。常見的四類隨機算法：109網(wǎng)絡(luò)流

流,流量,最大流sv1v3v2v4t11/168/13101/412/1215/204/47/74/911/14稱f:V

V

R為流,若f滿足：(1)容量限制,f(u,v)

c(u,v)(2)反對稱性,f(u,v)=-f(v,u)(3)流守恒性,任意u

V\{s,t},

v

Vf(u,v)=0流量|f|=

v

Vf(s,v).

最大流:給定流網(wǎng)絡(luò)G,s,t,c,求

max{|f|:f是G的流}111流網(wǎng)絡(luò)的割割(S,T):(1)T=V-S(2)sS,t

T.f(S,T)=

u

S,v

Tf(u,v):f穿過割(S,T)的凈流c(S,T)=

u

S,v

Tc(u,v):割(S,T)的容量sv1v3v2v4t11/168/13101/412/1215/204/47/74/911/14←ST→例.下圖中的割(S,T),S={s,v1,v2},T={v3,v4,t}.

f(S,T)=19,

c(S,T)=26.最大流最小割定理f(S,T)=|f|,|f|

min{c(S,T)|割(S,T)}.

定理(最大流最小割)下列條件等價

(1)f是G的一個最大流;

(2)G不包含增廣路徑;

(3)存在割(S,T)使得|f|=c(S,T).

最大流算法基本思想:

找從s到t的增廣路徑,增大流,無則停止,得最大流113計算理論

CH1集合、關(guān)系與語言

數(shù)學(xué)歸納法鴿巢原理對角化原理1.5三個基本的證明技術(shù)116字