計(jì)算理論與算法總復(fù)習(xí)

計(jì)算理論與算法總復(fù)習(xí)2024/7/122

of158成績(jī)計(jì)算方法平時(shí)成績(jī)30%上機(jī)題目平時(shí)作業(yè)平時(shí)考勤期末成績(jī)70%算法題中，嚴(yán)格按照題目要求給出算法代碼、算法思想、測(cè)試用例的求解過(guò)程。如果題目沒(méi)有明確要求給出算法代碼，那么不需要給出。2024/7/123

of158考題類型判斷題：10分.5個(gè)填空題：30分.10個(gè)大題：60分.5道CH1算法概述2024/7/125

of158算法的五個(gè)特征1）有窮性2）確定性3）輸入4）輸出5）可行性算法的定義:Informally,analgorithmisanywell-definedcomputationalprocedurethattakessomevalue,orsetofvalues,asinputandproducessomevalue,orsetofvalues,asoutput.Analgorithmisthusasequenceofcomputationalstepsthattransformtheinputintotheoutput.

2024/7/126

of158O、o、

、

、

第一種理解方法設(shè)f和g是定義域?yàn)樽匀粩?shù)N上的函數(shù)f(n)=O(g(n)).

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

n0

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

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

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

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

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

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

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

f(n)=O(g(n))且f(n)=(g(n))2024/7/127

of158O、o、

、

、

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

n,g(n)=n,則lg

n=o(n)o

2024/7/128

of158標(biāo)準(zhǔn)復(fù)雜性函數(shù)的比較O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)<O(2n)<O(n!)<O(nn)多項(xiàng)式時(shí)間階指數(shù)時(shí)間階一個(gè)算法的時(shí)間復(fù)雜性如果是O(nk)(k為有理數(shù)），則稱此算法需要多項(xiàng)式時(shí)間。有效算法以多項(xiàng)式時(shí)間為限界的算法稱為有效算法2024/7/129

of158標(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）不能劃等號(hào)2）以下若無(wú)特殊聲明，log是以2為底的對(duì)數(shù)3）上式只有在n較大的時(shí)候成立O(1)的含義？計(jì)算時(shí)間由一個(gè)常數(shù)（零次多項(xiàng)式）來(lái)限界多項(xiàng)式時(shí)間階指數(shù)時(shí)間階2024/7/1210

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

104

2024/7/1211

of158例假設(shè)某算法在輸入規(guī)模為n的時(shí)間復(fù)雜性為T(mén)(n)=3*2n。在某臺(tái)計(jì)算機(jī)上實(shí)現(xiàn)并完成該算法的時(shí)間為t秒。現(xiàn)在另一計(jì)算機(jī)，其運(yùn)行速度為第一臺(tái)的64倍，那么在這臺(tái)新機(jī)器上用同一算法在t秒內(nèi)能解輸入規(guī)模為多大的問(wèn)題？2024/7/1212

of158例解：設(shè)新機(jī)器用同一算法內(nèi)能解輸入規(guī)模為n1的問(wèn)題，那么有3*2n=3*2n1/64，解得n1=n+6.CH2分治法

2024/7/1214

of158例1用分治法求n個(gè)元素集合S中的最大、最小元素。假設(shè)n=2m。要求每次平分成2個(gè)子集。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.}2024/7/1215

of15814.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)+22024/7/1216

of158

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

=3n/2-22024/7/1217

of158歸并排序（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)+cn12024/7/1218

of158主定理：其中n=ck,k為某個(gè)非負(fù)常數(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)+22024/7/1219

of158快排序---劃分過(guò)程

3865977613274949lowhighpivot=49

01234567high38659776134927low27389776134965high27389776654913low27381376654997high49=low2024/7/1220

