算法分析與設(shè)計(jì)-復(fù)習(xí)提綱課件

算法分析與設(shè)計(jì)常熟理工學(xué)院計(jì)算機(jī)學(xué)院劉在德算法分析與設(shè)計(jì)常熟理工學(xué)院計(jì)算機(jī)學(xué)院1第1章緒論掌握三種漸近符號(hào)（O、Ω、Θ）的含義；會(huì)用三種漸近符號(hào)表示算法的時(shí)間復(fù)雜度；會(huì)用擴(kuò)展遞歸技術(shù)分析算法時(shí)間的復(fù)雜性；對(duì)于表示算法時(shí)間的簡(jiǎn)單遞推式，能夠用擴(kuò)展遞歸技術(shù)求出最終結(jié)果。P15：例1.6P18：實(shí)驗(yàn)1P22：習(xí)題1.7第1章緒論掌握三種漸近符號(hào)（O、Ω、Θ）的含義；2三種漸近符號(hào)的含義大O符號(hào)：若存在兩個(gè)正的常數(shù)c和n0，對(duì)于任意n≥n0，都有T(n)≤c×f(n)，則稱(chēng)T(n)=O(f(n))

大Ω符號(hào)：若存在兩個(gè)正的常數(shù)c和n0，對(duì)于任意n≥n0，都有T(n)≥c×g(n)，則稱(chēng)T(n)=Ω(g(n))Θ符號(hào)：若存在三個(gè)正的常數(shù)c1、c2和n0，對(duì)于任意n≥n0都有c1×f(n)≥T(n)≥c2×f(n)，則稱(chēng)T(n)=Θ(f(n))

三種漸近符號(hào)的含義大O符號(hào)：若存在兩個(gè)正的常數(shù)c和n0，對(duì)于3漸近符號(hào)表示算法時(shí)間復(fù)雜度[定理1.1]若T(n)=amnm+am-1nm-1+···a1n+a0(am>0)，則有T(n)=O(nm)，且T(n)=Ω(nm)，從而T(n)=Θ(nm)[例]

T(n)＝5n2＋8n＋1

當(dāng)n≥1時(shí)，5n2＋8n＋1≤5n2＋8n＋n＝5n2＋9n≤5n2＋9n2≤14n2＝O(n2)

當(dāng)n≥1時(shí)，5n2＋8n＋1≥5n2＝Ω(n2)

∴當(dāng)n≥1時(shí)，14n2≥5n2＋8n＋1≥5n2

則：5n2＋8n＋1＝Θ(n2)

漸近符號(hào)表示算法時(shí)間復(fù)雜度[定理1.1]若T(n)=am4用擴(kuò)展遞歸技術(shù)分析算法時(shí)間的復(fù)雜性擴(kuò)展遞歸技術(shù)：將遞推關(guān)系式中右邊項(xiàng)根據(jù)遞推式進(jìn)行逐次替換，得到求和表達(dá)式[例]

用擴(kuò)展遞歸技術(shù)分析算法時(shí)間的復(fù)雜性擴(kuò)展遞歸技術(shù)：將遞推關(guān)系式5第2章NP完全理論對(duì)于簡(jiǎn)單的判定問(wèn)題，會(huì)畫(huà)判定樹(shù)。判定樹(shù)（DecisionTrees）是一棵二叉樹(shù)：它的每一個(gè)內(nèi)部結(jié)點(diǎn)對(duì)應(yīng)一個(gè)形如x≤y的比較，如果關(guān)系成立，則控制轉(zhuǎn)移到該結(jié)點(diǎn)的左子樹(shù)，否則，控制轉(zhuǎn)移到該結(jié)點(diǎn)的右子樹(shù)，它的每一個(gè)葉子結(jié)點(diǎn)表示問(wèn)題的一個(gè)結(jié)果。

第2章NP完全理論對(duì)于簡(jiǎn)單的判定問(wèn)題，會(huì)畫(huà)判定樹(shù)。6[例]對(duì)三個(gè)數(shù)進(jìn)行排序的判定樹(shù)[例]對(duì)三個(gè)數(shù)進(jìn)行排序的判定樹(shù)7第3章蠻力法掌握改進(jìn)的串匹配算法——KMP算法理解n個(gè)元素的生成排列對(duì)象理解n個(gè)元素組成的集合的生成子集理解0/1背包問(wèn)題理解TSP問(wèn)題第3章蠻力法掌握改進(jìn)的串匹配算法——KMP算法8KMP算法KMP算法思路：如果某趟在Si和Tj匹配失敗后，指針i不回溯；模式T向右滑動(dòng)至某個(gè)位置k，使得tk對(duì)準(zhǔn)si繼續(xù)進(jìn)行匹配。怎么求k？模式T=“t1t2…tm”中的每一個(gè)字符tj都對(duì)應(yīng)一個(gè)k，顯然k與S無(wú)關(guān)。用next[j]表示tj對(duì)應(yīng)的k值，則t1…tk-1既是t1…tj-1的真前綴，又是t1…tj-1的真后綴的最長(zhǎng)子串，稱(chēng)k是tj的前綴函數(shù)值，它等于最長(zhǎng)子串長(zhǎng)度加1。KMP算法KMP算法思路：9next數(shù)組的定義next數(shù)組定義如下：t1t2t3t4t5t6ababac真前綴真后綴∵t1=t5,t1t2t3=t3t4t5∴a和aba都是ababa的真前綴和真后綴，但aba的長(zhǎng)度最大∴next[6]=3+1=4，即當(dāng)t6和si匹配失敗后，將t4和si比較一個(gè)求k的例子：next數(shù)組的定義next數(shù)組定義如下：t1t2t3t4t510next數(shù)組的求法：已求出next[1],…,next[j]，咋求next[j+1]?設(shè)k是t[j]的前綴函數(shù)值，從而有

