《算法設(shè)計(jì)與分析》復(fù)習(xí)題.doc

填空1直接或間接地調(diào)用自身的算法稱為 遞歸 。2算法的復(fù)雜性是 算法效率 的度量，是評(píng)價(jià)算法優(yōu)劣的重要依據(jù)。3以廣度優(yōu)先或以最小耗費(fèi)方式搜索問(wèn)題解的算法稱為 分支限界法 。4回溯法解題的顯著特點(diǎn)是在搜索過(guò)程中動(dòng)態(tài)產(chǎn)生問(wèn)題的解空間。在任何時(shí)刻，算法只保存從根結(jié)點(diǎn)到當(dāng)前擴(kuò)展結(jié)點(diǎn)的路徑。如果解空間樹(shù)中從根結(jié)點(diǎn)到葉結(jié)點(diǎn)的最長(zhǎng)路徑的長(zhǎng)度為h(n)，則回溯法所需的計(jì)算空間通常為 o(h(n) 。5人們通常將問(wèn)題的解決方案分為兩大類：一類是可以通過(guò)執(zhí)行若干個(gè)步驟就能得出問(wèn)題結(jié)論的，叫做 算法方案 方案；另一類是不能通過(guò)若干個(gè)步驟直截了當(dāng)?shù)氐贸鼋Y(jié)論，而是需要反復(fù)驗(yàn)證才能解決的，叫做 啟發(fā)式方案 方案。6算法就是一組有窮的 規(guī)則 ，它們規(guī)定了解決某一特定類型問(wèn)題的 一系列運(yùn)算 。7在進(jìn)行問(wèn)題的計(jì)算復(fù)雜性分析之前，首先必須建立求解問(wèn)題所用的計(jì)算模型。3個(gè)基本計(jì)算模型是 隨機(jī)存取機(jī)、 隨機(jī)存取存儲(chǔ)程序機(jī) 、 圖靈機(jī) 。8快速排序算法的性能取決于 劃分的對(duì)稱性 。9計(jì)算機(jī)的資源最重要的是 內(nèi)存 和 運(yùn)算 資源。因而，算法的復(fù)雜性有時(shí)間 和 空間 之分。10貪心算法總是做出在當(dāng)前看來(lái) 最優(yōu) 的選擇。也就是說(shuō)貪心算法并不從整體最優(yōu)考慮，它所做出的選擇只是在某種意義上的 局部最優(yōu)解 。11許多可以用貪心算法求解的問(wèn)題一般具有2個(gè)重要的性質(zhì)： 最優(yōu)子結(jié)構(gòu)的 性質(zhì)和 貪心選擇的 性質(zhì)。12常見(jiàn)的兩種分支限界法為 隊(duì)列式 和 優(yōu)先隊(duì)列式 。13解決0/1背包問(wèn)題可以使用動(dòng)態(tài)規(guī)劃、回溯法和分支限界法，其中需要排序的是 回溯法 ，不需要排序的是 動(dòng)態(tài)規(guī)劃和分支限界法 。14f ( n ) = 6 2n + n2，f(n)的漸進(jìn)性態(tài)f ( n ) = O ( 2n )。15對(duì)于含有n個(gè)元素的排列樹(shù)問(wèn)題，最好情況下計(jì)算時(shí)間復(fù)雜性為 ，最壞情況下計(jì)算時(shí)間復(fù)雜性為 n! 。16在忽略常數(shù)因子的情況下，O、和三個(gè)符號(hào)中， 提供了算法運(yùn)行時(shí)間的一個(gè)上界。17回溯法的求解過(guò)程，即在問(wèn)題的解空間樹(shù)中，按 深度優(yōu)先 策略從根結(jié)點(diǎn)出發(fā)搜索解空間樹(shù)。18分支限界法的求解過(guò)程，即在問(wèn)題的解空間樹(shù)中，按 廣度優(yōu)先 策略從根結(jié)點(diǎn)出發(fā)搜索解空間樹(shù)。19多項(xiàng)式的上界為 2n 。20用分支限界法解布線問(wèn)題時(shí)，對(duì)空間樹(shù)搜索結(jié)束的標(biāo)志是 活結(jié)點(diǎn)表為空 。21使用回溯法進(jìn)行狀態(tài)空間樹(shù)裁剪分支時(shí)一般有兩個(gè)標(biāo)準(zhǔn)：約束條件和目標(biāo)函數(shù)的界，N皇后問(wèn)題和0/1背包問(wèn)題正好是兩種不同的類型，其中同時(shí)使用約束條件和目標(biāo)函數(shù)的界進(jìn)行裁剪的是 0-1背包 ，只使用約束條件進(jìn)行裁剪的是 N皇后 。簡(jiǎn)答1. 算法分析的目的是什么？分析算的的效率以求改進(jìn)2. 算法的漸進(jìn)時(shí)間復(fù)雜性的含義？當(dāng)問(wèn)題的規(guī)模n趨向無(wú)窮大時(shí)，影響算法效率的重要因素是T（n）的數(shù)量級(jí)，而其他因素僅是實(shí)用時(shí)間復(fù)雜度相差的常熟倍，因此可以用T（n）的數(shù)量級(jí)（階）評(píng)價(jià)算法。時(shí)間復(fù)雜度T（n）的數(shù)量級(jí)（階）稱為漸進(jìn)時(shí)間復(fù)雜性3. 最壞情況下的時(shí)間復(fù)雜性和平均時(shí)間復(fù)雜性有什么不同？最壞情況下的時(shí)間復(fù)雜性和平均時(shí)間復(fù)雜性考察的是n固定時(shí)，不同輸入實(shí)例下的算法所耗時(shí)間。最壞情況下的時(shí)間復(fù)雜性取的輸入實(shí)例中最大的時(shí)間復(fù)雜度：W(n)=maxT(n，I),IDn平均時(shí)間復(fù)雜性是所有輸入實(shí)例的處理時(shí)間與各自概率的乘積和：A(n)=P(I)T(n，I)IDn4. 簡(jiǎn)述分治法的基本思想。分治法的是將一個(gè)規(guī)模為n的問(wèn)題分解為k個(gè)規(guī)模較小的子問(wèn)題，這些子問(wèn)題相互獨(dú)立且與原題相同5. 簡(jiǎn)述動(dòng)態(tài)規(guī)劃方法所運(yùn)用的最優(yōu)化原理。“最優(yōu)化原理”用數(shù)學(xué)化的語(yǔ)言來(lái)描述：假設(shè)為了解決某一優(yōu)化問(wèn)題，需要依次作出n個(gè)決策D1，D2，Dn，如若這個(gè)決策序列是最優(yōu)的，對(duì)于任何一個(gè)整數(shù)k，1<k<n，不論前面k個(gè)決策是怎樣的，以后的最優(yōu)決策只取決于由前面決策所確定的當(dāng)前狀態(tài)，即以后的決策Dk+1，Dk+2，Dn也是最優(yōu)的。6. 簡(jiǎn)述最優(yōu)子結(jié)構(gòu)性質(zhì)。一道動(dòng)態(tài)規(guī)劃問(wèn)題其實(shí)就是一個(gè)遞推問(wèn)題，假設(shè)當(dāng)前決策結(jié)果是fn，則最優(yōu)子結(jié)構(gòu)就是要讓fn-k最優(yōu)，最優(yōu)子結(jié)構(gòu)性質(zhì)就是能讓轉(zhuǎn)移到n的狀態(tài)是最優(yōu)的，并且與后面的決策沒(méi)有關(guān)系，即讓后面的決策安心地使用前面的局部最優(yōu)解的一種性質(zhì)7. 簡(jiǎn)述回溯法基本思想?；厮莘ǖ幕咀龇ㄊ撬阉?，在問(wèn)題的解空間樹(shù)中，按深度優(yōu)先策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹(shù)。算法搜索至解空間樹(shù)的任意一點(diǎn)時(shí)，先判斷該結(jié)點(diǎn)是否包含問(wèn)題的解。如果肯定不包含，則跳過(guò)對(duì)該結(jié)點(diǎn)為根的子樹(shù)的搜索，逐層向其祖先結(jié)點(diǎn)回溯；否則，進(jìn)入該子樹(shù)，繼續(xù)按深度優(yōu)先策略搜索。8. 用回溯法求解的問(wèn)題，其解如何表示？有什么規(guī)定？問(wèn)題的解可以表示為n元組：（x1,x2,xn），xiSi,Si為有窮集合，xiSi,（x1,x2,xn）具備完備性，即（x1,x2,xn）是合理的，則（x1,x2,xi）(i<n)一定合理。9. 回溯法的搜索特點(diǎn)是什么？在解空間樹(shù)上跳躍式地深度優(yōu)先搜索，即用判定函數(shù)考察xk的取值，如果xk是合理的就搜索xk為根節(jié)點(diǎn)的子樹(shù)，如果xk取完了所有的值，便回溯到xk-1。10. 貪心算法的基本思想？是一種依據(jù)最優(yōu)化量度依次選擇輸入的分級(jí)處理方法。基本思路是：首先根據(jù)題意，選取一種量度標(biāo)準(zhǔn)；然后按這種量度標(biāo)準(zhǔn)對(duì)這n個(gè)輸入排序，依次選擇輸入量加入部分解中。如果當(dāng)前這個(gè)輸入量的加入，不滿足約束條件，則不把此輸入加到這部分解中。11. 什么是直接遞歸和間接遞歸？消除遞歸一般要用到什么數(shù)據(jù)結(jié)構(gòu)？在定義一個(gè)過(guò)程或者函數(shù)的時(shí)候又出現(xiàn)了調(diào)用本過(guò)程或者函數(shù)的成分，既調(diào)用它自己本身，這稱為直接遞歸。如果過(guò)程或者函數(shù)P調(diào)用過(guò)程或者函數(shù)Q，Q又調(diào)用P，這個(gè)稱為間接遞歸。消除遞歸一般要用到棧這種數(shù)據(jù)結(jié)構(gòu)。算法填空1n后問(wèn)題回溯算法（1）用二維數(shù)組ANN存儲(chǔ)皇后位置，若第i行第j列放有皇后，則Aij為非0值，否則值為0。（2）分別用一維數(shù)組MN、L2*N-1、R2*N-1表示豎列、左斜線、右斜線是否放有棋子，有則值為1，否則值為0。for ( j=0; j<N; j+ )if (!Mj&&!Li+j&&!Ri-j+N ) /安全檢查 Aij=i+1;/放皇后 Mj=Li+j=Ri-j+N=1; ; if ( i=N-1 )輸出結(jié)果; else try(i+1,M,L,R,A) ;/試探下一行 Aij=0 ;/去皇后 Mj=Li+j=Ri-j+N=0 ;2數(shù)塔問(wèn)題。有形如下圖所示的數(shù)塔，從頂部出發(fā)，在每一結(jié)點(diǎn)可以選擇向左走或是向右走，一起走到底層，要求找出一條路徑，使路徑上的值最大。for ( r=n-2; r>=0; r- )/自底向上遞歸計(jì)算for ( c=0; ; c+ ) if ( tr+1c > tr+1c+1 ) ;else ;3用回溯法解0/1背包問(wèn)題時(shí)，計(jì)算結(jié)點(diǎn)的上界的函數(shù)如下所示，請(qǐng)?jiān)诳崭裰刑钊牒线m的內(nèi)容：private static double bound ( int i )double cleft = c - cw; / 剩余容量double bound = cp; / 結(jié)點(diǎn)的上界while (i <= n && wi <= cleft) cleft-=wi ; bound+=pi ; i+ ; if (i <= n) bound+=pi*cleft/wi ;return bound;4用回溯法解圖的m著色問(wèn)題時(shí)，使用下面的函數(shù)OK檢查當(dāng)前擴(kuò)展結(jié)點(diǎn)的每一個(gè)兒子所相應(yīng)的顏色的可用性，則需耗時(shí)（漸進(jìn)時(shí)間上限） 。private static boolean ok( int k )/ 檢查顏色可用性 for(int j=1;j<=n;j+)if( akj && xj=xk ) return false;return true;5Hanoi算法Hanoi ( n, a, b, c )if ( n=1 ) move(a,c) ;else Hanoi(n-1,a,c,b) ; Move(a,c) ;Hanoi ( n-1, b, a, c );算法應(yīng)用1給定多項(xiàng)式p(x) = anxn + an-1xn-1 + + a1x + a0，假設(shè)使用以下方法求解：p = a0;xpower = 1;for ( i=1; i<=n; i+ )xpower = x * xpower;p = p + ai * xpower;（1）該算法最壞情況下使用的加法和乘法分別為多少次？（2）能不能對(duì)算法的性能進(jìn)行提高？如果可以，請(qǐng)寫(xiě)出改進(jìn)算法。（1）該算法最壞情況下使用的加法n次，乘法2n次（2）改進(jìn)的算法為：floatHorner(A,floatx)p=An+1;for(j=1;j<=n;j+)p=x*p+An-j;returnp;該算法中使用加法n次，乘法n次2假設(shè)有7個(gè)物品，它們的重量和價(jià)值如下表所示。若這些物品均不能被分割，且背包容量M150，使用回溯方法求解此背包問(wèn)題。請(qǐng)寫(xiě)出狀態(tài)空間搜索樹(shù)。物品ABCDEFG重量35306050401025價(jià)值104030503540303已知在如下所示的電路板中，陰影部分是已作了封鎖標(biāo)記的方格，請(qǐng)按照隊(duì)列式分支限界法在圖中確定a到b的最短布線方案，要求布線時(shí)只能沿直線或直角進(jìn)行，在圖中標(biāo)出求得最優(yōu)解時(shí)各方格情況。ba4設(shè)有n=2k個(gè)運(yùn)動(dòng)員要進(jìn)行循環(huán)賽，現(xiàn)設(shè)計(jì)一個(gè)滿足以下要求的比賽日程表： 每個(gè)選手必須與其他n-1名選手比賽各一次； 每個(gè)選手一天至多只能賽一次； 循環(huán)賽要在最短時(shí)間內(nèi)完成。（1）如果n=2k，循環(huán)賽最少需要進(jìn)行多少天； 如果n2k，循環(huán)賽最少需要進(jìn)行多少天。（2）當(dāng)n=23=8時(shí)，請(qǐng)畫(huà)出循環(huán)賽日程表：5已知，k=1，2，3，4，5，6，r1=5，r2=10，r3=3，r4=12，r5=5，r6=50，r7=6，求矩陣鏈積A1A2A3A4A5A6的最佳求積順序。使用 算法進(jìn)行求解。最優(yōu)值數(shù)組為： 123456123456最優(yōu)斷開(kāi)位置數(shù)組為：123456123456因此，最佳乘積序列為 。共執(zhí)行乘法 次。6棋盤(pán)覆蓋問(wèn)題。（1）將下圖特殊棋盤(pán)進(jìn)行L型骨牌填充。（2）算法時(shí)間復(fù)雜性。7用分支限界法解裝載問(wèn)題時(shí)，對(duì)算法進(jìn)行了一些改進(jìn)，下面的程序段給出了改進(jìn)部分。試說(shuō)明劃線部分完成什么功能，以及這樣做的原因，即采用這樣的方式，算法在執(zhí)行上有什么不同。 / 檢查左兒子結(jié)點(diǎn) int wt = ew + wi; / 左兒子結(jié)點(diǎn)的重量 if ( wt <= c ) / 可行結(jié)點(diǎn) if ( wt > bestw ) bestw = wt ; / 加入活結(jié)點(diǎn)隊(duì)列 if ( i < n ) queue.put( new Integer( wt ) ); / 檢查右兒子結(jié)點(diǎn) if ( ew + r > bestw && i < n ) queue.put( new Integer( wt ) ); / 可能含最優(yōu)解 ew=( ( Integer )queue.remove( ) ).intValue( ); / 取下一擴(kuò)展結(jié)點(diǎn)8單源最短路徑的求解。給定帶權(quán)有向圖（如下圖所示）G = ( V，E )，其中每條邊的權(quán)是非負(fù)實(shí)數(shù)。另外，還給定V中的一個(gè)頂點(diǎn)，稱為源?，F(xiàn)在要計(jì)算從源到所有其它各頂點(diǎn)的最短路長(zhǎng)度。這里路的長(zhǎng)度是指路上各邊權(quán)之和。這個(gè)問(wèn)題通常稱為單源最短路徑問(wèn)題。請(qǐng)用Dijkstra算法計(jì)算從源頂點(diǎn)1到其它頂點(diǎn)間最短路徑。請(qǐng)將此過(guò)程填入下表中。432110030maxint10-1初始dist5dist4dist3dist2uS迭代算法設(shè)計(jì)1用分治算法求給定二叉樹(shù)的高度。2用合適算法求解裝載問(wèn)題。3用貪心法求解部分背包問(wèn)題，已知n=3，C=40，（w1，w2，w3）=（28，15，24），（p1，p2，p3）=（35，25，24）。4給定a，用二分法設(shè)計(jì)出求an的算法。5用回溯法求解 1，2，3，4，5 ，這5個(gè)自然數(shù)中任取3個(gè)數(shù)的組合。