of158大整數(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計(jì)算成本：3次n/2位乘法，6次不超過(guò)n位加減法，2次移位，所有加法和移位共計(jì)O(n)次運(yùn)算。由此可得，T(n)=O(nlog3)=O(n1.59)這種思想同樣可以用于十進(jìn)制數(shù)的乘法中。2024/7/1221

of158求第k小的元素longSelect(k,S){if(|S|≤38){將S中的元素排成非遞減序；

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

{

將S中的元素劃分成長(zhǎng)度等于5的

|S|/5

個(gè)子序列；2024/7/1222

of158

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

m←Select(

|M|/2

，M);

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

m和大于m的三個(gè)子序列S1，S2和S3;if(|S1|>k)return(Select(k,S1));elseif(|S1|+|S2|≥k)return(m);elsereturn(Select(k-|S1|-|S2|,S3));}}2024/7/1223

of158線性時(shí)間選擇問(wèn)題:定理：算法Select在O(n)時(shí)間內(nèi)找出n個(gè)元素序列中的第k小的元素。

cn≤38T(

n/5

)+T(

3n/4

)+cnn>38T(n)≤T(n)=20cn用線性時(shí)間從n個(gè)元素中選擇出第k個(gè)小的元素2024/7/1224

of158線性時(shí)間選擇:中位數(shù)應(yīng)用中位數(shù)原理X軸上有n個(gè)點(diǎn)，由左至右依次排列為找一個(gè)點(diǎn)xp(不一定是n個(gè)點(diǎn)之一)，使xp到各點(diǎn)距離和最小，解為：x1x2xpxnx即解為中位數(shù)或中位數(shù)的平均值。2024/7/1225

of158【例】殘缺棋盤(pán)殘缺棋盤(pán)是一個(gè)有2k×2k

（k≥1）個(gè)方格的棋盤(pán)，其中恰有一個(gè)方格殘缺。圖中給出k=1時(shí)各種可能的殘缺棋盤(pán)，其中殘缺的方格用陰影表示。

稱作“三格板”，殘缺棋盤(pán)問(wèn)題就是要用這四種三格板覆蓋更大的殘缺棋盤(pán)。①號(hào)②號(hào)③號(hào)④號(hào)2024/7/1226

of158問(wèn)題分解過(guò)程：以k=2時(shí)的問(wèn)題為例，用二分法進(jìn)行分解，得到如下圖，用雙線劃分的四個(gè)k=1的棋盤(pán)。①號(hào)②號(hào)③號(hào)④號(hào)2024/7/1227

of158循環(huán)賽日程表設(shè)計(jì)一個(gè)滿足以下要求的比賽日程表：(1)每個(gè)選手必須與其他n-1個(gè)選手各賽一次；(2)每個(gè)選手一天只能賽一次；(3)循環(huán)賽一共進(jìn)行n-1天。按分治策略，將所有的選手分為兩半，n個(gè)選手的比賽日程表就可以通過(guò)為n/2個(gè)選手設(shè)計(jì)的比賽日程表來(lái)決定。遞歸地用對(duì)選手進(jìn)行分割，直到只剩下2個(gè)選手時(shí)，比賽日程表的制定就變得很簡(jiǎn)單。這時(shí)只要讓這2個(gè)選手進(jìn)行比賽就可以了。2024/7/1228

of158循環(huán)賽日程表加4加2(a)2k(k=1)個(gè)選手比賽122112213443344312211234214334124321567865877856876556786587785687651234214334124321(b)2k(k=2)個(gè)選手比賽(c)2k(k=3)個(gè)選手比賽2024/7/1229

of158循環(huán)賽日程表的推廣設(shè)計(jì)一個(gè)滿足以下要求的比賽日程表：(1)每個(gè)選手必須與其他n-1個(gè)選手各賽一次；(2)每個(gè)選手一天只能賽一次；(3)n為偶數(shù)時(shí)，循環(huán)賽一共進(jìn)行n-1天。

n為奇數(shù)時(shí)，循環(huán)賽一共進(jìn)行n天。CH3動(dòng)歸

2024/7/1231

of158方法概述:基本思想動(dòng)態(tài)規(guī)劃的思想實(shí)質(zhì)是分治思想和解決冗余。與分治法類似的是，將原問(wèn)題分解成若干個(gè)子問(wèn)題，先求解子問(wèn)題，然后從這些子問(wèn)題的解得到原問(wèn)題的解。與分治法不同的是，經(jīng)分解的子問(wèn)題往往不是互相獨(dú)立的。若用分治法來(lái)解，有些共同部分（子問(wèn)題或子子問(wèn)題）被重復(fù)計(jì)算了很多次。2024/7/1232

of158方法概述:適用條件

動(dòng)態(tài)規(guī)劃法的有效性依賴于問(wèn)題本身所具有的兩個(gè)重要性質(zhì)最優(yōu)子結(jié)構(gòu)：當(dāng)問(wèn)題的最優(yōu)解包含了其子問(wèn)題的最優(yōu)解時(shí)，稱該問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。重疊子問(wèn)題：在用遞歸算法自頂向下解問(wèn)題時(shí)，每次產(chǎn)生的子問(wèn)題并不總是新問(wèn)題，有些子問(wèn)題被反復(fù)計(jì)算多次。動(dòng)態(tài)規(guī)劃算法正是利用了這種子問(wèn)題的重疊性質(zhì)，對(duì)每一個(gè)子問(wèn)題只解一次，而后將其解保存在一個(gè)表格中，在以后盡可能多地利用這些子問(wèn)題的解。2024/7/1233

of158多段圖的最短路問(wèn)題123456789101112s97324212711118654356425V1V2V3V4V5t2024/7/1234

of158多段圖的最短路問(wèn)題假設(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)化原理成立。2024/7/1235

of158cost(i,j)=min{C(j,r)+cost(i+1,r)}

r∈Vi+1<j,r>∈EjrtViVi+1最短最短向前處理法：設(shè)P(i,j)是從Vi中的點(diǎn)j到t的一條最短路，cost(i,j)是這條路線的耗費(fèi)。由后向前推算，得到2024/7/1236

of158筆試題2024/7/1237

of158筆試題2024/7/1238

of158筆試題2024/7/1239

of158矩陣鏈乘法矩陣鏈乘問(wèn)題滿足最優(yōu)性原理記A[i:j]為AiAi+1…Aj鏈乘的一個(gè)最優(yōu)括號(hào)方案，設(shè)A[i:j]的最優(yōu)次序中含有二個(gè)子鏈A[i:k]和A[k+1:n]，則A[i:k]和A[k+1:n]也是最優(yōu)的。（反證可得）2024/7/1240

of158遞歸求解最優(yōu)解的值記m[i][j]為計(jì)算A[i:j]的最少乘法數(shù)，則原問(wèn)題的最優(yōu)值為

m[1][n](AiAi+1…Ak)pi-1×pk×(Ak+1Ak+2…Aj)pk×pj2024/7/1241

of158貨物儲(chǔ)運(yùn)問(wèn)題在一個(gè)鐵路沿線順序存放著n堆裝滿貨物的集裝箱。貨物儲(chǔ)運(yùn)公司要將集裝箱有次序地集中成一堆。規(guī)定每次只能選相鄰的2堆集裝箱合并成新的一堆，所需的運(yùn)輸費(fèi)用與新的一堆中集裝箱數(shù)成正比。給定各堆的集裝箱數(shù)，試制定一個(gè)運(yùn)輸方案，使總運(yùn)輸費(fèi)用最少。5,3,4,1,3,2,3,4設(shè)合并a[i:j]，1≤i≤j≤n，所需的最少費(fèi)用為m[i,j]，則原問(wèn)題的最優(yōu)值為m[1，n]。由最優(yōu)子結(jié)構(gòu)性質(zhì)可知，2024/7/1242

of1580-1背包問(wèn)題00000pi–1(j–wi)pi–1(j)0pi(j)0目標(biāo)

0i–1in0j–wi

jM2024/7/1243

of158最長(zhǎng)公共子序列的結(jié)構(gòu)設(shè)序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最長(zhǎng)公共子序列為Z={z1,z2,…,zk}，則(1)若xm=yn，則zk=xm=yn，

且z1,z2,…,zk-1是否為x1,x2,…,xm-1和y1,y2,…,yn-1的最長(zhǎng)公共子序列。(2)若xm≠yn且zk≠xm，則Z是x1,x2,…,xm-1和Y的最長(zhǎng)公共子序列(3)若xm≠yn且zk≠yn，則Z是X和y1,y2,…,yn-1的最長(zhǎng)公共子序列2024/7/1244

of158子問(wèn)題的遞歸結(jié)構(gòu)由最長(zhǎng)公共子序列問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)建立子問(wèn)題最優(yōu)值的遞歸關(guān)系。用c[i][j]記錄序列和的最長(zhǎng)公共子序列的長(zhǎng)度。其中，Xi={x1,x2,…,xi}；Yj={y1,y2,…,yj}。當(dāng)i=0或j=0時(shí)，空序列是Xi和Yj的最長(zhǎng)公共子序列。故此時(shí)C[i][j]=0。其它情況下，由最優(yōu)子結(jié)構(gòu)性質(zhì)可建立遞歸關(guān)系如下：CH4貪心法2024/7/1246

of158部分(或者小數(shù))背包問(wèn)題

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

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

(w1,w2,w3)=(18,15,10)2024/7/1247

of158n=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.52024/7/1248

of158活動(dòng)安排:問(wèn)題描述有n個(gè)活動(dòng)集E={1,2,…,n}使用同一資源，而同一時(shí)間內(nèi)同一資源只能由一個(gè)活動(dòng)使用。每個(gè)活動(dòng)的使用時(shí)間為[si,fi)i=1,…,n，si為開(kāi)始時(shí)間，fi為結(jié)束時(shí)間，若[si,fi)與[sj,fj)不相交稱活動(dòng)i和活動(dòng)j是相容的。問(wèn)題：選出最大的相容活動(dòng)子集合。2024/7/1249

of158貪心策略將各活動(dòng)按結(jié)束時(shí)間排序f1≤f2≤…≤fn，先選出活動(dòng)1，然后按活動(dòng)編好從小到大的次序依次選擇與當(dāng)前活動(dòng)相容的活動(dòng)。2024/7/1250

of158活動(dòng)安排:計(jì)算示例11個(gè)活動(dòng)已按結(jié)束時(shí)間排序，用貪心算法求解：

i1234567891011start_timei

130535688212finish_timei

456789101112131401234567891011121314timea1a2a3a4a5a6a7a8a9a10a11相容活動(dòng)：{a3,a9,a11},{a1,a4,a8,a11},{a2,a4,a9,a11}01234567891011121314timea1a2a3a4a5a6a7a8a9a10a112024/7/1251

of158有限期的任務(wù)安排問(wèn)題用貪心法求解有限期的任務(wù)安排問(wèn)題：假設(shè)只能在同一臺(tái)機(jī)器上加工n個(gè)任務(wù)，每個(gè)任務(wù)i完成時(shí)間均是一個(gè)單位時(shí)間。又設(shè)每個(gè)任務(wù)i都有一個(gè)完成期限di>0,當(dāng)且僅當(dāng)任務(wù)i在它的期限截止以前被完成時(shí)，任務(wù)i才能獲得pi的效益，每個(gè)任務(wù)的期限從整個(gè)工序的開(kāi)工開(kāi)始計(jì)時(shí)，問(wèn)應(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)2024/7/1252

of158有限期的任務(wù)安排問(wèn)題

首先按效益非增次序進(jìn)行排序，然后按照期限依次對(duì)此次序進(jìn)行調(diào)整，排在后面的或提前或排除。2024/7/1253

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

任務(wù)0123456

pi030252015105

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

總效益：902024/7/1254

of158最優(yōu)裝載2024/7/1255

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

從剩下的貨箱中，選擇重量最小的貨箱。2024/7/1256

of158排序之車(chē)間作業(yè)計(jì)劃模型一：一臺(tái)機(jī)器、n個(gè)零件的排序

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

時(shí)間最短。零件加工時(shí)間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.82024/7/1257

of158排序之車(chē)間作業(yè)計(jì)劃模型二：兩臺(tái)機(jī)器、n個(gè)零件的排序目的：使得完成全部工作的總時(shí)間最短?；痉椒ǎ涸诘谝慌_(tái)機(jī)器上加工時(shí)間越少的零件越早加工；在第二臺(tái)機(jī)器上加工時(shí)間越少的零件越晚加工；2024/7/1258

of158某車(chē)間需要用一臺(tái)車(chē)床和一臺(tái)銑床加工A、B、C、D

四個(gè)零件。每個(gè)零件都需要先用車(chē)床加工，再用銑床

加工。車(chē)床和銑床加工每個(gè)零件所需的工時(shí)（包括

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

小時(shí)。

26BADC

2024/7/1259CH5回溯法

2024/7/1260

of1582024/7/1260

of158子集樹(shù)與排列樹(shù)遍歷子集樹(shù)需O(2n)計(jì)算時(shí)間

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

x[t]=i;if(legal(t))backtrack(t+1);}}2024/7/1261

