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

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

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

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

若存在正數(shù)c和n0使得對一切nn0有0cg(n)f(n)f(n)=o(g(n)).

若對任意正數(shù)c存在n0使得對一切nn0有0f(n)<cg(n)f(n)=(g(n)).

若對任意正數(shù)c存在n0使得對一切nn0有0cg(n)<f(n)f(n)=(g(n))

f(n)=O(g(n))且f(n)=(g(n))11/6/20226O、o、、、第二種理解方法求復(fù)雜性函數(shù)階的極限方法例如，f(n)=n2/4,g(n)=n2,則n2/4=θ(n2)f(n)=lg

n,g(n)=n,則lg

n=o(n)o11/6/20227標準復(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ù)），則稱此算法需要多項式時間。有效算法以多項式時間為限界的算法稱為有效算法11/6/20228標準復(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ù)時間階11/6/20229例例：算法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

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

11/6/202213例1用分治法求n個元素集合S中的最大、最小元素。假設(shè)n=2m。要求每次平分成2個子集。voidmaxmin(int

A[],int&e_max,int&e_min,int

low,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.}11/6/20221414.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)+211/6/202215用分治法求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-211/6/202216歸并排序（MergeSort)voidMergeSort(intA[],intB[],intl,inth){ if(l==h) return;

intm=(l+h)/2;

MergeSort(A,B,l,m);

MergeSort(A,B,m+1,h); Merge(A,B,l,m,h);}T(n)=n=2n>22T(n/2)

+cn111/6/202217主定理：其中n=ck,k為某個非負常數(shù)T(n)=n=2n>2aT(n/c)

+bnxdT(n)=a<cx(nx

logn)(nx)a=cxa>cxT(n)=n=2n>22T(n/2)

+cn1歸并排序

(nlogn)T(n)=1n=2n>22T(n/2)+211/6/202218快排序---劃分過程

3865977613274949lowhighpivot=49

01234567high38659776134927low27389776134965high27389776654913low27381376654997high49=low11/6/202219大整數(shù)乘法由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ù)的乘法中。11/6/202220求第k小的元素longSelect(k,S){if(|S|≤38){將S中的元素排成非遞減序；

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

{

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

|S|/5

個子序列；11/6/202221由各子序列的中值元素組成非遞減序列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));}}11/6/202222線性時間選擇問題:定理：算法Select在O(n)時間內(nèi)找出n個元素序列中的第k小的元素。

cn≤38T(n/5)+T(3n/4)+cnn>38T(n)≤T(n)=20cn用線性時間從n個元素中選擇出第k個小的元素11/6/202223線性時間選擇:中位數(shù)應(yīng)用中位數(shù)原理X軸上有n個點，由左至右依次排列為找一個點xp(不一定是n個點之一)，使xp到各點距離和最小，解為：x1x2xpxnx即解為中位數(shù)或中位數(shù)的平均值。11/6/202224【例】殘缺棋盤殘缺棋盤是一個有2k×2k

（k≥1）個方格的棋盤，其中恰有一個方格殘缺。圖中給出k=1時各種可能的殘缺棋盤，其中殘缺的方格用陰影表示。

稱作“三格板”，殘缺棋盤問題就是要用這四種三格板覆蓋更大的殘缺棋盤。①號②號③號④號11/6/202225問題分解過程：以k=2時的問題為例，用二分法進行分解，得到如下圖，用雙線劃分的四個k=1的棋盤。①號②號③號④號11/6/202226循環(huán)賽日程表設(shè)計一個滿足以下要求的比賽日程表：(1)每個選手必須與其他n-1個選手各賽一次；(2)每個選手一天只能賽一次；(3)循環(huán)賽一共進行n-1天。按分治策略，將所有的選手分為兩半，n個選手的比賽日程表就可以通過為n/2個選手設(shè)計的比賽日程表來決定。遞歸地用對選手進行分割，直到只剩下2個選手時，比賽日程表的制定就變得很簡單。這時只要讓這2個選手進行比賽就可以了。11/6/202227循環(huán)賽日程表加4加2(a)2k(k=1)個選手比賽122112213443344312211234214334124321567865877856876556786587785687651234214334124321(b)2k(k=2)個選手比賽(c)2k(k=3)個選手比賽11/6/202228循環(huán)賽日程表的推廣設(shè)計一個滿足以下要求的比賽日程表：(1)每個選手必須與其他n-1個選手各賽一次；(2)每個選手一天只能賽一次；(3)n為偶數(shù)時，循環(huán)賽一共進行n-1天。

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