t1…t2tk-1=tj-k+1tj-k+2…tj-1比較tk和tj，得2種情況：(1)tk=tj：說(shuō)明t1…tk-1tk=tj-k+1…tj-1tj，則next[j+1]=k+1；(2)tk≠tj：此時(shí)要找出t1…tj-1的后綴中第2大真前綴next[next[j]]=next[k],t1…tnext[k]-1=tj-next[k]+1…tj-1，再比較tnext[k]和tj，又會(huì)出現(xiàn)2種情況：next數(shù)組的求法：已求出next[1],…,next[j11next數(shù)組的求法：當(dāng)tnext[k]=tj時(shí)，與(1)類(lèi)似，next[j+1]=next[k]+1；當(dāng)不等時(shí)，找第3大真前綴，重復(fù)(2)的過(guò)程，直至找到t1…tj-1后綴中的最大真前綴，或確定t1…tj-1的后綴中沒(méi)有最大真前綴，此時(shí)next[j+1]=1。next數(shù)組的求法：當(dāng)tnext[k]=tj時(shí)，與(1)類(lèi)似12算法3.4KMP算法中求next數(shù)組voidGetNext(charT[],intnext[])

{//下標(biāo)從1開(kāi)始next[1]=0;j=1;k=0;while(j<=m)If((k==0)||(T[j]==T[k])){j++;k++;next[j]=k;}elsek=next[k]}算法3.4KMP算法中求next數(shù)組voidGetNe13算法3.5KMP算法1.在串S和T中分別設(shè)定比較的起始下標(biāo)i和j；2.循環(huán)直到S中所剩字符長(zhǎng)度小于T的長(zhǎng)度或T中所有字符均比較完畢2.1如S[i]=T[j]，則繼續(xù)比較S和T的下一字符；否則2.2將j向右滑動(dòng)到next[j]位置，即j=next[j]；2.3如果j=0，則將i和j分別加1，準(zhǔn)備下一趟比較；3.如果T中所有字符均比較完畢，則返回匹配的起始下標(biāo)，否則返回0。算法3.5KMP算法1.在串S和T中分別設(shè)定比較的起始14生成排列對(duì)象思路：假定已生成了{(lán)1,2,…,n-1}的所有(n-1)!個(gè)排列，可以把n插入到n-1個(gè)元素的每一種排列的n個(gè)位置中去，得到問(wèn)題規(guī)模為n的所有排列。這時(shí)排列總數(shù)為n(n-1)!=n!。時(shí)間復(fù)雜性：O(n!)算法3.9生成排列對(duì)象（偽代碼）1.生成初始排列{1}；2.for(i=2;i<=n;i++)for(j=1;j<=(i-1)!;j++)for(k=i;k>=1;k--)

將i插入到第j個(gè)排列中的第k個(gè)位置；生成排列對(duì)象思路：假定已生成了{(lán)1,2,…,n-1}的所有(15生成子集思路：n個(gè)元素組成的集合A={a1,a2,…,an}的所有2n個(gè)子集與長(zhǎng)度為n的所有2n個(gè)比特串之間存在一一對(duì)應(yīng)關(guān)系。建立這種關(guān)系的方法是為每個(gè)子集指定一個(gè)比特串b1b2…bn，如果ai屬于該子集，則bi=1，否則bi=0(1≤i≤n)。如3個(gè)元素組成的集合，比特串110表示{a1a2}，比特串000表示Φ。生成子集思路：n個(gè)元素組成的集合A={a1,a2,…,an}16算法3.10生成子集1.初始化一個(gè)長(zhǎng)度為n的比特串s=00…0，并將對(duì)應(yīng)的子集輸出；2.for(i=1;i<2n;i++)2.1s++;2.2將s對(duì)應(yīng)的子集輸出；時(shí)間復(fù)雜性：O(2n)。算法3.10生成子集1.初始化一個(gè)長(zhǎng)度為n的比特串s170/1背包問(wèn)題0/1背包問(wèn)題：給定n個(gè)重量為{w1,w2,…wn}、價(jià)值為{v1,v2,…,vn}的物品和1個(gè)容量為C的背包，求這些物品中的一個(gè)最有價(jià)值的子集，并能夠裝到背包中。思路：考慮給定n個(gè)物品集合的所有子集，找出所有可能的子集(總重量不超過(guò)背包容量的子集)，計(jì)算每個(gè)子集的價(jià)值，從中找出價(jià)值最大子集。0/1背包問(wèn)題0/1背包問(wèn)題：給定n個(gè)重量為{w1,w2,…18TSP問(wèn)題TSP問(wèn)題：旅行家要旅行n個(gè)城市然后回到出發(fā)城市，要求各個(gè)城市經(jīng)歷且僅經(jīng)歷一次，并要求所經(jīng)過(guò)的路程最短。思路：1)找出所有的Hamilton回路，并計(jì)算每個(gè)回路的路徑長(zhǎng)度；2)從中選擇路徑長(zhǎng)度最短的回路。TSP問(wèn)題TSP問(wèn)題：旅行家要旅行n個(gè)城市然后回到出發(fā)城市，19TSP問(wèn)題時(shí)間復(fù)雜性：(n-1)!/2(出發(fā)城市固定，實(shí)際旅游了n-1個(gè)城市)。例子：abdca11acdba11TSP問(wèn)題時(shí)間復(fù)雜性：(n-1)!/2(出發(fā)城市固定，實(shí)際20第4/5章分/減治法理解分治法的基本思路及在典型問(wèn)題中的應(yīng)用掌握遞歸方法在算法設(shè)計(jì)中的應(yīng)用。掌握減治法在經(jīng)典問(wèn)題中的應(yīng)用習(xí)題4.3習(xí)題4.4習(xí)題5.2第4/5章分/減治法理解分治法的基本思路及在典型問(wèn)題中21分治法的求解過(guò)程

一般來(lái)說(shuō)，分治法的求解過(guò)程由以下三個(gè)階段組成：（1）劃分：既然是分治，當(dāng)然需要把規(guī)模為n的原問(wèn)題劃分為k個(gè)規(guī)模較小的子問(wèn)題，并盡量使這k個(gè)子問(wèn)題的規(guī)模大致相同。（2）求解子問(wèn)題：各子問(wèn)題的解法與原問(wèn)題的解法通常是相同的，可以用遞歸的方法求解各個(gè)子問(wèn)題，有時(shí)遞歸處理也可以用循環(huán)來(lái)實(shí)現(xiàn)。（3）合并：把各個(gè)子問(wèn)題的解合并起來(lái)，合并的代價(jià)因情況不同有很大差異，分治算法的有效性很大程度上依賴(lài)于合并的實(shí)現(xiàn)。分治法的求解過(guò)程一般來(lái)說(shuō)，分治法的求解過(guò)程由以22子問(wèn)題的規(guī)模是n/2子問(wèn)題的解原問(wèn)題的解原問(wèn)題的規(guī)模是n減治法的設(shè)計(jì)思想子問(wèn)題子問(wèn)題的解23遞歸遞歸（Recursion）就是子程序（或函數(shù)）直接調(diào)用自己或通過(guò)一系列調(diào)用語(yǔ)句間接調(diào)用自己，是一種描述問(wèn)題和解決問(wèn)題的基本方法。遞歸有兩個(gè)基本要素：⑴邊界條件：確定遞歸到何時(shí)終止；⑵遞歸模式：大問(wèn)題是如何分解為小問(wèn)題的。遞歸遞歸（Recursion）就是子程序（或函數(shù)24一個(gè)遞歸和減治法混合應(yīng)用例子----俄式乘法習(xí)題5的第2題intrmul(intn,intm)/*方法1：遞歸法*/{inthalfn,bm,product;if(n==0)return0;if(n==1)returnm;一個(gè)遞歸和減治法混合應(yīng)用例子----俄式乘法習(xí)題5的第2題25if(n%2==0){halfn=n>>1;bm=m<<1;product=rmul(halfn,bm);}if(n%2==1){halfn=n>>1;bm=m<<1;product=rmul(halfn,bm)+m;}returnproduct;}if(n%2==0)26intrmul(intn,intm)/*方法2：非遞歸法*/

{intresult=0;while(n!=0){if(n%2==0)m=m<<1;else{result=result+m;m=m<<1;}n=n>>1;}returnresult;}intrmul(intn,intm)/*方27第6章動(dòng)態(tài)規(guī)劃法掌握動(dòng)態(tài)規(guī)劃法的設(shè)計(jì)思想掌握動(dòng)態(tài)規(guī)劃法在TSP問(wèn)題和0/1背包問(wèn)題中的應(yīng)用。給出一個(gè)TSP或者0/1背包問(wèn)題的實(shí)例，能夠?qū)懗鏊膭?dòng)態(tài)規(guī)劃過(guò)程。P134：實(shí)驗(yàn)6第6章動(dòng)態(tài)規(guī)劃法掌握動(dòng)態(tài)規(guī)劃法的設(shè)計(jì)思想28動(dòng)態(tài)規(guī)劃法的設(shè)計(jì)思想

動(dòng)態(tài)規(guī)劃法將待求解問(wèn)題分解成若干個(gè)相互重疊的子問(wèn)題，每個(gè)子問(wèn)題對(duì)應(yīng)決策過(guò)程的一個(gè)階段，一般來(lái)說(shuō)，子問(wèn)題的重疊關(guān)系表現(xiàn)在對(duì)給定問(wèn)題求解的遞推關(guān)系（也就是動(dòng)態(tài)規(guī)劃函數(shù)）中，將子問(wèn)題的解求解一次并填入表中，當(dāng)需要再次求解此子問(wèn)題時(shí)，可以通過(guò)查表獲得該子問(wèn)題的解而不用再次求解，從而避免了大量重復(fù)計(jì)算。動(dòng)態(tài)規(guī)劃法的設(shè)計(jì)思想動(dòng)態(tài)規(guī)劃法將待求解問(wèn)題分解成若29原問(wèn)題的解原問(wèn)題……填表子問(wèn)題1子問(wèn)題2子問(wèn)題n動(dòng)態(tài)規(guī)劃法的求解過(guò)程原問(wèn)題的解原問(wèn)題……填表子問(wèn)題1子30n=5時(shí)分治法計(jì)算斐波那契數(shù)的過(guò)程。

F(5)F(4)F(3)F(3)F(2)F(2)F(1)F(2)F(1)F(1)F(0)F(1)F(0)F(1)F(0)例：計(jì)算斐波那契數(shù)：n=5時(shí)分治法計(jì)算斐波那契數(shù)的過(guò)程。F(5)F(4)F(33101234567890112358132134動(dòng)態(tài)規(guī)劃法求解斐波那契數(shù)F(9)的填表過(guò)程：注意到，計(jì)算F(n)是以計(jì)算它的兩個(gè)重疊子問(wèn)題

F(n-1)和F(n-2)的形式來(lái)表達(dá)的，所以，可以設(shè)計(jì)一張表填入n+1個(gè)F(n)的值。

01234567890112358132134動(dòng)態(tài)規(guī)劃法求解32TSP問(wèn)題

TSP問(wèn)題是指旅行家要旅行n個(gè)城市，要求各個(gè)城市經(jīng)歷且僅經(jīng)歷一次然后回到出發(fā)城市，并要求所走的路程最短。各個(gè)城市間的距離可以用代價(jià)矩陣來(lái)表示。C=∞3675∞2364∞2375∞帶權(quán)圖的代價(jià)矩陣TSP問(wèn)題TSP問(wèn)題是指旅行家要旅行n個(gè)城市，要求33假設(shè)從頂點(diǎn)i出發(fā)，令d(i,V')表示從頂點(diǎn)i出發(fā)經(jīng)過(guò)V'中各個(gè)頂點(diǎn)一次且僅一次，最后回到出發(fā)點(diǎn)i的最短路徑長(zhǎng)度，開(kāi)始時(shí)，V'＝V－{i}，于是，TSP問(wèn)題的動(dòng)態(tài)規(guī)劃函數(shù)為：d(i,V')=min{cik+d(k,V－{k})}(k∈V')（式6.5）d(k,{})=cki(k≠i)（式6.6）假設(shè)從頂點(diǎn)i出發(fā)，令d(i,V')表示從頂點(diǎn)i出發(fā)經(jīng)過(guò)V'34這是最后一個(gè)階段的決策，而：

d(1,{2,3})=min{c12+d(2,{3}),c13+d(3,{2})}d(2,{1,3})=min{c21+d(1,{3}),c23+d(3,{1})}d(3,{1,2})=min{c31+d(1,{2}),c32+d(2,{1})}這一階段的決策又依賴(lài)于下面的計(jì)算結(jié)果：d(1,{2})=c12+d(2,{})d(2,{3})=c23+d(3,{})d(3,{2})=c32+d(2,{})d(1,{3})=c13+d(3,{})d(2,{1})=c21+d(1,{})d(3,{1})=c31+d(1,{})

從城市0出發(fā)經(jīng)城市1、2、3然后回到城市0的最短路徑長(zhǎng)度是：d(0,{1,2,3})=min{c01+d(1,{2,3}),c02+d(2,{1,3}),c03+d(3,{1,2})}而下式可以直接獲得（括號(hào)中是該決策引起的狀態(tài)轉(zhuǎn)移）：d(1,{})=c10=5(1→0)d(2,{})=c20=6(2→0)d(3,{})=c30=3(3→0)這是最后一個(gè)階段的決策，而：從城市0出發(fā)經(jīng)城市1、2、3然35再向前倒推，有：d(1,{2})=c12+d(2,{})=2+6=8(1→2)d(1,{3})=c13+d(3,{})=3+3=6(1→3)d(2,{3})=c23+d(3,{})=2+3=5(2→3)d(2,{1})=c21+d(1,{})=4+5=9(2→1)d(3,{1})=c31+d(1,{})=7+5=12(3→1)d(3,{2})=c32+d(2,{})=5+6=11(3→2)再向前倒退，有：d(1,{2,3})=min{c12+d(2,{3}),c13+d(3,{2})}=min{2+5,3+11}=7(1→2)d(2,{1,3})=min{c21+d(1,{3}),c23+d(3,{1})}=min{4+6,2+12}=10(2→1)d(3,{1,2})=min{c31+d(1,{2}),c32+d(2,{1})}=min{7+8,5+9}=14(3→2)最后有：d(0,{1,2,3})=min{c01+d(1,{2,3}),c02+d(2,{1,3}),c03+d(3,{1,2})}=min{3+7,6+10,7+14}=10(0→1)所以，從頂點(diǎn)0出發(fā)的TSP問(wèn)題的最短路徑長(zhǎng)度為10，路徑是0→1→2→3→0。

再向前倒推，有：d(3,{1,2})=min{c31+d36算法6.1——TSP問(wèn)題1．for(i=1;i<n;i++)//初始化第0列d[i][0]=c[i][0];2．for(j=1;j<2n-1-1;j++)for(i=1;i<n;i++)//依次進(jìn)行第i次迭代if(子集V[j]中不包含i)對(duì)V[j]中的每個(gè)元素k，計(jì)算d[i][j]=min(c[i][k]+d[k][j-1]);3．對(duì)V[2n-1-1]中的每一個(gè)元素k，計(jì)算d[0][2n-1-1]=min(c[0][k]+d[k][2n-1-2]);4．輸出最短路徑長(zhǎng)度d[0][2n-1-1];偽代碼設(shè)頂點(diǎn)之間的代價(jià)存放在數(shù)組c[n][n]中，動(dòng)態(tài)規(guī)劃法求解TSP問(wèn)題的算法如下：

算法6.1——TSP問(wèn)題偽代碼設(shè)頂點(diǎn)之間的代價(jià)存放在370/1背包問(wèn)題

在0/1背包問(wèn)題中，物品i或者被裝入背包，或者不被裝入背包，設(shè)xi表示物品i裝入背包的情況，則當(dāng)xi=0時(shí)，表示物品i沒(méi)有被裝入背包，xi=1時(shí)，表示物品i被裝入背包。根據(jù)問(wèn)題的要求，有如下約束條件和目標(biāo)函數(shù)：

（式6.9）（式6.10）于是，問(wèn)題歸結(jié)為尋找一個(gè)滿(mǎn)足約束條件式6.9，并使目標(biāo)函數(shù)式6.10達(dá)到最大的解向量X=(x1,x2,…,xn)。0/1背包問(wèn)題在0/1背包問(wèn)題中，物品i或者38

0/1背包問(wèn)題可以看作是決策一個(gè)序列(x1,x2,…,xn)，對(duì)任一變量xi的決策是決定xi=1還是xi=0。在對(duì)xi-1決策后，已確定了(x1,…,xi-1)，在決策xi時(shí)，問(wèn)題處于下列兩種狀態(tài)之一：（1）背包容量不足以裝入物品i，則xi=0，背包不增加價(jià)值；（2）背包容量可以裝入物品i，則xi=1，背包的價(jià)值增加了vi。這兩種情況下背包價(jià)值的最大者應(yīng)該是對(duì)xi決策后的背包價(jià)值。令V(i,j)表示在前i(1≤i≤n)個(gè)物品中能夠裝入容量為j（1≤j≤C）的背包中的物品的最大值，則可以得到如下動(dòng)態(tài)規(guī)劃函數(shù)：V(i,0)=V(0,j)=0（式6.11）（式6.12）0/1背包問(wèn)題可以看作是決策一個(gè)序列(x1,x2,39式6.11表明：把前面i個(gè)物品裝入容量為0的背包和把0個(gè)物品裝入容量為j的背包，得到的價(jià)值均為0。式6.12的第一個(gè)式子表明：如果第i個(gè)物品的重量大于背包的容量，則裝入前i個(gè)物品得到的最大價(jià)值和裝入前i-1個(gè)物品得到的最大價(jià)值是相同的，即物品i不能裝入背包；第二個(gè)式子表明：如果第i個(gè)物品的重量小于背包的容量，則會(huì)有以下兩種情況：（1）如果把第i個(gè)物品裝入背包，則背包中物品的價(jià)值等于把前i-1個(gè)物品裝入容量為j-wi的背包中的價(jià)值加上第i個(gè)物品的價(jià)值vi；（2）如果第i個(gè)物品沒(méi)有裝入背包，則背包中物品的價(jià)值就等于把前i-1個(gè)物品裝入容量為j的背包中所取得的價(jià)值。顯然，取二者中價(jià)值較大者作為把前i個(gè)物品裝入容量為j的背包中的最優(yōu)解。

式6.11表明：把前面i個(gè)物品裝入容量為0的背包和把40根據(jù)動(dòng)態(tài)規(guī)劃函數(shù)，用一個(gè)(n+1)×(C+1)的二維表V，V[i][j]表示把前i個(gè)物品裝入容量為j的背包中獲得的最大價(jià)值。

0例如，有5個(gè)物品，其重量分別是{2,2,6,5,4}，價(jià)值分別為{6,3,5,4,6}，背包的容量為10。x5=1x4=0x3=0x2=1x1=1

012345678910

00000000000w1=2v1=6100666666666w2=2v2=3200669999999w3=6v3=5300669999111114w4=5v4=44006699910111314w5=5v5=6500669912121515150根據(jù)動(dòng)態(tài)規(guī)劃函數(shù)，用一個(gè)(n+1)×(C+1)的二維表41按下述方法來(lái)劃分階段：第一階段，只裝入前1個(gè)物品，確定在各種情況下的背包能夠得到的最大價(jià)值；第二階段，只裝入前2個(gè)物品，確定在各種情況下的背包能夠得到的最大價(jià)值；依此類(lèi)推，直到第n個(gè)階段。最后，V(n,C)便是在容量為C的背包中裝入n個(gè)物品時(shí)取得的最大價(jià)值。為了確定裝入背包的具體物品，從V(n,C)的值向前推，如果V(n,C)>V(n-1,C)，表明第n個(gè)物品被裝入背包，前n-1個(gè)物品被裝入容量為C-wn的背包中；否則，第n個(gè)物品沒(méi)有被裝入背包，前n-1個(gè)物品被裝入容量為C的背包中。依此類(lèi)推，直到確定第1個(gè)物品是否被裝入背包中為止。由此，得到如下函數(shù)：

（式6.13）

按下述方法來(lái)劃分階段：第一階段，只裝入前1個(gè)物品，確42

設(shè)n個(gè)物品的重量存儲(chǔ)在數(shù)組w[n]中，價(jià)值存儲(chǔ)在數(shù)組v[n]中，背包容量為C，數(shù)組V[n+1][C+1]存放迭代結(jié)果，其中V[i][j]表示前i個(gè)物品裝入容量為j的背包中獲得的最大價(jià)值，數(shù)組x[n]存儲(chǔ)裝入背包的物品，動(dòng)態(tài)規(guī)劃法求解0/1背包問(wèn)題的算法如下：

算法6.3——0/1背包問(wèn)題

intKnapSack(intn,intw[],intv[]){for(i=0;i<=n;i++)//初始化第0列V[i][0]=0;for(j=0;j<=C;j++)//初始化第0行V[0][j]=0;for(i=1;i<=n;i++)//計(jì)算第i行，進(jìn)行第i次迭代for(j=1;j<=C;j++)if(j<w[i])C++描述設(shè)n個(gè)物品的重量存儲(chǔ)在數(shù)組w[n]中，價(jià)值存43算法6.3——0/1背包問(wèn)題V[i][j]=V[i-1][j];elseV[i][j]=max(V[i-1][j],V[i-1][j-w[i]]+v[i]);j=C;//求裝入背包的物品for(i=n;i>0;i--){if(V[i][j]>V[i-1][j]){x[i]=1;j=j-w[i];}elsex[i]=0;}returnV[n][C];//返回背包取得的最大價(jià)值}C++描述算法6.3——0/1背包問(wèn)題C++描述44第7章貪心法掌握貪心法的設(shè)計(jì)思想掌握貪心法在TSP問(wèn)題中的應(yīng)用掌握貪心法在背包問(wèn)題中的應(yīng)用P155：實(shí)驗(yàn)7第7章貪心法掌握貪心法的設(shè)計(jì)思想45貪心法的求解過(guò)程

用貪心法求解問(wèn)題應(yīng)該考慮如下幾個(gè)方面：（1）候選集合C：為了構(gòu)造問(wèn)題的解決方案，有一個(gè)候選集合C作為問(wèn)題的可能解，即問(wèn)題的最終解均取自于候選集合C。例如，在付款問(wèn)題中，各種面值的貨幣構(gòu)成候選集合。（2）解集合S：隨著貪心選擇的進(jìn)行，解集合S不斷擴(kuò)展，直到構(gòu)成一個(gè)滿(mǎn)足問(wèn)題的完整解。例如，在付款問(wèn)題中，已付出的貨幣構(gòu)成解集合。貪心法的求解過(guò)程用貪心法求解問(wèn)題應(yīng)該考慮如下幾個(gè)46

（3）解決函數(shù)solution：檢查解集合S是否構(gòu)成問(wèn)題的完整解。例如，在付款問(wèn)題中，解決函數(shù)是已付出的貨幣金額恰好等于應(yīng)付款。

（4）選擇函數(shù)select：即貪心策略，這是貪心法的關(guān)鍵，它指出哪個(gè)候選對(duì)象最有希望構(gòu)成問(wèn)題的解，選擇函數(shù)通常和目標(biāo)函數(shù)有關(guān)。例如，在付款問(wèn)題中，貪心策略就是在候選集合中選擇面值最大的貨幣。（5）可行函數(shù)feasible：檢查解集合中加入一個(gè)候選對(duì)象是否可行，即解集合擴(kuò)展后是否滿(mǎn)足約束條件。例如，在付款問(wèn)題中，可行函數(shù)是每一步選擇的貨幣和已付出的貨幣相加不超過(guò)應(yīng)付款。

（3）解決函數(shù)solution：檢查解集合S是否構(gòu)成問(wèn)題47貪心法的一般過(guò)程Greedy(C)//C是問(wèn)題的輸入集合即候選集合{S={};//初始解集合為空集while(notsolution(S))//集合S沒(méi)有構(gòu)成問(wèn)題的一個(gè)解{x=select(C);//在候選集合C中做貪心選擇iffeasible(S,x)//判斷集合S中加入x后的解是否可行S=S+{x};C=C-{x};}returnS;}貪心法的一般過(guò)程48TSP問(wèn)題

最近鄰點(diǎn)策略：從任意城市出發(fā)，每次在沒(méi)有到過(guò)的城市中選擇最近的一個(gè)，直到經(jīng)過(guò)了所有的城市，最后回到出發(fā)城市。TSP問(wèn)題最近鄰點(diǎn)策略：從任意城市出發(fā)，每次在沒(méi)有到過(guò)的城49(d)城市3→城市5(e)城市5→城市2(f)城市2→城市1最近鄰點(diǎn)貪心策略求解TSP問(wèn)題的過(guò)程25221543225221543232522154327363215432233215432C=∞33263∞73237∞25232∞36253∞(a)5城市的代價(jià)矩陣(b)城市1→城市4(c)城市4→城市3(d)城市3→城市5(e)城市5→城市50背包問(wèn)題

給定n種物品和一個(gè)容量為C的背包，物品i的重量是wi，其價(jià)值為vi，背包問(wèn)題是如何選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大?

背包問(wèn)題給定n種物品和一個(gè)容量為C的背包，51

于是，背包問(wèn)題歸結(jié)為尋找一個(gè)滿(mǎn)足約束條件式7.1，并使目標(biāo)函數(shù)式7.2達(dá)到最大的解向量X=(x1,x2,…,xn)。設(shè)xi表示物品i裝入背包的情況，根據(jù)問(wèn)題的要求，有如下約束條件和目標(biāo)函數(shù)：（式7.1）（式7.2）于是，背包問(wèn)題歸結(jié)為尋找一個(gè)滿(mǎn)足約束條件式752三種看似合理的貪心策略：（1）選擇價(jià)值最大的物品，因?yàn)檫@可以盡可能快地增加背包的總價(jià)值。但是，雖然每一步選擇獲得了背包價(jià)值的極大增長(zhǎng)，但背包容量卻可能消耗得太快，使得裝入背包的物品個(gè)數(shù)減少，從而不能保證目標(biāo)函數(shù)達(dá)到最大。（2）選擇重量最輕的物品，因?yàn)檫@可以裝入盡可能多的物品，從而增加背包的總價(jià)值。但是，雖然每一步選擇使背包的容量消耗得慢了，但背包的價(jià)值卻沒(méi)能保證迅速增長(zhǎng)，從而不能保證目標(biāo)函數(shù)達(dá)到最大。（3）選擇單位重量?jī)r(jià)值最大的物品，在背包價(jià)值增長(zhǎng)和背包容量消耗兩者之間尋找平衡。三種看似合理的貪心策略：5312050背包180190200(a)三個(gè)物品及背包(b)貪心策略1(c)貪心策略2(d)貪心策略350301020203020/30201010/203010例如，有3個(gè)物品，其重量分別是{20,30,10}，價(jià)值分別為{60,120,50}，背包的容量為50，應(yīng)用三種貪心策略裝入背包的物品和獲得的價(jià)值如圖所示。12050背包54第8章回溯法掌握回溯法的設(shè)計(jì)思想針對(duì)某一特定實(shí)例，會(huì)寫(xiě)出動(dòng)態(tài)搜索過(guò)程，并畫(huà)出搜索空間樹(shù)，從而找到最優(yōu)解0/1背包問(wèn)題TSP問(wèn)題第8章回溯法掌握回溯法的設(shè)計(jì)思想55

對(duì)于任何一個(gè)問(wèn)題，可能解的表示方式和它相應(yīng)的解釋隱含了解空間及其大小。例如，對(duì)于有n個(gè)物品的0/1背包問(wèn)題，其可能解的表示方式可以有以下兩種：（1）可能解由一個(gè)不等長(zhǎng)向量組成，當(dāng)物品i(1≤i≤n)裝入背包時(shí)，解向量中包含分量i，否則，解向量中不包含分量i，當(dāng)n=3時(shí)，其解空間是：{(),(1),(2),(3),(1,2),(1,3),(2,3),(1,2,3)}（2）可能解由一個(gè)等長(zhǎng)向量{x1,x2,…,xn}組成，其中xi=1(1≤i≤n)表示物品i裝入背包，xi=0表示物品i沒(méi)有裝入背包，當(dāng)n=3時(shí)，其解空間是：{(0,0,0),(0,0,1),(0,1,0),(1,0,0),(0,1,1),(1,0,1),(1,1,0),(1,1,1)}對(duì)于任何一個(gè)問(wèn)題，可能解的表示方式和它相應(yīng)的56為了用回溯法求解一個(gè)具有n個(gè)輸入的問(wèn)題，一般情況下，將其可能解表示為滿(mǎn)足某個(gè)約束條件的等長(zhǎng)向量X=(x1,x2,…,xn)，其中分量xi(1≤i≤n)的取值范圍是某個(gè)有限集合Si={ai1,ai2,…,airi}，所有可能的解向量構(gòu)成了問(wèn)題的解空間。

為了用回溯法求解一個(gè)具有n個(gè)輸入的問(wèn)題，一般57問(wèn)題的解空間一般用解空間樹(shù)（SolutionSpaceTrees,也稱(chēng)狀態(tài)空間樹(shù)）的方式組織，樹(shù)的根結(jié)點(diǎn)位于第1層，表示搜索的初始狀態(tài)，第2層的結(jié)點(diǎn)表示對(duì)解向量的第一個(gè)分量做出選擇后到達(dá)的狀態(tài)，第1層到第2層的邊上標(biāo)出對(duì)第一個(gè)分量選擇的結(jié)果，依此類(lèi)推，從樹(shù)的根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的路徑就構(gòu)成了解空間的一個(gè)可能解。問(wèn)題的解空間一般用解空間樹(shù)（Solution58對(duì)于n=3的0/1背包問(wèn)題，其解空間樹(shù)如圖8.2所示，樹(shù)中的8個(gè)葉子結(jié)點(diǎn)分別代表該問(wèn)題的8個(gè)可能解。

對(duì)物品1的選擇對(duì)物品3的選擇對(duì)物品2的選擇1111110000000112345781112141531069對(duì)于n=3的0/1背包問(wèn)題，其解空間樹(shù)如圖8.2所示，樹(shù)中的59對(duì)于n=4的TSP問(wèn)題，其解空間樹(shù)如圖8.3所示，樹(shù)中的24個(gè)葉子結(jié)點(diǎn)分別代表該問(wèn)題的24個(gè)可能解，例如結(jié)點(diǎn)5代表一個(gè)可能解，路徑為1→2→3→4→1，長(zhǎng)度為各邊代價(jià)之和。

243422343413142412123312134131312321214241434322434123124134圖8.3n=4的TSP問(wèn)題的解空間樹(shù)5710121517212326283133373942444749525457596264469111416202225273032363841434648515356586163381319242935404550556021834241123434對(duì)于n=4的TSP問(wèn)題，其解空間樹(shù)如圖8.3所示，樹(shù)60解空間樹(shù)的動(dòng)態(tài)搜索

回溯法從根結(jié)點(diǎn)出發(fā)，按照深度優(yōu)先策略遍歷解空間樹(shù)，搜索滿(mǎn)足約束條件的解。在搜索至樹(shù)中任一結(jié)點(diǎn)時(shí)，先判斷該結(jié)點(diǎn)對(duì)應(yīng)的部分解是否滿(mǎn)足約束條件，或者是否超出目標(biāo)函數(shù)的界，也就是判斷該結(jié)點(diǎn)是否包含問(wèn)題的（最優(yōu)）解，如果肯定不包含，則跳過(guò)對(duì)以該結(jié)點(diǎn)為根的子樹(shù)的搜索，即所謂剪枝（Pruning）；否則，進(jìn)入以該結(jié)點(diǎn)為根的子樹(shù)，繼續(xù)按照深度優(yōu)先策略搜索。解空間樹(shù)的動(dòng)態(tài)搜索回溯法從根結(jié)點(diǎn)出發(fā)，按照深61例如，對(duì)于n=3的0/1背包問(wèn)題，三個(gè)物品的重量為{20,15,10}，價(jià)值為{20,30,25}，背包容量為25，從圖8.2所示的解空間樹(shù)的根結(jié)點(diǎn)開(kāi)始搜索，搜索過(guò)程如下：1不可行解價(jià)值=20價(jià)值=55價(jià)值=30價(jià)值=25價(jià)值=01111000000112811121415131069不可行解例如，對(duì)于n=3的0/1背包問(wèn)題，三個(gè)物品的重量為{20,62再如，對(duì)于n=4的TSP問(wèn)題，其代價(jià)矩陣如圖8.5所示，

C=∞36712∞2886∞2376∞圖8.5TSP問(wèn)題的代價(jià)矩陣再如，對(duì)于n=4的TSP問(wèn)題，其代價(jià)矩陣如圖8.5所632344221231341313123212142414322434123124134圖8.6TSP問(wèn)題的搜索空間547544112746485153583813242935404550556021834241234123442212313413131232121424143264回溯法的求解過(guò)程

由于問(wèn)題的解向量X=(x1,x2,…,xn)中的每個(gè)分量xi(1≤i≤n)都屬于一個(gè)有限集合Si={ai1,ai2,…,airi}，因此，回溯法可以按某種順序（例如字典序）依次考察笛卡兒積S1×S2×…×Sn中的元素。初始時(shí)，令解向量X為空，然后，從根結(jié)點(diǎn)出發(fā)，選擇S1的第一個(gè)元素作為解向量X的第一個(gè)分量，即x1=a11，如果X=(x1)是問(wèn)題的部分解，則繼續(xù)擴(kuò)展解向量X，選擇S2的第一個(gè)元素作為解向量X的第2個(gè)分量，否則，選擇S1的下一個(gè)元素作為解向量X的第一個(gè)分量，即x1=a12。依此類(lèi)推，一般情況下，如果X=(x1,x2,…,xi)是問(wèn)題的部分解，則選擇Si+1的第一個(gè)元素作為解向量X的第i+1個(gè)分量時(shí)，有下面三種情況：回溯法的求解過(guò)程由于問(wèn)題的解向量X=(x165（1）如果X=(x1,x2,…,xi＋1)是問(wèn)題的最終解，則輸出這個(gè)解。如果問(wèn)題只希望得到一個(gè)解，則結(jié)束搜索，否則繼續(xù)搜索其他解；（2）如果X=(x1,x2,…,xi＋1)是問(wèn)題的部分解，則繼續(xù)構(gòu)造解向量的下一個(gè)分量；（3）如果X=(x1,x2,…,xi＋1)既不是問(wèn)題的部分解也不是問(wèn)題的最終解，則存在下面兩種情況：①如果xi+1=ai＋1k不是集合Si＋1的最后一個(gè)元素，則令xi+1=ai＋1k＋1，即選擇Si+1的下一個(gè)元素作為解向量X的第i+1個(gè)分量；②如果xi+1=ai＋1k是集合Si＋1的最后一個(gè)元素，就回溯到X=(x1,x2,…,xi)，選擇Si的下一個(gè)元素作為解向量X的第i個(gè)分量，假設(shè)xi=aik，如果aik不是集合Si的最后一個(gè)元素，則令xi=aik＋1；否則，就繼續(xù)回溯到X=(x1,x2,…,xi－1)；（1）如果X=(x1,x2,…,xi＋1)是問(wèn)題的最終66回溯法的一般框架——迭代形式1．X={};2．flag=false;3．k=1;4．while(k>=1)4.1當(dāng)(Sk沒(méi)有被窮舉)循環(huán)執(zhí)行下列操作4.1.1xk=Sk中的下一個(gè)元素;4.1.2將xk加入X;4.1.3if(X為最終解)flag=true;轉(zhuǎn)步驟5;4.1.4elseif(X為部分解)k=k+1;轉(zhuǎn)步驟4;4.2重置Sk，使得下一個(gè)元素排在第1位;4.3k=k-1;//回溯5．ifflag輸出解X;else輸出“無(wú)解”;回溯算法的非遞歸迭代形式的一般框架如下：回溯法的一般框架——迭代形式回溯算法的非遞歸迭代形式67第9章分支限界法掌握分支限界法的設(shè)計(jì)思想針對(duì)某一特定實(shí)例，會(huì)寫(xiě)出動(dòng)態(tài)搜索過(guò)程，并畫(huà)出搜索空間樹(shù)，從而找到最優(yōu)解0/1背包問(wèn)題TSP問(wèn)題第9章分支限界法掌握分支限界法的設(shè)計(jì)思想68分支限界法首先確定一個(gè)合理的限界函數(shù)，并根據(jù)限界函數(shù)確定目標(biāo)函數(shù)的界[down,up]。然后，按照廣度優(yōu)先策略遍歷問(wèn)題的解空間樹(shù)，在分支結(jié)點(diǎn)上，依次搜索該結(jié)點(diǎn)的所有孩子結(jié)點(diǎn)，分別估算這些孩子結(jié)點(diǎn)的目標(biāo)函數(shù)的可能取值，如果某孩子結(jié)點(diǎn)的目標(biāo)函數(shù)可能取得的值超出目標(biāo)函數(shù)的界，則將其丟棄，因?yàn)閺倪@個(gè)結(jié)點(diǎn)生成的解不會(huì)比目前已經(jīng)得到的解更好；否則，將其加入待處理結(jié)點(diǎn)表（以下簡(jiǎn)稱(chēng)表PT）中。依次從表PT中選取使目標(biāo)函數(shù)的值取得極值的結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)，重復(fù)上述過(guò)程，直到找到最優(yōu)解。解空間樹(shù)的動(dòng)態(tài)搜索（2）分支限界法首先確定一個(gè)合理的限界函數(shù)，并根據(jù)69隨著這個(gè)遍歷過(guò)程的不斷深入，表PT中所估算的目標(biāo)函數(shù)的界越來(lái)越接近問(wèn)題的最優(yōu)解。當(dāng)搜索到一個(gè)葉子結(jié)點(diǎn)時(shí)，如果該結(jié)點(diǎn)的目標(biāo)函數(shù)值是表PT中的極值（對(duì)于最小化問(wèn)題，是極小值；對(duì)于最大化問(wèn)題，是極大值），則該葉子結(jié)點(diǎn)對(duì)應(yīng)的解就是問(wèn)題的最優(yōu)解；否則，根據(jù)這個(gè)葉子結(jié)點(diǎn)調(diào)整目標(biāo)函數(shù)的界（對(duì)于最小化問(wèn)題，調(diào)整上界；對(duì)于最大化問(wèn)題，調(diào)整下界），依次考察表PT中的結(jié)點(diǎn)，將超出目標(biāo)函數(shù)界的結(jié)點(diǎn)丟棄，然后從表PT中選取使目標(biāo)函數(shù)取得極值的結(jié)點(diǎn)繼續(xù)進(jìn)行擴(kuò)展。隨著這個(gè)遍歷過(guò)程的不斷深入，表PT中所估算的70例：0/1背包問(wèn)題。假設(shè)有4個(gè)物品，其重量分別為(4,7,5,3)，價(jià)值分別為(40,42,25,12)，背包容量W=10。首先，將給定物品按單位重量?jī)r(jià)值從大到小排序，結(jié)果如下：物品重量(w)價(jià)值(v)價(jià)值/重量(v/w)144010274263525543124例：0/1背包問(wèn)題。假設(shè)有4個(gè)物品，其重量分別71

應(yīng)用貪心法求得近似解為(1,0,0,0)，獲得的價(jià)值為40，這可以作為0/1背包問(wèn)題的下界。如何求得0/1背包問(wèn)題的一個(gè)合理的上界呢？考慮最好情況，背包中裝入的全部是第1個(gè)物品且可以將背包裝滿(mǎn)，則可以得到一個(gè)非常簡(jiǎn)單的上界的計(jì)算方法：ub=W×(v1/w1)=10×10=100。于是，得到了目標(biāo)函數(shù)的界[40,100]。

限界函數(shù)為：

應(yīng)用貪心法求得近似解為(1,0,0,0)，獲得72×w=0,v=0ub=100w=4,v=40ub=76w=0,v=0ub=60w=11無(wú)效解w=4,v=40ub=70w=9,v=65ub=69w=4,v=40ub=64w=12無(wú)效解w=9,v=65ub=6523456789×1分支限界法求解0/1背包問(wèn)題×w=0,v=0w=4,v=40w=0,v=0w=1173分支限界法求解0/1背包問(wèn)題，其搜索空間如圖9.1所示，具體的搜索過(guò)程如下：（1）在根結(jié)點(diǎn)1，沒(méi)有將任何物品裝入背包，因此，背包的重量和獲得的價(jià)值均為0，根據(jù)限界函數(shù)計(jì)算結(jié)點(diǎn)1的目標(biāo)函數(shù)值為10×10=100；（2）在結(jié)點(diǎn)2，將物品1裝入背包，因此，背包的重量為4，獲得的價(jià)值為40，目標(biāo)函數(shù)值為40+(10-4)×6=76，將結(jié)點(diǎn)2加入待處理結(jié)點(diǎn)表PT中；在結(jié)點(diǎn)3，沒(méi)有將物品1裝入背包，因此，背包的重量和獲得的價(jià)值仍為0，目標(biāo)函數(shù)值為10×6＝60，將結(jié)點(diǎn)3加入表PT中；（3）在表PT中選取目標(biāo)函數(shù)值取得極大的結(jié)點(diǎn)2優(yōu)先進(jìn)行搜索；

分支限界法求解0/1背包問(wèn)題，其搜索空間如圖74（4）在結(jié)點(diǎn)4，將物品2裝入背包，因此，背包的重量為11，不滿(mǎn)足約束條件，將結(jié)點(diǎn)4丟棄；在結(jié)點(diǎn)5，沒(méi)有將物品2裝入背包，因此，背包的重量和獲得的價(jià)值與結(jié)點(diǎn)2相同，目標(biāo)函數(shù)值為40+(10-4)×5=70，將結(jié)點(diǎn)5加入表PT中；（5）在表PT中選取目標(biāo)函數(shù)值取得極大的結(jié)點(diǎn)5優(yōu)先進(jìn)行搜索；（6）在結(jié)點(diǎn)6，將物品3裝入背包，因此，背包的重量為9，獲得的價(jià)值為65，目標(biāo)函數(shù)值為65+(10-9)×4=69，將結(jié)點(diǎn)6加入表PT中；在結(jié)點(diǎn)7，沒(méi)有將物品3裝入背包，因此，背包的重量和獲得的價(jià)值與結(jié)點(diǎn)5相同，目標(biāo)函數(shù)值為40+(10-4)×4＝64，將結(jié)點(diǎn)6加入表PT中；（4）在結(jié)點(diǎn)4，將物品2裝入背包，因此，背包的重量為11，不75（7）在表PT中選取目標(biāo)函數(shù)值取得極大的結(jié)點(diǎn)6優(yōu)先進(jìn)行搜索；（8）在結(jié)點(diǎn)8，將物品4裝入背包，因此，背包的重量為12，不滿(mǎn)足約束條件，將結(jié)點(diǎn)8丟棄；在結(jié)點(diǎn)9，沒(méi)有將物品4裝入背包，因此，背包的重量和獲得的價(jià)值與結(jié)點(diǎn)6相同，目標(biāo)函數(shù)值為65；（9）由于結(jié)點(diǎn)9是葉子結(jié)點(diǎn)，同時(shí)結(jié)點(diǎn)9的目標(biāo)函數(shù)值是表PT中的極大值，所以，結(jié)點(diǎn)9對(duì)應(yīng)的解即是問(wèn)題的最優(yōu)解，搜索結(jié)束。（7）在表PT中選取目標(biāo)函數(shù)值取得極大的結(jié)點(diǎn)6優(yōu)先進(jìn)行搜索；76分支限界法的設(shè)計(jì)思想

假設(shè)求解最大化問(wèn)題，解向量為X=(x1,x2,…,xn)，其中，xi的取值范圍為某個(gè)有窮集合Si，|Si|=ri（1≤i≤n）。在使用分支限界法搜索問(wèn)題的解空間樹(shù)時(shí)，首先根據(jù)限界函數(shù)估算目標(biāo)函數(shù)的界[down,up]，然后從根結(jié)點(diǎn)出發(fā)，擴(kuò)展根結(jié)點(diǎn)的r1個(gè)孩子結(jié)點(diǎn)，從而構(gòu)成分量x1的r1種可能的取值方式。對(duì)這r1個(gè)孩子結(jié)點(diǎn)分別估算可能取得的目標(biāo)函數(shù)值bound(x1)，其含義是以該孩子結(jié)點(diǎn)為根的子樹(shù)所可能取得的目標(biāo)函數(shù)值不大于bound(x1)，也就是部分解應(yīng)滿(mǎn)足：bound(x1)≥bound(x1,x2)≥…≥bound(x1,

x2,…,xk)≥…≥bound(x1,x2,…,xn)分支限界法的設(shè)計(jì)思想假設(shè)求解最大化問(wèn)題，解77若某孩子結(jié)點(diǎn)的目標(biāo)函數(shù)值超出目標(biāo)函數(shù)的界，則將該孩子結(jié)點(diǎn)丟棄；否則，將該孩子結(jié)點(diǎn)保存在待處理結(jié)點(diǎn)表PT中。從表PT中選取使目標(biāo)函數(shù)取得極大值的結(jié)點(diǎn)作為下一次擴(kuò)展的根結(jié)點(diǎn)，重復(fù)上述過(guò)程，當(dāng)?shù)竭_(dá)一個(gè)葉子結(jié)點(diǎn)時(shí)，就得到了一個(gè)可行解X=(x1,x2,…,xn)及其目標(biāo)函數(shù)值bound(x1,x2,…,xn)。如果bound(x1,x2,…,xn)是表PT中目標(biāo)函數(shù)值最大的結(jié)點(diǎn)，則bound(x1,x2,…,xn)就是所求問(wèn)題的最大值，(x1,x2,…,xn)就是問(wèn)題的最優(yōu)解；如果bound(x1,x2,…,xn)不是表PT中目標(biāo)函數(shù)值最大的結(jié)點(diǎn)，說(shuō)明還存在某個(gè)部分解對(duì)應(yīng)的結(jié)點(diǎn)，其上界大于bound(x1,x2,…,xn)。于是，用bound(x1,x2,…,xn)調(diào)整目標(biāo)函數(shù)的下界，即令down=bound(x1,x2,…,xn)，并將表PT中超出目標(biāo)函數(shù)下界down的結(jié)點(diǎn)刪除，然后選取目標(biāo)函數(shù)值取得極大值的結(jié)點(diǎn)作為下一次擴(kuò)展的根結(jié)點(diǎn)，繼續(xù)搜索，直到某個(gè)葉子結(jié)點(diǎn)的目標(biāo)函數(shù)值在表PT中最大。若某孩子結(jié)點(diǎn)的目標(biāo)函數(shù)值超出目標(biāo)函數(shù)的界，則將該孩子78分支限界法求解最大化問(wèn)題的一般過(guò)程分支限界法的一般過(guò)程1．根據(jù)限界函數(shù)確定目標(biāo)函數(shù)的界[down,up]；2．將待處理結(jié)點(diǎn)表PT初始化為空；3．對(duì)根結(jié)點(diǎn)的每個(gè)孩子結(jié)點(diǎn)x執(zhí)行下列操作3.1估算結(jié)點(diǎn)x的目標(biāo)函數(shù)值value;3.2若(value>=down)，則將結(jié)點(diǎn)x加入表PT中；4．循環(huán)直到某個(gè)葉子結(jié)點(diǎn)的目標(biāo)函數(shù)值在表PT中最大4.1i=表PT中值最大的結(jié)點(diǎn)；4.2對(duì)結(jié)點(diǎn)i的每個(gè)孩子結(jié)點(diǎn)x執(zhí)行下列操作4.2.1估算結(jié)點(diǎn)x的目標(biāo)函數(shù)值value;4.2.2若(value>=down)，則將結(jié)點(diǎn)x加入表PT中；4.2.3若(結(jié)點(diǎn)x是葉子結(jié)點(diǎn)且結(jié)點(diǎn)x的value值在表PT中最大)，則將結(jié)點(diǎn)x對(duì)應(yīng)的解輸出，算法結(jié)束；4.2.4若(結(jié)點(diǎn)x是葉子結(jié)點(diǎn)但結(jié)點(diǎn)x的value值在表PT中不是最大)，則令down=value，并且將表PT中所有小于value的結(jié)點(diǎn)刪除；分支限界法求解最大化問(wèn)題的一般過(guò)程分支限界法的一般過(guò)程79算法分析與設(shè)計(jì)常熟理工學(xué)院計(jì)算機(jī)學(xué)院劉在德算法分析與設(shè)計(jì)常熟理工學(xué)院計(jì)算機(jī)學(xué)院80第1章緒論掌握三種漸近符號(hào)（O、Ω、Θ）的含義；會(huì)用三種漸近符號(hào)表示算法的時(shí)間復(fù)雜度；會(huì)用擴(kuò)展遞歸技術(shù)分析算法時(shí)間的復(fù)雜性；對(duì)于表示算法時(shí)間的簡(jiǎn)單遞推式，能夠用擴(kuò)展遞歸技術(shù)求出最終結(jié)果。P15：例1.6P18：實(shí)驗(yàn)1P22：習(xí)題1.7第1章緒論掌握三種漸近符號(hào)（O、Ω、Θ）的含義；81三種漸近符號(hào)的含義大O符號(hào)：若存在兩個(gè)正的常數(shù)c和n0，對(duì)于任意n≥n0，都有T(n)≤c×f(n)，則稱(chēng)T(n)=O(f(n))

大Ω符號(hào)：若存在兩個(gè)正的常數(shù)c和n0，對(duì)于任意n≥n0，都有T(n)≥c×g(n)，則稱(chēng)T(n)=Ω(g(n))Θ符號(hào)：若存在三個(gè)正的常數(shù)c1、c2和n0，對(duì)于任意n≥n0都有c1×f(n)≥T(n)≥c2×f(n)，則稱(chēng)T(n)=Θ(f(n))

三種漸近符號(hào)的含義大O符號(hào)：若存在兩個(gè)正的常數(shù)c和n0，對(duì)于82漸近符號(hào)表示算法時(shí)間復(fù)雜度[定理1.1]若T(n)=amnm+am-1nm-1+···a1n+a0(am>0)，則有T(n)=O(nm)，且T(n)=Ω(nm)，從而T(n)=Θ(nm)[例]

T(n)＝5n2＋8n＋1

當(dāng)n≥1時(shí)，5n2＋8n＋1≤5n2＋8n＋n＝5n2＋9n≤5n2＋9n2≤14n2＝O(n2)

當(dāng)n≥1時(shí)，5n2＋8n＋1≥5n2＝Ω(n2)

∴當(dāng)n≥1時(shí)，14n2≥5n2＋8n＋1≥5n2

則：5n2＋8n＋1＝Θ(n2)

漸近符號(hào)表示算法時(shí)間復(fù)雜度[定理1.1]若T(n)=am83用擴(kuò)展遞歸技術(shù)分析算法時(shí)間的復(fù)雜性擴(kuò)展遞歸技術(shù)：將遞推關(guān)系式中右邊項(xiàng)根據(jù)遞推式進(jìn)行逐次替換，得到求和表達(dá)式[例]

用擴(kuò)展遞歸技術(shù)分析算法時(shí)間的復(fù)雜性擴(kuò)展遞歸技術(shù)：將遞推關(guān)系式84第2章NP完全理論對(duì)于簡(jiǎn)單的判定問(wèn)題，會(huì)畫(huà)判定樹(shù)。判定樹(shù)（DecisionTrees）是一棵二叉樹(shù)：它的每一個(gè)內(nèi)部結(jié)點(diǎn)對(duì)應(yīng)一個(gè)形如x≤y的比較，如果關(guān)系成立，則控制轉(zhuǎn)移到該結(jié)點(diǎn)的左子樹(shù)，否則，控制轉(zhuǎn)移到該結(jié)點(diǎn)的右子樹(shù)，它的每一個(gè)葉子結(jié)點(diǎn)表示問(wèn)題的一個(gè)結(jié)果。

第2章NP完全理論對(duì)于簡(jiǎn)單的判定問(wèn)題，會(huì)畫(huà)判定樹(shù)。85[例]對(duì)三個(gè)數(shù)進(jìn)行排序的判定樹(shù)[例]對(duì)三個(gè)數(shù)進(jìn)行排序的判定樹(shù)86第3章蠻力法掌握改進(jìn)的串匹配算法——KMP算法理解n個(gè)元素的生成排列對(duì)象理解n個(gè)元素組成的集合的生成子集理解0/1背包問(wèn)題理解TSP問(wèn)題第3章蠻力法掌握改進(jìn)的串匹配算法——KMP算法87KMP算法KMP算法思路：如果某趟在Si和Tj匹配失敗后，指針i不回溯；模式T向右滑動(dòng)至某個(gè)位置k，使得tk對(duì)準(zhǔn)si繼續(xù)進(jìn)行匹配。怎么求k？模式T=“t1t2…tm”中的每一個(gè)字符tj都對(duì)應(yīng)一個(gè)k，顯然k與S無(wú)關(guān)。用next[j]表示tj對(duì)應(yīng)的k值，則t1…tk-1既是t1…tj-1的真前綴，又是t1…tj-1的真后綴的最長(zhǎng)子串，稱(chēng)k是tj的前綴函數(shù)值，它等于最長(zhǎng)子串長(zhǎng)度加1。KMP算法KMP算法思路：88next數(shù)組的定義next數(shù)組定義如下：t1t2t3t4t5t6ababac真前綴真后綴∵t1=t5,t1t2t3=t3t4t5∴a和aba都是ababa的真前綴和真后綴，但aba的長(zhǎng)度最大∴next[6]=3+1=4，即當(dāng)t6和si匹配失敗后，將t4和si比較一個(gè)求k的例子：next數(shù)組的定義next數(shù)組定義如下：t1t2t3t4t589next數(shù)組的求法：已求出next[1],…,next[j]，咋求next[j+1]?設(shè)k是t[j]的前綴函數(shù)值，從而有

t1…t2tk-1=tj-k+1tj-k+2…tj-1比較tk和tj，得2種情況：(1)tk=tj：說(shuō)明t1…tk-1tk=tj-k+1…tj-1tj，則next[j+1]=k+1；(2)tk≠tj：此時(shí)要找出t1…tj-1的后綴中第2大真前綴next[next[j]]=next[k],t1…tnext[k]-1=tj-next[k]+1…tj-1，再比較tnext[k]和tj，又會(huì)出現(xiàn)2種情況：next數(shù)組的求法：已求出next[1],…,next[j90next數(shù)組的求法：當(dāng)tnext[k]=tj時(shí)，與(1)類(lèi)似，next[j+1]=next[k]+1；當(dāng)不等時(shí)，找第3大真前綴，重復(fù)(2)的過(guò)程，直至找到t1…tj-1后綴中的最大真前綴，或確定t1…tj-1的后綴中沒(méi)有最大真前綴，此時(shí)next[j+1]=1。next數(shù)組的求法：當(dāng)tnext[k]=tj時(shí)，與(1)類(lèi)似91算法3.4KMP算法中求next數(shù)組voidGetNext(charT[],intnext[])

{//下標(biāo)從1開(kāi)始next[1]=0;j=1;k=0;while(j<=m)If((k==0)||(T[j]==T[k])){j++;k++;next[j]=k;}elsek=next[k]}算法3.4KMP算法中求next數(shù)組voidGetNe92算法3.5KMP算法1.在串S和T中分別設(shè)定比較的起始下標(biāo)i和j；2.循環(huán)直到S中所剩字符長(zhǎng)度小于T的長(zhǎng)度或T中所有字符均比較完畢2.1如S[i]=T[j]，則繼續(xù)比較S和T的下一字符；否則2.2將j向右滑動(dòng)到next[j]位置，即j=next[j]；2.3如果j=0，則將i和j分別加1，準(zhǔn)備下一趟比較；3.如果T中所有字符均比較完畢，則返回匹配的起始下標(biāo)，否則返回0。算法3.5KMP算法1.在串S和T中分別設(shè)定比較的起始93生成排列對(duì)象思路：假定已生成了{(lán)1,2,…,n-1}的所有(n-1)!個(gè)排列，可以把n插入到n-1個(gè)元素的每一種排列的n個(gè)位置中去，得到問(wèn)題規(guī)模為n的所有排列。這時(shí)排列總數(shù)為n(n-1)!=n!。時(shí)間復(fù)雜性：O(n!)算法3.9生成排列對(duì)象（偽代碼）1.生成初始排列{1}；2.for(i=2;i<=n;i++)for(j=1;j<=(i-1)!;j++)for(k=i;k>=1;k--)

將i插入到第j個(gè)排列中的第k個(gè)位置；生成排列對(duì)象思路：假定已生成了{(lán)1,2,…,n-1}的所有(94生成子集思路：n個(gè)元素組成的集合A={a1,a2,…,an}的所有2n個(gè)子集與長(zhǎng)度為n的所有2n個(gè)比特串之間存在一一對(duì)應(yīng)關(guān)系。建立這種關(guān)系的方法是為每個(gè)子集指定一個(gè)比特串b1b2…bn，如果ai屬于該子集，則bi=1，否則bi=0(1≤i≤n)。如3個(gè)元素組成的集合，比特串110表示{a1a2}，比特串000表示Φ。生成子集思路：n個(gè)元素組成的集合A={a1,a2,…,an}95算法3.10生成子集1.初始化一個(gè)長(zhǎng)度為n的比特串s=00…0，并將對(duì)應(yīng)的子集輸出；2.for(i=1;i<2n;i++)2.1s++;2.2將s對(duì)應(yīng)的子集輸出；時(shí)間復(fù)雜性：O(2n)。算法3.10生成子集1.初始化一個(gè)長(zhǎng)度為n的比特串s960/1背包問(wèn)題0/1背包問(wèn)題：給定n個(gè)重量為{w1,w2,…wn}、價(jià)值為{v1,v2,…,vn}的物品和1個(gè)容量為C的背包，求這些物品中的一個(gè)最有價(jià)值的子集，并能夠裝到背包中。思路：考慮給定n個(gè)物品集合的所有子集，找出所有可能的子集(總重量不超過(guò)背包容量的子集)，計(jì)算每個(gè)子集的價(jià)值，從中找出價(jià)值最大子集。0/1背包問(wèn)題0/1背包問(wèn)題：給定n個(gè)重量為{w1,w2,…97TSP問(wèn)題TSP問(wèn)題：旅行家要旅行n個(gè)城市然后回到出發(fā)城市，要求各個(gè)城市經(jīng)歷且僅經(jīng)歷一次，并要求所經(jīng)過(guò)的路程最短。思路：1)找出所有的Hamilton回路，并計(jì)算每個(gè)回路的路徑長(zhǎng)度；2)從中選擇路徑長(zhǎng)度最短的回路。TSP問(wèn)題TSP問(wèn)題：旅行家要旅行n個(gè)城市然后回到出發(fā)城市，98TSP問(wèn)題時(shí)間復(fù)雜性：(n-1)!/2(出發(fā)城市固定，實(shí)際旅游了n-1個(gè)城市)。例子：abdca11acdba11TSP問(wèn)題時(shí)間復(fù)雜性：(n-1)!/2(出發(fā)城市固定，實(shí)際99第4/5章分/減治法理解分治法的基本思路及在典型問(wèn)題中的應(yīng)用掌握遞歸方法在算法設(shè)計(jì)中的應(yīng)用。掌握減治法在經(jīng)典問(wèn)題中的應(yīng)用習(xí)題4.3習(xí)題4.4習(xí)題5.2第4/5章分/減治法理解分治法的基本思路及在典型問(wèn)題中100分治法的求解過(guò)程

一般來(lái)說(shuō)，分治法的求解過(guò)程由以下三個(gè)階段組成：（1）劃分：既然是分治，當(dāng)然需要把規(guī)模為n的原問(wèn)題劃分為k個(gè)規(guī)模較小的子問(wèn)題，并盡量使這k個(gè)子問(wèn)題的規(guī)模大致相同。（2）求解子問(wèn)題：各子問(wèn)題的解法與原問(wèn)題的解法通常是相同的，可以用遞歸的方法求解各個(gè)子問(wèn)題，有時(shí)遞歸處理也可以用循環(huán)來(lái)實(shí)現(xiàn)。（3）合并：把各個(gè)子問(wèn)題的解合并起來(lái)，合并的代價(jià)因情況不同有很大差異，分治算法的有效性很大程度上依賴(lài)于合并的實(shí)現(xiàn)。分治法的求解過(guò)程一般來(lái)說(shuō)，分治法的求解過(guò)程由以101子問(wèn)題的規(guī)模是n/2子問(wèn)題的解原問(wèn)題的解原問(wèn)題的規(guī)模是n減治法的設(shè)計(jì)思想子問(wèn)題子問(wèn)題的解102遞歸遞歸（Recursion）就是子程序（或函數(shù)）直接調(diào)用自己或通過(guò)一系列調(diào)用語(yǔ)句間接調(diào)用自己，是一種描述問(wèn)題和解決問(wèn)題的基本方法。遞歸有兩個(gè)基本要素：⑴邊界條件：確定遞歸到何時(shí)終止；⑵遞歸模式：大問(wèn)題是如何分解為小問(wèn)題的。遞歸遞歸（Recursion）就是子程序（或函數(shù)103一個(gè)遞歸和減治法混合應(yīng)用例子----俄式乘法習(xí)題5的第2題intrmul(intn,intm)/*方法1：遞歸法*/{inthalfn,bm,product;if(n==0)return0;if(n==1)returnm;一個(gè)遞歸和減治法混合應(yīng)用例子----俄式乘法習(xí)題5的第2題104if(n%2==0){halfn=n>>1;bm=m<<1;product=rmul(halfn,bm);}if(n%2==1){halfn=n>>1;bm=m<<1;product=rmul(halfn,bm)+m;}returnproduct;}if(n%2==0)105intrmul(intn,intm)/*方法2：非遞歸法*/

{intresult=0;while(n!=0)