of1582024/7/1261

of158子集樹(shù)與排列樹(shù)遍歷排列樹(shù)需要O(n!)計(jì)算時(shí)間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]);}}2024/7/1262

of1582024/7/1262

of1584后問(wèn)題設(shè)有一4*4的棋盤(pán)，把4個(gè)皇后放在棋盤(pán)上，要求滿足下列兩個(gè)條件：1）任意兩個(gè)皇后不在同一行上和同一列上；2）任意兩個(gè)皇后不在同一條對(duì)角線上；問(wèn)有多少種放法？2024/7/1263

of1582024/7/1263

of15812347568109x1=1x2=23424233BBBBB111213141516x1=2BB134132024/7/1264

of158裝載問(wèn)題有一批共n個(gè)集裝箱要裝上2艘載重量分別為c1和c2的輪船，其中集裝箱i的重量為wi，且裝載問(wèn)題要求確定是否有一個(gè)合理的裝載方案可將這個(gè)集裝箱裝上這2艘輪船。如果有，找出一種裝載方案。最優(yōu)裝載方案:(1)首先將第一艘輪船盡可能裝滿；(2)將剩余的集裝箱裝上第二艘輪船。2024/7/1265

of158問(wèn)題分析將第一艘輪船盡可能裝滿等價(jià)于選取全體集裝箱的一個(gè)子集，使該子集中集裝箱重量之和最接近。由此可知，裝載問(wèn)題等價(jià)于以下特殊的0-1背包問(wèn)題。2024/7/1266

