北航研究生算法2018精心整理

1、一：判斷題1、一個(gè)正確的算法，對于每個(gè)合法輸入，都會(huì)在有限的時(shí)間內(nèi)輸出一個(gè)滿足要求的結(jié)果。（對）2、NP完全問題比其他所有NP問題都要難。（錯(cuò)）3、回溯法用深度優(yōu)先法或廣度優(yōu)先法搜索狀態(tài)空間樹。（錯(cuò)，僅深度優(yōu)先）4、在動(dòng)態(tài)規(guī)劃中，各個(gè)階段所確定的策略就構(gòu)成一個(gè)策略序列，通常稱為一個(gè)決策各個(gè)階段所確定的決策就構(gòu)成一個(gè)決策序列，通常稱為一個(gè)策略。（錯(cuò)）5、P類和NP類問題的關(guān)系用PNP來表示是錯(cuò)誤的。（錯(cuò)）6、若近似算法A求解某極小化問題一實(shí)例的解為Sa，且已知該問題的最優(yōu)解為Sa/3，則該近似算法的性能比精確度量為3。（錯(cuò)）7、通常來說，算法的最壞情況的時(shí)間復(fù)雜行比平均情況的時(shí)間復(fù)雜性容易計(jì)算。

2、（對）8、若P2多項(xiàng)式時(shí)間轉(zhuǎn)化為(polynomial transforms to)P1P1多項(xiàng)式時(shí)間轉(zhuǎn)化為P2，則P2至少與P1一樣難。（錯(cuò)）9、快速排序算法的平均時(shí)間復(fù)雜度是O(nlogn)，使用隨機(jī)化快速排序算法可以將平均時(shí)間復(fù)雜度降得更低。（錯(cuò)）10、基于比較的尋找數(shù)組A1,n中最大元素的問題下屆是(n/3)n-1。（錯(cuò)）11、O(f(n)+O(g(n)=O(minf(n),g(n)（錯(cuò)）12、若f(n)=(g(n)，g(n)=(h(n)，則f(n)=(h(n)（對）13、若f(n)=O(g(n)，則g(n)=(f(n)（對）O(f(n)+O(g(n) = O(maxf(n),g(n)

3、 O(f(n)+O(g(n) = O(f(n)+g(n) O(f(n)*O(g(n) = O(f(n)*g(n) O(cf(n) = O(f(n) f(n)= O(g(n)， g(n)= O (h(n) Þ f(n)= O (h(n)；f(n)= W(g(n)， g(n)= W (h(n) Þ f(n)= W(h(n)； f(n)= Q(g(n)， g(n)= Q(h(n) Þ f(n)= Q(h(n)；f(n)= Q(g(n) Û g(n)= Q (f(n) .f(n)= O(g(n) Û g(n)= W (f(n) ；14、貪婪技術(shù)所做的每

4、一步選擇所產(chǎn)生的部分解，不一定是可行性的。（錯(cuò)）15、LasVegas算法只要給出解就是正確的。（對）16、一個(gè)完全多項(xiàng)式近似方案是一個(gè)近似方案A，其中每一個(gè)算法A在輸入實(shí)例I的規(guī)模的多項(xiàng)式時(shí)間內(nèi)運(yùn)行。一個(gè)多項(xiàng)式近似方案(PAS)是一個(gè)近似方案A,其中每一個(gè)算法A 在輸入實(shí)例I的規(guī)模的多項(xiàng)式時(shí)間內(nèi)運(yùn)行;一個(gè)完全多項(xiàng)式近似方案(FPAS)是一個(gè)近似方案A,其中每個(gè)算法 A在以輸入實(shí)例的規(guī)模和1/兩者的多項(xiàng)式時(shí)間內(nèi)運(yùn)行.（錯(cuò)）二：簡答1、 二叉查找樹屬于減治策略的三個(gè)變種中的哪一個(gè)的應(yīng)用？什么情況下二叉查找樹表現(xiàn)出最差的效率？此時(shí)的查找和插入算法的復(fù)雜性如何？答：減治策略有3個(gè)主要的變種，包括減常

5、量、減常數(shù)因子和減可變規(guī)模。(1) 二叉查找樹屬于減可變規(guī)模變種的應(yīng)用。(2) 當(dāng)先后插入的關(guān)鍵字有序時(shí)，構(gòu)成的二叉查找樹蛻變?yōu)閱沃洌瑯涞纳疃鹊扔趎，此時(shí)二叉查找樹表現(xiàn)出最差的效率，(3) 查找和插入算法的時(shí)間效率都屬于(n)。2、 何謂偽多項(xiàng)式算法？如何將一Monte Carlo算法轉(zhuǎn)化為Las Vegas算法？答：若一個(gè)數(shù)值算法的時(shí)間復(fù)雜度可以表示為輸入數(shù)值N的多項(xiàng)式，但其運(yùn)行時(shí)間與輸入數(shù)值N的二進(jìn)制位數(shù)呈指數(shù)增長關(guān)系，則稱其時(shí)間復(fù)雜度為偽多項(xiàng)式時(shí)間。Las Vegas算法不會(huì)得到不正確的解。一旦用拉斯維加斯算法找到一個(gè)解，這個(gè)解就一定是正確解。但有時(shí)用拉斯維加斯算法找不到解。Monte

6、 Carlo算法每次都能得到問題的解，但不保證所得解的準(zhǔn)確性轉(zhuǎn)化：可以在Monte Carlo算法給出的解上加一個(gè)驗(yàn)證算法，如果正確就得到解，如果錯(cuò)誤就不能生成問題的解，這樣Monte Carlo算法便轉(zhuǎn)化為了Las Vegas算法。3、 構(gòu)造AVL樹和2-3樹的主要目的是什么？它們各自有什么樣的查找和插入的效率？答：(1)當(dāng)先后插入的關(guān)鍵字有序時(shí)，構(gòu)成的二叉查找樹蛻變?yōu)閱沃?，樹的深度等于n，此時(shí)二叉查找樹表現(xiàn)出最差的效率，為了解決這一問題，可以構(gòu)造AVL樹或2-3樹，使樹的深度減小。一棵AVL樹要求它的每個(gè)節(jié)點(diǎn)的左右子樹的高度差不能超過1。2-3樹和2-3-4樹允許一棵查找樹的單個(gè)節(jié)點(diǎn)不止

7、包含一個(gè)元素。(2) AVL樹在最差情況下，查找和插入操作的效率屬于(lgn)。2-3樹無論在最差還是平均情況下，查找和插入的效率都屬于(log n)。4、 寫出0/1背包問題的一個(gè)多項(xiàng)式等價(jià)(Polynomial Equivalent)的判定問題，并說明為什么它們是多項(xiàng)式等價(jià)的。答：0/1背包問題：從M件物品中，取出若干件放在空間為W的背包里，給出一個(gè)能獲得最大價(jià)值的方案。每件物品的體積為W1，W2Wn，與之相對應(yīng)的價(jià)值為P1,P2Pn。+判定問題I：從M件物品中，取出若干件放在空間為W的背包里，是否存在一個(gè)方案，所獲價(jià)值P*？。每件物品的體積為W1，W2Wn，與之相對應(yīng)的價(jià)值為P1,P2P

8、n。若判定問題I存在多項(xiàng)式時(shí)間的解法，則反復(fù)調(diào)用該算法就可以在多項(xiàng)式時(shí)間內(nèi)解決0/1背包的優(yōu)化問題。因而這個(gè)判定問題與原問題多項(xiàng)式等價(jià)。5、 下面問題是否屬于NP問題？為什么？問題表述：給定圖G=(N,A)中的兩個(gè)點(diǎn)p、q，整數(shù)c和t，圖G中每條邊的長度cij及便利這條邊的時(shí)間tij，問圖G中是否存在一條由p到q的路徑，使得其長度大于c，且遍歷時(shí)間小于t？答：這個(gè)問題屬于NP問題。因?yàn)槿艚o出該問題的一個(gè)解，可以在多項(xiàng)式時(shí)間內(nèi)檢驗(yàn)這個(gè)解的正確性。如給出一條由p到q的路徑，可以在多項(xiàng)式時(shí)間內(nèi)計(jì)算出它的長度及遍歷時(shí)間，然后分別與C和t進(jìn)行比較，從而可以判斷這個(gè)解的對錯(cuò)。分治題1. 寫出一個(gè)求解下列問

9、題的分治算法，推導(dǎo)其時(shí)間復(fù)雜性并與蠻力法相比較。給定互不相等的n個(gè)數(shù)的一個(gè)序列a1,a2,an，若其中某兩個(gè)數(shù)ai和aj的關(guān)系為：ai>aj且i<j，則稱ai和aj是逆序的。要求計(jì)算該序列中的逆序個(gè)數(shù)，即具有逆序關(guān)系的元素對的總數(shù)目。解：/* *求解n個(gè)數(shù)的一個(gè)序列，具有逆序關(guān)系的元素對的總數(shù)目*/count = 0;/逆序元素對的全局計(jì)數(shù)變量mergeInvertedPairs(A,low,mid,high) i = low;j = mid+1;k = low;tmpn;/用于歸并排序的輔助數(shù)組while i <= mid && j <= high i

10、f (Ai > Aj) tmpk = Aj+;count += (mid-i+1);/相比歸并排序，就多了這一條語句 else tmpk = Ai+;k+;while i <= mid tmpk+ = Ai+;while j <= high tmpk+ = Aj+;for (j = low; j <= high; j+) Aj = tmpj;findInvertedPairs(A, low, high) if (low < high) mid = (low+high) / 2;findInvertedPairs(A,low,mid);findInvertedPai

11、rs(A,mid+1,high);mergeInvertedPairs(A,low,mid,high);算法思路：以歸并排序?yàn)榛A(chǔ)，在兩兩集合合并的時(shí)候如果前一個(gè)集合的元素ai>aj，那么說明需要調(diào)整次序，逆序數(shù)num=num+mid-i。時(shí)間復(fù)雜度的迭代公式為 因此算法的時(shí)間復(fù)雜度為T(n)=O(nlogn)；蠻力法的時(shí)間復(fù)雜度為O(n2)，當(dāng)n數(shù)目較大時(shí)，分治法計(jì)算規(guī)模遠(yuǎn)小于蠻力法。2. A1,n為一個(gè)整數(shù)序列，A中的整數(shù)a如果在A中出現(xiàn)次數(shù)多余n/2，那么a稱為多數(shù)元素。例如，在序列1,3,2,3,3,4,3中3是多數(shù)元素，因?yàn)槌霈F(xiàn)了4次，大于7/2。求A的多數(shù)元素問題的蠻力算法復(fù)

12、雜性如何？設(shè)計(jì)一個(gè)具有變治思想的算法，提高蠻力算法的效率，寫出偽代碼并分析其事件復(fù)雜性。2. num <- src0; count <- 0; for i <- 0 to n-1 do if(num = srci) count+; else count-; if(count < 0) num <- srci; count = 0; 采用減治的思想每一個(gè)減去一個(gè)元素，時(shí)間復(fù)雜度為O(n)，蠻力法的時(shí)間復(fù)雜度為O(n2)。動(dòng)態(tài)規(guī)劃題1. 某工廠調(diào)查了解市場情況，估計(jì)在今后四個(gè)月內(nèi)，市場對其產(chǎn)品的需求量如下表所示。時(shí)期（月）需要量（產(chǎn)品單位）12233244已知：對每個(gè)

13、月來講，生產(chǎn)一批產(chǎn)品的固定成本費(fèi)為3（千元），若不生成，則為零。每生產(chǎn)單位產(chǎn)品的成本費(fèi)為1（千元）。同時(shí)，在任何一個(gè)月內(nèi)，生產(chǎn)能力所允許的最大生產(chǎn)批量為不超過6個(gè)單位。又知：每單位產(chǎn)品的庫存費(fèi)用為每月0.5（千元），同時(shí)要求在第一個(gè)月開始之初，及在第四個(gè)月末，均無產(chǎn)品庫存。問：在滿足上述條件下，該廠應(yīng)如何安排各個(gè)時(shí)期的生產(chǎn)與庫存，使所花的總成本費(fèi)用最低？寫出你所設(shè)的狀態(tài)變量、決策變量、狀態(tài)轉(zhuǎn)移方程與遞推關(guān)系式，和手工求解的詳細(xì)步驟及結(jié)果。解：設(shè)階段序數(shù)k表示月份，狀態(tài)變量xk為第k個(gè)月初擁有的單位產(chǎn)品數(shù)量，亦為第k-1月末時(shí)的單位產(chǎn)品數(shù)量，決策變量uk為第k個(gè)月生產(chǎn)的單位產(chǎn)品數(shù)量，ck為第k月

14、份需要的產(chǎn)品數(shù)量，這里xk和uk均取離散變量。狀態(tài)轉(zhuǎn)移方程為： xk+1=xk+uk-ck , k =1,2,3,4; 且x1=0。k段允許決策集合為: Dkxk=max(0,ck-xk)uk6, k = 1,2,3; 當(dāng)k=4時(shí)，uk=ck-xk。設(shè)vk(xk,uk)為第k月的成本費(fèi),單位為(千元)，則 vk=0.5*xk+uk+Iuk,Iuk=3, &uk>00, &uk=0故指標(biāo)函數(shù)為 V1,4=k=14vk令fkxk表示為由xk出發(fā)采用最優(yōu)生產(chǎn)方案到第4個(gè)月結(jié)束這段期間的產(chǎn)品成本。根據(jù)最優(yōu)化原理，則有遞推公式： fkxk=0, k=5fkxk=ukDkxkmin0

15、.5*xk+uk+Iuk+fk+1xk+uk-ck, &k=1,2,3,4其中： ck=2, k=13, k=22, k=34, k=4逆序計(jì)算的詳細(xì)步驟如下：(1) 當(dāng)k=4時(shí)， f4x4=u4D4x4min0.5*x4+u4+Iu4=2 x4=4, u4=05.5 x4=3,u4=16 x4=2,u4=26.5 x4=1,u4=37 x4=0,u4=4(2) 當(dāng)k=3時(shí)，因?yàn)?x4=x3+u3-c3=x3+u3-24,u3+x3=x4+22,6，且u36所以有：當(dāng)x3=0,u3=6,5,4,3,2,此時(shí)f3x3=min11,13.5,13,12.5,12=11, 在u3=6,u4=

16、0處取得最小值。當(dāng)x3=1,u3=5,4,3,2,1,此時(shí)f3x3=min10.5,13,12.5,12,11.5=10.5,在u3=5,u4=0處取得最小值。當(dāng)x3=2,u3=4,3,2,1,0,此時(shí)f3x3=min10,12.5,12,11.5,8=8,在u3=0,u4=4處取得最小值。當(dāng)x3=3,u3=3,2,1,0,此時(shí)f3x3=min9.5,12,11.5,8=8,在u3=0,u4=4處取得最小值。當(dāng)x3=4,u3=2,1,0,此時(shí)f3x3=min9,11.5,8=8,在u3=0,u4=4處取得最小值。當(dāng)x3=5,u3=1,0,此時(shí)f3x3=min8.5,8=8,在u3=0,u4=4

17、處取得最小值。當(dāng)x3=6,u3=0,此時(shí)f3x3=min5=5,在u3=0,u4=0處取得最小值。(3) 當(dāng)k=2時(shí)，因?yàn)閤3=x2+u2-c2=x2+u2-36,u2+x2=x3+33,9，且x26,u26所以有：當(dāng)x2=0,u2=(6,5,4,3)時(shí)，f2x2=min17,16,17.5,17=16,在u2=5,u3=0,u4=4處取得最小值。當(dāng)x2=1,u2=(6,5,4,3,2)時(shí)，f2x2=min17.5,16.5,15.5,17,16.5=15.5,且在u2=4,u3=0,u4=4處取得最小值。當(dāng)x2=2,u2=(6,5,4,3,2,1)時(shí)，f2x2=min18,17,16,15,

18、16.5,16=15,在u2=3,u3=0,u4=4處取得最小值。當(dāng)x2=3,u2=(6,5,4,3,2,1,0)時(shí)，f2x2=min15.5,17.5,16.5,15.5,14.5,16,12.5=12.5，且在u2=0,u3=6,u4=0處取得最小值。當(dāng)x2=4,u2=(5,4,3,2,1,0)時(shí)，f2x2=min15,17,16,15,14,12.5=12.5,且在u2=0,u3=5,u4=0處取得最小值。當(dāng)x2=5,u2=(4,3,2,1,0)時(shí)，f2x2=min14.5,16.5,15.5,14.5,10.5=10.5,且在u2=0,u3=0,u4=4處取得最小值。當(dāng)x2=6,u2=

19、(3,2,1,0)時(shí)，f2x2=min14,16,15,14.5,11=11,且在u2=0,u3=0,u4=4處取得最小值。(4) 當(dāng)k=1時(shí)，因?yàn)閤1=0,x2=x1+u1-c1=u1-26,u1=x2+22,6,所以有：當(dāng)u1=(6,5,4,3,2), f1x1=min21.5,20.5,22,21.5,21=20.5,且在u1=5,u2= 0,u3=6,u4=0處取得最小值。綜上所述，最優(yōu)的庫存方案為：第一月生產(chǎn)5單位產(chǎn)品，第二月和第四月不生產(chǎn)，第三月生產(chǎn)6單位產(chǎn)品。2. 用動(dòng)態(tài)規(guī)劃方法手工求解以下問題有8萬元的投資可以投給3個(gè)過目，每個(gè)項(xiàng)目在不同筒子數(shù)額下（以萬元為單位）的利潤如下表投

20、資額盈利項(xiàng)目012345678項(xiàng)目105154080909598100項(xiàng)目20515406070737475項(xiàng)目30426404550515253請安排投資計(jì)劃，使總的利潤最大。寫出你所設(shè)的狀態(tài)變量、決策變量、狀態(tài)轉(zhuǎn)移方程與遞推關(guān)系式和手工求解的詳細(xì)步驟及結(jié)構(gòu)。解：狀態(tài)變量：xk 表示留給項(xiàng)目k.n的投資額，其中n為項(xiàng)目總個(gè)數(shù)，k=1.n.決策變量：uk 表示投給項(xiàng)目k的投資額.允許決策集合： Dkxk=uk | 0ukxk狀態(tài)轉(zhuǎn)移方程： xk+1=xk-uk遞推關(guān)系式： fkxk=ukDkxkmax gkuk+fk+1xk-uk k=n-1,1fnxn=gnxn 其中，gkuk表示項(xiàng)目k的投

21、資額為uk時(shí)的盈利.針對本題，n = 3，xk最大取8手工詳解過程：1. 初始化k = 3f30=0;f31=4;f32=26;f33=40;f34=45;f35=50;f36=51;f37=52;f38=53. x3012345678f3(x3)04264045505152532. k = 2f20=maxg20+f30=0+0=0;f21=maxg20+f31,g21+f30=max0+4,5+0=5;f22=maxg20+f32,g21+f31,g22+f30=max0+26,5+4,15+0=26;f23=maxg20+f33,g21+f32,g22+f31,g23+f30=max0+

22、40,5+26,15+4,40+0=40;f24=maxg20+f34,g21+f33,g22+f32,g23+f31,g24+f30=max0+45,5+40,15+26,40+4,60+0=60;f25=maxg20+f35,g21+f34,g22+f33,g23+f32,g24+f31,g25+f30=max0+50,5+45,15+40,40+26,60+4,70+0=70;f26=maxg20+f36,g21+f35,g22+f34,g23+f33,g24+f32,g25+f31,g26+f30=max0+51,5+50,15+45,40+40,60+26,70+4,73+0=86;

23、f27=maxg20+f37,g21+f36,g22+f35,g23+f34,g24+f33,g25+f32,g26+f31,g27+f30=max0+52,5+51,15+50,40+45,60+40,70+26,73+4,74+0=100;f28=maxg20+f38,g21+f37,g22+f36,g23+f35,g24+f34,g25+f33,g26+f32,g27+f31,g28+f30=max0+53,5+52,15+51,40+50,60+45,70+40,73+26,74+4,75+0=110.x2012345678f2(x2)0526406070861001103. k =

24、1f18=maxg10+f28,g11+f27,g12+f26,g13+f25,g14+f24,g15+f23,g16+f22,g17+f21,g18+f20=max0+110,5+100,15+86,40+70,80+60,90+40,95+26,98+5,100+0=140x1012345678f1(x1)0526408090106120140最終結(jié)果：給項(xiàng)目1投資4萬元，項(xiàng)目2投資4萬元，項(xiàng)目3不投資，將獲得最大利潤140萬元.線路題的某種深搜解法：1)可以根據(jù)線路(l1,l2,.,lm)的取舍構(gòu)建一棵m層二叉搜索樹。第i層的所有左分支表示鋪設(shè)線路li，右分支則表示不鋪設(shè)。如果存在可行解

25、，遍歷此二叉搜索樹即可找到最優(yōu)解。2)前進(jìn)：當(dāng)前節(jié)點(diǎn)未被剪枝并且仍有子節(jié)點(diǎn)即可繼續(xù)前進(jìn)。分支：先遍歷左分支，后遍歷右分支?；厮荩鹤笥曳种Ф急槐闅v時(shí)返回父節(jié)點(diǎn)。剪枝：剪枝條件如下：1。有環(huán)路2。當(dāng)前地井?dāng)?shù) + 地井?dāng)?shù)下界 > UMAX3。當(dāng)前跨區(qū)鋪設(shè)線路數(shù) + 跨區(qū)鋪設(shè)線路數(shù)下界 > DMAX4。當(dāng)前費(fèi)用 + 費(fèi)用下界 >= 已知最優(yōu)方案的費(fèi)用3)子問題的下界為費(fèi)用下界、地井?dāng)?shù)下界、跨區(qū)線路數(shù)下界。費(fèi)用下界是根據(jù)剩余站點(diǎn)數(shù)量定義的，累計(jì)最小的路線花費(fèi)即可得到。由于限制被極度弱化，所以非常粗糙，但是正確有效。另外兩個(gè)下界也類似。父問題的上界是已知最優(yōu)方案的費(fèi)用，顯然正確有效。4)

26、按費(fèi)用從小到大排序所有路線l1,l2,.,lm計(jì)算子問題下界：1。費(fèi)用下界：剩余站點(diǎn)數(shù)量->最小花費(fèi)#累計(jì)最小的線路花費(fèi)即可得到，下同2。地井?dāng)?shù)下界：剩余站點(diǎn)數(shù)量->最小地井?dāng)?shù)3。跨區(qū)線路數(shù)下界：剩余站點(diǎn)數(shù)量->最小跨區(qū)線路數(shù)search(空集, l1)返回最優(yōu)結(jié)果def search(線路集合S，當(dāng)前線路l):判斷線路集合S是否合格，條件如下：1。無環(huán)路2。當(dāng)前地井?dāng)?shù) + 地井?dāng)?shù)下界 <= UMAX3。當(dāng)前跨區(qū)鋪設(shè)線路數(shù) + 跨區(qū)鋪設(shè)線路數(shù)下界 <= DMAX4。當(dāng)前費(fèi)用 + 費(fèi)用下界 < 已知最優(yōu)方案的費(fèi)用如果合格：當(dāng)前網(wǎng)絡(luò)已經(jīng)覆蓋所有站點(diǎn):記S為已知最優(yōu)否則若剩下的線路數(shù)有可能使所有站點(diǎn)構(gòu)成網(wǎng)絡(luò):search(S l, l的下一