11/6/202230方法概述:基本思想動態(tài)規(guī)劃的思想實質(zhì)是分治思想和解決冗余。與分治法類似的是，將原問題分解成若干個子問題，先求解子問題，然后從這些子問題的解得到原問題的解。與分治法不同的是，經(jīng)分解的子問題往往不是互相獨立的。若用分治法來解，有些共同部分（子問題或子子問題）被重復(fù)計算了很多次。11/6/202231方法概述:適用條件

動態(tài)規(guī)劃法的有效性依賴于問題本身所具有的兩個重要性質(zhì)最優(yōu)子結(jié)構(gòu)：當問題的最優(yōu)解包含了其子問題的最優(yōu)解時，稱該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。重疊子問題：在用遞歸算法自頂向下解問題時，每次產(chǎn)生的子問題并不總是新問題，有些子問題被反復(fù)計算多次。動態(tài)規(guī)劃算法正是利用了這種子問題的重疊性質(zhì)，對每一個子問題只解一次，而后將其解保存在一個表格中，在以后盡可能多地利用這些子問題的解。11/6/202232多段圖的最短路問題123456789101112s97324212711118654356425V1V2V3V4V5t11/6/202233多段圖的最短路問題假設(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)化原理成立。11/6/202234cost(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)是這條路線的耗費。由后向前推算，得到11/6/202235筆試題11/6/202236筆試題11/6/202237筆試題11/6/202238矩陣鏈乘法矩陣鏈乘問題滿足最優(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)的。（反證可得）11/6/202239遞歸求解最優(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×pj11/6/202240貨物儲運問題在一個鐵路沿線順序存放著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ì)可知，11/6/2022410-1背包問題00000pi–1(j–

wi)pi–1(j)0pi(j)0目標

0i–1in0j–

wi