of158算法設(shè)計(jì)解空間：子集樹(shù)可行性約束函數(shù)(選擇當(dāng)前元素)：上界函數(shù)當(dāng)前載重量cw+剩余集裝箱的重量r

當(dāng)前最優(yōu)載重量bestw2024/7/1267

of158算法設(shè)計(jì)上界函數(shù)：用于剪去不含最優(yōu)解的子樹(shù)，從而提高算法在平均情況下的運(yùn)行效率。設(shè)Z是解空間樹(shù)第i層上的當(dāng)前擴(kuò)展結(jié)點(diǎn)，cw是當(dāng)前載重量，R是剩余集裝箱的重量，bestW是當(dāng)前最優(yōu)載重量，則當(dāng)

cw+r≤bestW時(shí)，剪去Z的右子樹(shù)。2024/7/1268

of158裝載問(wèn)題解空間：子集樹(shù)可行性約束函數(shù)(選擇當(dāng)前元素)：上界函數(shù)(不選擇當(dāng)前元素)：當(dāng)前載重量cw+剩余集裝箱的重量r

當(dāng)前最優(yōu)載重量bestwprivatestaticvoidbacktrack(inti){//搜索第i層結(jié)點(diǎn)

if(i>n){//到達(dá)葉結(jié)點(diǎn)

//更新最優(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){//搜索左子樹(shù)

x[i]=1;

cw+=w[i];

backtrack(i+1);

cw-=w[i];}

if(cw+r>bestw){x[i]=0;//搜索右子樹(shù)

backtrack(i+1);}r+=w[i];}2024/7/1269

