算法分析與設(shè)計(jì)復(fù)習(xí)資料

《算法分析與設(shè)計(jì)》考試要點(diǎn)整理一、問答題（30分）。1．什么是最壞情況時(shí)間復(fù)雜性？什么是平均情況時(shí)間復(fù)雜性？答：最壞情況時(shí)間復(fù)雜性：平均情況時(shí)間復(fù)雜性：I*是DN中使T(N,I*)達(dá)到Tmax(N)的合法輸入；P(I)是在算法的應(yīng)用中出現(xiàn)輸入I的概率2．什么是遞歸算法？什么是遞歸函數(shù)？答：（1）遞歸算法:直接或間接地調(diào)用自身的算法；（2）遞歸函數(shù):用函數(shù)自身給出定義的函數(shù)。3．遞歸函數(shù)的二要素是什么？答：（1）邊界條件（2）遞歸方程4．分治法的設(shè)計(jì)思想是什么？答：將一個(gè)規(guī)模為n的問題分解為k個(gè)規(guī)模較小的子問題,這些子問題相互獨(dú)立且與原問題相同。5．什么叫問題的最優(yōu)子結(jié)構(gòu)性質(zhì)？答：一個(gè)問題的最優(yōu)解包含著其子問題的最優(yōu)解。這種性質(zhì)稱為最優(yōu)子結(jié)構(gòu)性質(zhì)。6．動(dòng)態(tài)規(guī)劃基本步驟是什么？答：（1）找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征;（2）遞歸地定義最優(yōu)值;（3）以自底向上的方式計(jì)算出最優(yōu)值;(4)根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解。7．動(dòng)態(tài)規(guī)劃算法的基本要素是什么？舉例說明一些可以用動(dòng)態(tài)規(guī)劃算法解決的問題。答：（1）最優(yōu)子結(jié)構(gòu)性質(zhì)和子問題重疊性質(zhì)是動(dòng)態(tài)規(guī)劃算法的基本要素（2）矩陣連乘問題，建立遞歸關(guān)系，求最優(yōu)解，0-1背包問題等8．說明分治法與動(dòng)態(tài)規(guī)劃法的相同點(diǎn)和不同之處？答：同：基本思想都是將待求解問題分解成若干個(gè)子問題先求解子問題，然后從這些子問題的解得到原問題的解；異：（1）適合于用動(dòng)態(tài)規(guī)劃法求解的問題，經(jīng)分解得到的子問題往往不是相互獨(dú)立的。若用分治法解這類問題，則分解得到的子問題數(shù)目太多，以至于最后解決原問題需要消耗指數(shù)時(shí)間；（2）不同子問題的數(shù)目常常只有多項(xiàng)式量級，在用分治法求解時(shí)，有些子問題被重復(fù)計(jì)算了許多次。動(dòng)態(tài)規(guī)劃法保存已解決的子問題的答案，在需要時(shí)再找到已得到的答案，可以避免大量重復(fù)計(jì)算，從而得到多項(xiàng)式時(shí)間算法。9．貪心算法的兩個(gè)重要要素是什么？舉例說明一些可以用貪心算法解決的問題。答：（1）貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。（2）背包問題，單源最短路徑，最小生成樹問題等。10．什么叫貪心選擇性質(zhì)？答：所謂貪心選擇性質(zhì)是指所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來達(dá)到。11．貪心算法與動(dòng)態(tài)規(guī)劃算法的的相同點(diǎn)和不同之處？答：同：貪心算法和動(dòng)態(tài)規(guī)劃算法都要求問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)異：貪心具有貪心選擇性質(zhì)，這是貪心算法可行的第一個(gè)基本要素，也是貪心算法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別。12．背包問題與0－1背包問題有何區(qū)別？答：背包問題可以用貪心算法求解，而0-1背包問題不能用貪心算法求解。13．回溯法與分支限界法之間的相同點(diǎn)是什么？不同之處在哪些方面？答：同：他們同是在問題的解空間樹上搜索問題解的算法；異：（1）求解目標(biāo)：回溯法的求解目標(biāo)是找出解空間樹中滿足約束條件的所有解，而分支限界法的求解目標(biāo)則是找出滿足約束條件的一個(gè)解，或是在滿足約束條件的解中找出在某種意義下的最優(yōu)解；（2）搜索方式的不同：回溯法以深度優(yōu)先的方式搜索解空間樹，而分支限界法則以廣度優(yōu)先或以最小耗費(fèi)優(yōu)先的方式搜索解空間樹。14．分支限界法基本思想是什么？答：分支限界法常以廣度優(yōu)先或以最小耗費(fèi)（最大效益）優(yōu)先的方式搜索問題的解空間樹。15．常用的剪枝函數(shù)有哪兩類？答：（1）約束函數(shù)（2）限界函數(shù)16．約束函數(shù)的功能是什么？答：用約束函數(shù)在擴(kuò)展結(jié)點(diǎn)處剪去不滿足約束的子樹17．限界函數(shù)的功能是什么？答：用限界函數(shù)剪去得不到最優(yōu)解的子樹18.．常見的兩種分支限界法是什么？答：（1）隊(duì)列式(FIFO)分支限界法：按照隊(duì)列先進(jìn)先出（FIFO）原則選取下一個(gè)節(jié)點(diǎn)為擴(kuò)展節(jié)點(diǎn)。（2）優(yōu)先隊(duì)列式分支限界法：按照優(yōu)先隊(duì)列中規(guī)定的優(yōu)先級選取優(yōu)先級最高的節(jié)點(diǎn)成為當(dāng)前擴(kuò)展節(jié)點(diǎn)。19．回溯法中剪枝函數(shù)有哪幾類？各有何用途？答：（1）約束函數(shù)限界函數(shù)（2）用約束函數(shù)在擴(kuò)展結(jié)點(diǎn)處剪去不滿足約束的子樹；用限界函數(shù)剪去得不到最優(yōu)解的子樹。20．什么是P問題和NP問題？答：（1）P（Polynomial）問題：如果一個(gè)問題可以找到一個(gè)能在多項(xiàng)式時(shí)間里解決它的算法，那么這個(gè)問題就屬于P問題。（2）NP（Non-DeterministicPolynomial）問題：NP問題不是非P類問題，是多項(xiàng)式復(fù)雜程度的非確定性問題。是指可以在多項(xiàng)式的時(shí)間里驗(yàn)證一個(gè)解的問題。NP問題的另一個(gè)定義是，可以在多項(xiàng)式的時(shí)間里猜出一個(gè)解的問題。21．什么是NP完全問題？答：NP完全（NPC，Complete）問題：如果問題的所有可能答案，都是可以在多項(xiàng)式時(shí)間內(nèi)進(jìn)行正確與否的驗(yàn)算的話，就叫完全多項(xiàng)式非確定問題。22．NP-Hard問題？答：（1）NP-Hard問題要比NPC問題的范圍廣；（2）NP-Hard問題同樣難以找到多項(xiàng)式的算法，它不一定是NP問題；（3）即使NPC問題發(fā)現(xiàn)了多項(xiàng)式級的算法，NP-Hard問題有可能仍然無法得到多項(xiàng)式級的算法；（4）事實(shí)上，由于NP-Hard放寬了限定條件，它將有可能比所有的NPC問題的時(shí)間復(fù)雜度更高從而更難以解決。二、證明題（算法時(shí)間復(fù)雜性）☆（1）O（f）+O（g）=O(max(f,g));☆（2）O（f）+O（g）=O(f+g);證明：令F[N]=O[f],則存在自然數(shù)N1,C1,使得對任意的自然數(shù)N>=N1，有：F（N）<=C1f[N];