jM11/6/202242最長公共子序列的結(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的最長公共子序列11/6/202243子問題的遞歸結(jié)構(gòu)由最長公共子序列問題的最優(yōu)子結(jié)構(gòu)性質(zhì)建立子問題最優(yōu)值的遞歸關(guān)系。用c[i][j]記錄序列和的最長公共子序列的長度。其中，Xi={x1,x2,…,xi}；Yj={y1,y2,…,yj}。當i=0或j=0時，空序列是Xi和Yj的最長公共子序列。故此時C[i][j]=0。其它情況下，由最優(yōu)子結(jié)構(gòu)性質(zhì)可建立遞歸關(guān)系如下：11/6/202244CH4貪心法11/6/202245部分(或者小數(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)11/6/202246n=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.511/6/202247活動安排:問題描述有n個活動集E={1,2,…,n}使用同一資源，而同一時間內(nèi)同一資源只能由一個活動使用。每個活動的使用時間為[si,fi)i=1,…,n，si為開始時間，fi為結(jié)束時間，若[si,fi)與[sj,fj)不相交稱活動i和活動j是相容的。問題：選出最大的相容活動子集合。11/6/202248貪心策略將各活動按結(jié)束時間排序f1≤f2≤…≤fn，先選出活動1，然后按活動編好從小到大的次序依次選擇與當前活動相容的活動。11/6/202249活動安排:計算示例11個活動已按結(jié)束時間排序，用貪心算法求解：

i1234567891011start_timei

130535688212finish_timei

456789101112131401234567891011121314timea1a2a3a4a5a6a7a8a9a10a11相容活動：{a3,a9,a11},{a1,a4,a8,a11},{a2,a4,a9,a11}01234567891011121314timea1a2a3a4a5a6a7a8a9a10a1111/6/202250有限期的任務(wù)安排問題用貪心法求解有限期的任務(wù)安排問題：假設(shè)只能在同一臺機器上加工n個任務(wù)，每個任務(wù)i完成時間均是一個單位時間。又設(shè)每個任務(wù)i都有一個完成期限di>0,當且僅當任務(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)11/6/202251有限期的任務(wù)安排問題

首先按效益非增次序進行排序，然后按照期限依次對此次序進行調(diào)整，排在后面的或提前或排除。11/6/202252以上過程反復(fù)進行到對第n個任務(wù)處理完畢。所得到的貪心解就是一個最優(yōu)解。

任務(wù)0123456

pi030252015105

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

總效益：9011/6/202253最優(yōu)裝載11/6/202254假設(shè)n=8,[w1,...,w8]=[100,200,50,90,150,50,20,80],c=400。

從剩下的貨箱中，選擇重量最小的貨箱。11/6/202255排序之車間作業(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.811/6/202256排序之車間作業(yè)計劃模型二：兩臺機器、n個零件的排序目的：使得完成全部工作的總時間最短。基本方法：在第一臺機器上加工時間越少的零件越早加工；在第二臺機器上加工時間越少的零件越晚加工；11/6/202257某車間需要用一臺車床和一臺銑床加工A、B、C、D

四個零件。每個零件都需要先用車床加工，再用銑床

加工。車床和銑床加工每個零件所需的工時（包括

加工前的準備時間以及加工后的處理時間）如下表。工時(小時)ABCD車床8466銑床6725則最優(yōu)方案為

小時。

26BADC

11/6/202258CH5回溯法

11/6/20225911/6/202260of158子集樹與排列樹遍歷子集樹需O(2n)計算時間

voidbacktrack(intt){if(t>n)output(x);elsefor(inti=0;i<=1;i++){

x[t]=i;if(legal(t))backtrack(t+1);}}11/6/20226011/6/202261of158子集樹與排列樹遍歷排列樹需要O(n!)計算時間voidbacktrack(intt){if(t>n)output(x);elsefor(inti=t;i<=n;i++){

swap(x[t],x[i]);if(legal(t))backtrack(t+1);

swap(x[t],x[i]);}}11/6/20226111/6/202262of1584后問題設(shè)有一4*4的棋盤，把4個皇后放在棋盤上，要求滿足下列兩個條件：1）任意兩個皇后不在同一行上和同一列上；2）任意兩個皇后不在同一條對角線上；問有多少種放法？11/6/20226211/6/202263of15812347568109x1=1x2=23424233BBBBB111213141516x1=2BB1341311/6/202263裝載問題有一批共n個集裝箱要裝上2艘載重量分別為c1和c2的輪船，其中集裝箱i的重量為wi，且裝載問題要求確定是否有一個合理的裝載方案可將這個集裝箱裝上這2艘輪船。如果有，找出一種裝載方案。最優(yōu)裝載方案:(1)首先將第一艘輪船盡可能裝滿；(2)將剩余的集裝箱裝上第二艘輪船。11/6/202264問題分析將第一艘輪船盡可能裝滿等價于選取全體集裝箱的一個子集，使該子集中集裝箱重量之和最接近。由此可知，裝載問題等價于以下特殊的0-1背包問題。11/6/202265算法設(shè)計解空間：子集樹可行性約束函數(shù)(選擇當前元素)：上界函數(shù)當前載重量cw+剩余集裝箱的重量r當前最優(yōu)載重量bestw11/6/202266算法設(shè)計上界函數(shù)：用于剪去不含最優(yōu)解的子樹，從而提高算法在平均情況下的運行效率。設(shè)Z是解空間樹第i層上的當前擴展結(jié)點，cw是當前載重量，R是剩余集裝箱的重量，bestW是當前最優(yōu)載重量，則當

cw+r≤bestW時，剪去Z的右子樹。11/6/202267裝載問題解空間：子集樹可行性約束函數(shù)(選擇當前元素)：上界函數(shù)(不選擇當前元素)：當前載重量cw+剩余集裝箱的重量r當前最優(yōu)載重量bestwprivatestaticvoidbacktrack(inti){//搜索第i層結(jié)點

if(i>n){//到達葉結(jié)點

//更新最優(yōu)解bestx,bestw;return;

if(cw>bestw){

for(j=1;j<=n;j++)bestx[j]=x[j];bestw=cw;}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];}11/6/202268最大團問題給定無向圖G=(V，E)。如果UV，且對任意u，vU有(u，v)E，則稱U是G的完全子圖。G的完全子圖U是G的團當且僅當U不包含在G的更大的完全子圖中。G的最大團是指G中所含頂點數(shù)最多的團。如果UV且對任意u，vU有(u，v)E，則稱U是G的空子圖。G的空子圖U是G的獨立集當且僅當U不包含在G的更大的空子圖中。G的最大獨立集是G中所含頂點數(shù)最多的獨立集。對于任一無向圖G=(V，E)其補圖G=(V1，E1)定義為：V1=V，且(u，v)E1當且僅當(u，v)E。U是G的最大團當且僅當U是G的最大獨立集。124531245311/6/202269最大團問題解空間：子集樹可行性約束函數(shù)：頂點i到已選入的頂點集中每一個頂點都有邊相連。上界函數(shù)：有足夠多的可選擇頂點使得算法有可能在右子樹中找到更大的團。privatestaticvoidbacktrack(inti){if(i>n){//到達葉結(jié)點

for(intj=1;j<=n;j++)bestx[j]=x[j];

bestn=cn;return;}//檢查頂點i與當前團的連接

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

ok=false;break;}if(ok){//進入左子樹

x[i]=1;cn++;backtrack(i+1);

cn--;}if(cn+n-i>bestn){//進入右子樹

x[i]=0;backtrack(i+1);}}}1245311/6/20227011/6/202271of158子集和問題問題給定由n個不同正數(shù)組成的集合W={wi}，和正數(shù)M，求W中所有和等于M的子集的集合；例如n=6,M=30,

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

11/6/20227111/6/202272of158子集和問題按照回溯法思想，從狀態(tài)樹的根結(jié)點出發(fā)，做深度優(yōu)先搜索；當在某一狀態(tài)A下，依次嘗試加入和不加入正數(shù)wi，若∑A+wi>M，則可停止對該結(jié)點的搜索；若∑A+∑(wi…wn)<M，則也可停止對該結(jié)點的搜索；11/6/20227211/6/202273of1580/1背包問題

且

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

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

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

11/6/20227811/6/202279of158方法概述:示例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)}②解空間樹:DBHAIEJKFCLMGNO1111111000000011/6/20227911/6/202280of158方法概述:示例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=3011/6/20228011/6/202281of158方法概述:示例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)}②解空間樹:DBHAIEJKFCLMGNO1111111000000011/6/20228111/6/202282of158方法概述:示例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=3011/6/20228211/6/202283of158分配問題分配問題：設(shè)有n個人，每個人都可以完成n種不同的任務(wù)，但所需時間不同。如果只需一人去完成每一項工作，則應(yīng)如何分配n個人并使完成所有n項工作的總時間為最小。11/6/202283單源最短路徑問題問題描述單源最短路徑問題：在下圖所給的有向圖G中，每一邊都有一個非負邊權(quán)。要求圖G的從源頂點s到目標頂點t之間的最短路徑。