of158最大團(tuán)問(wèn)題給定無(wú)向圖G=(V，E)。如果U

V，且對(duì)任意u，v

U有(u，v)

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

V且對(duì)任意u，v

U有(u，v)

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

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

E。U是G的最大團(tuán)當(dāng)且僅當(dāng)U是G的最大獨(dú)立集。12453124532024/7/1270

of158最大團(tuán)問(wèn)題解空間：子集樹(shù)可行性約束函數(shù)：頂點(diǎn)i到已選入的頂點(diǎn)集中每一個(gè)頂點(diǎn)都有邊相連。上界函數(shù)：有足夠多的可選擇頂點(diǎn)使得算法有可能在右子樹(shù)中找到更大的團(tuán)。privatestaticvoidbacktrack(inti){if(i>n){//到達(dá)葉結(jié)點(diǎn)

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

bestn=cn;return;}//檢查頂點(diǎn)i與當(dāng)前團(tuán)的連接

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

ok=false;break;}if(ok){//進(jìn)入左子樹(shù)

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

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

x[i]=0;backtrack(i+1);}}}124532024/7/1271

of1582024/7/1271

of158子集和問(wèn)題問(wèn)題給定由n個(gè)不同正數(shù)組成的集合W={wi}，和正數(shù)M，求W中所有和等于M的子集的集合；例如n=6,M=30,

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