同理令：G[N]=O[g],則存在自然數(shù)N2,C2,使得對任意的自然數(shù)N>=N2，有：G（N）<=C2g[N];

令C3=max{C1,C2},N3=max{N1,N2},則對所有的N>=N3,有F[N]<=C1f(N)<=C3f(N);

G[N]<=C2f(N)<=C3g(N);

故有：O(f)+O(g)=F(N)+G(N)<=C3f(N)+C3g(N)=C3(f(N)+g(N))=O(f+g);

因此有：O(f)+O(g)=O(f+g)O（f）O（g）=O（fg）;☆（4）如果g(N)=O(f(N)),則O(f)+O(g)=O(f);O（Cf(N)）=O(f(N)),其中C是一個(gè)正的常數(shù)；（6）f=O(f)三、動(dòng)態(tài)規(guī)劃知識點(diǎn)——流水作業(yè)調(diào)度問題:n個(gè)作業(yè){1，2，…，n}要在由2臺機(jī)器M1和M2組成的流水線上完成加工,其中機(jī)器M2要等時(shí)間t后才可利用。可表示為T(N,t)。每個(gè)作業(yè)加工的順序都是先在M1上加工，然后在M2上加工。M1和M2加工作業(yè)i所需的時(shí)間分別為ai和bi。流水作業(yè)調(diào)度問題要求確定這n個(gè)作業(yè)的最優(yōu)加工順序，使得從第一個(gè)作業(yè)在機(jī)器M1上開始加工，到最后一個(gè)作業(yè)在機(jī)器M2上加工完成所需的時(shí)間最少。分析：1.直觀上，一個(gè)最優(yōu)調(diào)度應(yīng)使機(jī)器M1沒有空閑時(shí)間，且機(jī)器M2的空閑時(shí)間最少。2.在一般情況下，機(jī)器M2上會(huì)有機(jī)器空閑和作業(yè)積壓2種情況。3.設(shè)全部作業(yè)的集合為N={1，2，…，n}。4.SíN是N的作業(yè)子集。在一般情況下，機(jī)器M1開始加工S中作業(yè)時(shí)，機(jī)器M2可能還在加工其他作業(yè)，要等時(shí)間t后才可利用。將這種情況下完成S中作業(yè)所需的最短時(shí)間記為T(S,t)。5.流水作業(yè)調(diào)度問題的最優(yōu)值為6.T(N,0)。設(shè)p是所給n個(gè)流水作業(yè)的一個(gè)最優(yōu)調(diào)度。它所需的加工時(shí)間為ap(1)+T’。其中T’是在機(jī)器M2的等待時(shí)間為bp(1)時(shí)，安排作業(yè)p(2)，…，p(n)所需的時(shí)間。記S=N-{p(1)}，則有T’=T(S,bp(1))。//說明了流水作業(yè)調(diào)度問題具有最優(yōu)子結(jié)構(gòu)的性質(zhì)。四、貪心算法知識點(diǎn)——活動(dòng)安排問題（代碼）重點(diǎn)題型：設(shè)待安排的11個(gè)活動(dòng)的開始時(shí)間和結(jié)束時(shí)間按結(jié)束時(shí)間如下：i1234567891011S[i]312128563805f[i]5413141191081267算法greedySelector的計(jì)算過程如上圖所示。圖中每行相應(yīng)于算法的一次迭代。陰影長條表示的活動(dòng)是已選入集合A的活動(dòng)?？瞻组L條表示的活動(dòng)是當(dāng)前正在檢查相容性的活動(dòng)。publicstaticintgreedySelector(int[]s,int[]f,booleana[]){intn=s.length-1;a[1]=true;intj=1;intcount=1;for(inti=2;i<=n;i++){if(s[i]>=f[j]){a[i]=true;j=i;count++;}elsea[i]=false;}returncount;}五、回溯法知識點(diǎn)——n后問題（代碼）重點(diǎn)題型：在n×n格的棋盤上放置彼此不受攻擊的n個(gè)皇后。按照國際象棋的規(guī)則，皇后可以攻擊與之處在同一行或同一列或同一斜線上的棋子。n后問題等價(jià)于在n×n格的棋盤上放置n個(gè)皇后，任何2個(gè)皇后不放在同一行或同一列或同一斜線上。1234567812345678QQQQQQQQ12345678解向量：(x1,x2,…,xn)顯約束：xi=1,2,…,n隱約束：1)不同列：xi1xj2)不處于同一正、反對角線：|i-j|1|xi-xjprivatestaticvoidbacktrack(intt){if(t>n){sum++;}elsefor(inti=1;i<=n;i++){x[t]=i;if(place(t))backtrack(t+1);}privatestaticbooleanplace(intk){for(intj=1;j<k;j++)if((Math.abs(k-j)==Math.abs(x[j]-x[k]))||(x[j]==x[k]))returnfalse;returntrue;}六、分支限界法知識點(diǎn)——0-1背包問題重點(diǎn)題型：c=341234p4528912091452820w30151081考慮根節(jié)點(diǎn)左孩子，可行，優(yōu)先級103，加入最大堆右孩子，可行，優(yōu)先級93，加入最大堆2取下一個(gè)節(jié)點(diǎn)（最大堆），即對應(yīng)于優(yōu)先級103的節(jié)點(diǎn)。左孩子，不可行右孩子，可行，優(yōu)先級102.2，加入最大堆3取下一個(gè)節(jié)點(diǎn)（最大堆），即對應(yīng)于優(yōu)先級102.2的節(jié)點(diǎn)。左孩子，不可行右孩子，可行，優(yōu)先級101，加入最大堆4取下一個(gè)節(jié)點(diǎn)（最大堆），即對應(yīng)于優(yōu)先級101的節(jié)點(diǎn)。左孩子，不可行右孩子，可行，優(yōu)先級91，加入最大堆5取下一個(gè)節(jié)點(diǎn)（最大堆），即對應(yīng)于優(yōu)先級93的節(jié)點(diǎn)。左孩子，可行，優(yōu)先級93，加入最大堆右孩子，可行，優(yōu)先級48，加入最大堆6取下一個(gè)節(jié)點(diǎn)（最大堆），即對應(yīng)于優(yōu)先級93的節(jié)點(diǎn)。左孩子，可行，優(yōu)先級93，加入最大堆右孩子，可行，優(yōu)先級65，加入最大堆7取下一個(gè)節(jié)點(diǎn)（最大堆），即對應(yīng)于優(yōu)先級93的節(jié)點(diǎn)。左孩子，可行，優(yōu)先級93，加入最大堆右孩子，可行，優(yōu)先級73，加入最大堆8取下一個(gè)節(jié)點(diǎn)（最大堆），即對應(yīng)于優(yōu)先級93的節(jié)點(diǎn)。結(jié)束2.設(shè)有n種面值為:d1≥d2≥……≥dn的錢幣，需要找零錢M，如何選擇錢幣dk，的數(shù)目Xk，滿足d1×Xi＋……dn×XnM，使得Xi＋……Xn最小請選擇貪心策略，并設(shè)計(jì)貪心算法。解：貪心原則：每次選擇最大面值硬幣。CU←M;i←1;X←0//X為解向量WhileCU≠0doX[i]←CUdivd[i]//X[i]為第i中硬幣數(shù)CU←CU-d[i]*X[i]i←i+1;repeat3.有n個(gè)物品，已知n=7,利潤為P=(10,5,15,7,6,18,3)，重量W=(2,3,5,7,1,4,1)，背包容積M=15,物品只能選擇全部裝入背包或不裝入背包，設(shè)計(jì)貪心算法，并討論是否可獲最優(yōu)解。解：定義結(jié)構(gòu)體數(shù)組G，將物品編號、利潤、重量作為一個(gè)結(jié)構(gòu)體：例如G[k]={1,10,2}求最優(yōu)解，按利潤/重量的遞減序，有{5,6,1,6}{1,10,2,5}{6,18,4,9/2}{3,15,5,3}{7,3,1,3}{2,5,3,5/3}{4,7,7,1}算法procedureKNAPSACK(P，W，M，X，n)//P(1：n)和W(1；n)分別含有按P(i)/W(i)≥P(i+1)/W(i+1)排序的n件物品的效益值和重量。M是背包的容量大小，而x(1：n)是解向量/