11/6/202284單源最短路徑問題下圖是用優(yōu)先隊列式分支限界法解有向圖G的單源最短路徑問題產(chǎn)生的解空間樹。其中，每一個結(jié)點旁邊的數(shù)字表示該結(jié)點所對應(yīng)的當前路長。11/6/202285CH7

隨機

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

11/6/202290流,流量,最大流sv1v3v2v4t11/168/13101/412/1215/204/47/74/911/14稱f:VVR為流,若f滿足：(1)容量限制,f(u,v)c(u,v)(2)反對稱性,f(u,v)=-f(v,u)(3)流守恒性,任意uV\{s,t},vVf(u,v)=0流量|f|=vVf(s,v).

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

max{|f|:f是G的流}11/6/202291流網(wǎng)絡(luò)的割割(S,T):(1)T=V-S(2)sS,tT.f(S,T)=uS,vTf(u,v):f穿過割(S,T)的凈流c(S,T)=uS,vTc(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的增廣路徑,增大流,無則停止,得最大流11/6/202293計算理論

11/6/202294CH1集合、關(guān)系與語言

11/6/202295數(shù)學(xué)歸納法鴿巢原理

對角化原理1.5三個基本的證明技術(shù)11/6/202296字母表字符串空串:e或者ε.∑*

:字母表∑上所有字符串(包括空串)的集合.1.7字母表與語言11/6/202297連接:xo

y

或者xy

反轉(zhuǎn).

xR

(wx)R=xRwR1.7字母表與語言11/6/202298字母表∑上滿足一定條件的字符串的集合L，稱為∑上的一種語言。L*:連接L中0個或多個字符串得到的所有字符串的集合.L+:連接L中1個或多個字符串得到的所有字符串的集合.1.7字母表與語言11/6/202299正則運算

并:AB

連接:AB={xy|xA且yB}

星號:A*={x1x2…xk|k0且每個xiA}1.8語言的有窮表示11/6/2022100正則表達式:稱R為正則表達式,若R是

1)a,a;2);3);4)(R1R2),這里R1和R2是正則表達式;5)(R1R2),這里R1和R2是正則表達式;6)(R1*),這里R1是正則表達式;