2024/7/1272

of1582024/7/1272

of158子集和問(wèn)題按照回溯法思想，從狀態(tài)樹(shù)的根結(jié)點(diǎn)出發(fā)，做深度優(yōu)先搜索；當(dāng)在某一狀態(tài)A下，依次嘗試加入和不加入正數(shù)wi，若∑A+wi>M，則可停止對(duì)該結(jié)點(diǎn)的搜索；若∑A+∑(wi…wn)<M，則也可停止對(duì)該結(jié)點(diǎn)的搜索；2024/7/1273

of1582024/7/1273

of1580/1背包問(wèn)題

且

2024/7/1274

of1582024/7/1274

of158有載重量M＝50的背包，物體重量分別為5,15,25,27,30，物體價(jià)值分別為12,30,44,46,50。求最優(yōu)裝入背包的物體及價(jià)值。2024/7/1275

of1582024/7/1275

of158回溯過(guò)程的效率用回溯法去處理一實(shí)例所要生成的結(jié)點(diǎn)數(shù)，一般是采用在狀態(tài)空間樹(shù)中生成一條隨機(jī)路徑的方法估計(jì)。2024/7/1276CH6分支限界法

2024/7/1277

of1582024/7/1277

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

2024/7/1278

of1582024/7/1278

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

2024/7/1279

of1582024/7/1279

of158方法概述:示例1示例1（FIFO隊(duì)列分枝限界法）問(wèn)題：0-1背包問(wèn)題:物品數(shù)n=3,重量w=(20,15,15),價(jià)值v=(40,25,25),背包容量c=30,試裝入最大價(jià)值之和的物品?求解：

①解空間:{(0,0,0),(0,0,1),…,(1,1,1)}②解空間樹(shù):DBHAIEJKFCLMGNO111111100000002024/7/1280

of1582024/7/1280

of158方法概述:示例1③BFS搜索（FIFO隊(duì)列）

擴(kuò)展結(jié)點(diǎn)活結(jié)點(diǎn)隊(duì)列(可行結(jié)點(diǎn))可行解(葉結(jié)點(diǎn))解值

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

∴最優(yōu)解為L(zhǎng),即(0,1,1);解值為50DBHAIEJKFCLMGNO11111110000000w=(20,15,15),v=(40,25,25),c=302024/7/1281

of1582024/7/1281

of158方法概述:示例2示例2（優(yōu)先隊(duì)列分枝限界法）問(wèn)題：0-1背包問(wèn)題:物品數(shù)n=3,重量w=(20,15,15),價(jià)值v=(40,25,25),背包容量c=30,試裝入最大價(jià)值之和的物品?求解：

①解空間:{(0,0,0),(0,0,1),…,(1,1,1)}②解空間樹(shù):DBHAIEJKFCLMGNO111111100000002024/7/1282

of1582024/7/1282

of158方法概述:示例2BFS搜索（優(yōu)先隊(duì)列：按價(jià)值率優(yōu)先）

擴(kuò)展結(jié)點(diǎn)活結(jié)點(diǎn)堆(可行結(jié)點(diǎn))可行解(葉結(jié)點(diǎn))解值

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

FL,ML

50(最優(yōu))GN,OφBCECFGCGDBHAIEJKFCLMGNO11111110000000w=(20,15,15),v=(40,25,25),c=302024/7/1283

of1582024/7/1283

of158分配問(wèn)題分配問(wèn)題：設(shè)有n個(gè)人，每個(gè)人都可以完成n種不同的任務(wù)，但所需時(shí)間不同。如果只需一人去完成每一項(xiàng)工作，則應(yīng)如何分配n個(gè)人并使完成所有n項(xiàng)工作的總時(shí)間為最小。2024/7/1284

of158單源最短路徑問(wèn)題問(wèn)題描述單源最短路徑問(wèn)題：在下圖所給的有向圖G中，每一邊都有一個(gè)非負(fù)邊權(quán)。要求圖G的從源頂點(diǎn)s到目標(biāo)頂點(diǎn)t之間的最短路徑。

2024/7/1285

of158單源最短路徑問(wèn)題

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

隨機(jī)

2024/7/1287

of1582024/7/1287

of158定義：在算法中引入隨機(jī)因素,即通過(guò)隨機(jī)數(shù)選擇算法的下一步操作。特點(diǎn)：簡(jiǎn)單、快速一種平衡：隨機(jī)算法可以理解為在時(shí)間、空間和隨機(jī)三大計(jì)算資源中的平衡2024/7/1288

of1582024/7/1288

of1581、數(shù)值概率算法：用于數(shù)值問(wèn)題的求解2、Sherwood算法一定能得到問(wèn)題的正確解常見(jiàn)的四類隨機(jī)算法：2024/7/1289

of1582024/7/1289

of1583、LasVegas算法或者得到正確的解，或者得不到解。4、MonteCarlo算法一定能得到解，但是得到的解可能不正確，然而這種概率是小的且有界的。常見(jiàn)的四類隨機(jī)算法：網(wǎng)絡(luò)流

2024/7/1291

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

V

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

c(u,v)(2)反對(duì)稱性,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的流}流網(wǎng)絡(luò)的割割(S,T):(1)T=V-S(2)sS,t

T.f(S,T)=

u

S,v

Tf(u,v):f穿過(guò)割(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.2024/7/1293

of220最大流最小割定理

f(S,T)=|f|,|f|

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

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

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

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

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

最大流算法基本思想:

找從s到t的增廣路徑,增大流,無(wú)則停止,得最大流計(jì)算理論

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

2024/7/1296

of158

數(shù)學(xué)歸納法鴿巢原理

對(duì)角化原理1.5三個(gè)基本的證明技術(shù)2024/7/1297

of158字母表字符串空串:e或者ε.∑*

:字母表∑上所有字符串(包括空串)的集合.1.7字母表與語(yǔ)言2024/7/1298

of158連接:xo

y

或者xy

反轉(zhuǎn).

xR

(wx)R=xRwR1.7字母表與語(yǔ)言2024/7/1299

of158字母表∑上滿足一定條件的字符串的集合L，稱為∑上的一種語(yǔ)言。L*:連接L中0個(gè)或多個(gè)字符串得到的所有字符串的集合.L+:連接L中1個(gè)或多個(gè)字符串得到的所有字符串的集合.1.7字母表與語(yǔ)言2024/7/12100

of158正則運(yùn)算

并:AB

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

星號(hào):A*={x1x2…xk|k0且每個(gè)xiA}1.8語(yǔ)言的有窮表示2024/7/12101

of158正則表達(dá)式:稱R為正則表達(dá)式,若R是

1)a,a;2);3);4)(R1R2),這里R1和R2是正則表達(dá)式;5)(R1R2),這里R1和R2是正則表達(dá)式;6)(R1*),這里R1是正則表達(dá)式;每個(gè)正則表達(dá)式R表示一個(gè)語(yǔ)言,記為L(zhǎng)(R).1.8語(yǔ)言的