北航研究生算法(208精心整理)

1、文案大全一：判斷題1、一個(gè)正確的算法，對(duì)于每個(gè)合法輸入，都會(huì)在有限的時(shí)間內(nèi)輸出一個(gè)滿足要求的結(jié)果。(對(duì))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è)決策。(錯(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ì)算。(對(duì))8、若P2多項(xiàng)式時(shí)間轉(zhuǎn)化為(polynomialt

2、ransformsto)P1,則P2至少與P1一樣難。(錯(cuò)9、快速排序算法的平均時(shí)間復(fù)雜度是O(nlogn),使用隨機(jī)化快速排序算法可以將平均時(shí)間復(fù)雜度降得更低。(錯(cuò))10、基于比較的尋找數(shù)組A1,n中最大元素的問題下屆是Q(n/3)。(錯(cuò))11、O(f(n)+O(g(n)=O(minf(n),g(n)(錯(cuò))12、若f(n)=Q(g(n)，g(n)=Q(h(n)，貝Uf(n)=Q(h(n)(對(duì))13、若f(n)=O(g(n),則g(n)=Q(f(n)(對(duì))14、貪婪技術(shù)所做的每一步選擇所產(chǎn)生的部分解，不一定是可行性的。(錯(cuò))15、LasVegas算法只要給出解就是正確的。(對(duì))16、一個(gè)完全多

3、項(xiàng)式近似方案是一個(gè)近似方案A，其中每一個(gè)算法A在輸入實(shí)例I的規(guī)模的多項(xiàng)式時(shí)間內(nèi)運(yùn)行。(錯(cuò))二：簡(jiǎn)答1、二叉查找樹屬于減治策略的三個(gè)變種中的哪一個(gè)的應(yīng)用？什么情況下二叉查找樹表現(xiàn)出最差的效率？此時(shí)的查找和插入算法的復(fù)雜性如何？答：減治策略有3個(gè)主要的變種，包括減常量、減常數(shù)因子和減可變規(guī)模。(1)二叉查找樹屬于減可變規(guī)模變種的應(yīng)用。(2)當(dāng)先后插入的關(guān)鍵字有序時(shí)，構(gòu)成的二叉查找樹蛻變?yōu)閱沃?，樹的深度等于n，此時(shí)二叉查找樹表現(xiàn)出最差的效率，(3)查找和插入算法的時(shí)間效率都屬于0(n)。2、何謂偽多項(xiàng)式算法？如何將一MonteCarlo算法轉(zhuǎn)化為L(zhǎng)asVegas算法？答：若一個(gè)數(shù)值算法的時(shí)間復(fù)雜度

4、可以表示為輸入數(shù)值N的多項(xiàng)式，但其運(yùn)行時(shí)間與輸入數(shù)值N的二進(jìn)制位數(shù)呈指數(shù)增長(zhǎng)關(guān)系，則稱其時(shí)間復(fù)雜度為偽多項(xiàng)式時(shí)間。LasVegas算法不會(huì)得到不正確的解。一旦用拉斯維加斯算法找到一個(gè)解，這個(gè)解就一定是正確解。但有時(shí)用拉斯維加斯算法找不到解。MonteCarlo算法每次都能得到問題的解，但不保證所得解的準(zhǔn)確性轉(zhuǎn)化：可以在MonteCarlo算法給出的解上加一個(gè)驗(yàn)證算法，如果正確就得到解，如果錯(cuò)誤就不能生成問題的解，這樣MonteCarlo算法便轉(zhuǎn)化為了LasVegas算法。3、構(gòu)造AVL樹和2-3樹的主要目的是什么？它們各自有什么樣的査找和插入的效率？答：(1)當(dāng)先后插入的關(guān)鍵字有序時(shí)，構(gòu)成的二

5、叉查找樹蛻變?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)不止包含一個(gè)元素。(2)AVL樹在最差情況下，查找和插入操作的效率屬于0(lgn)。2-3樹無論在最差還是平均情況下，查找和插入的效率都屬于0(logn)。4、寫出0/1背包問題的一個(gè)多項(xiàng)式等價(jià)(PolynomialEquivalent)的判定問題，并說明為什么它們是多項(xiàng)式等價(jià)的。答：0/1背包問題：從M件物品中，取出若干件放在空間為W的背包里，給出一個(gè)能獲得最

6、大價(jià)值的方案。每件物品的體積為W1，W2Wn，與之相對(duì)應(yīng)的價(jià)值為P1,P2Pn。+判定問題I：從M件物品中，取出若干件放在空間為W的背包里，是否存在一個(gè)方案，所獲價(jià)值三P*?。每件物品的體積為W1，W2Wn，與之相對(duì)應(yīng)的價(jià)值為P1,P2Pn。若判定問題I存在多項(xiàng)式時(shí)間的解法，則反復(fù)調(diào)用該算法就可以在多項(xiàng)式時(shí)間內(nèi)解決0/1背包的優(yōu)化問題。因而這個(gè)判定問題與原問題多項(xiàng)式等價(jià)。5、下面問題是否屬于NP問題？為什么？問題表述：給定圖中的兩個(gè)點(diǎn)、，整數(shù)和，圖中每條邊的長(zhǎng)度及便利這條邊的時(shí)間問圖中是否存在一條由到的路徑，使得其長(zhǎng)度大于，且遍歷時(shí)間小于？答：這個(gè)問題屬于NP問題。因?yàn)槿艚o出該問題的一個(gè)解，可

7、以在多項(xiàng)式時(shí)間內(nèi)檢驗(yàn)這個(gè)解的正確性。如給出一條由p到q的路徑，可以在多項(xiàng)式時(shí)間內(nèi)計(jì)算出它的長(zhǎng)度及遍歷時(shí)間，然后分別與C和t進(jìn)行比較，從而可以判斷這個(gè)解的對(duì)錯(cuò)。分治題1.寫出一個(gè)求解下列問題的分治算法，推導(dǎo)其時(shí)間復(fù)雜性并與蠻力法相比較。給定互不相等的n個(gè)數(shù)的一個(gè)序列，若其中某兩個(gè)數(shù)和的關(guān)系為：且，則稱和是逆序的。要求計(jì)算該序列中的逆序個(gè)數(shù)，即具有逆序關(guān)系的元素對(duì)的總數(shù)目。解：/*求解n個(gè)數(shù)的一個(gè)序列，具有逆序關(guān)系的元素對(duì)的總數(shù)目*/count=0;/逆序元素對(duì)的全局計(jì)數(shù)變量mergeInvertedPairs(A,low,mid,high)i=low;j=mid+1;k=low;tmpn;/用于

8、歸并排序的輔助數(shù)組whilei=mid&jAj)tmpk=Aj+;count+=(mid-i+1);/相比歸并排序，就多了這一條語句elsetmpk=Ai+;k+;whilei=midtmpk+=Ai+;whilej=hightmpk+=Aj+;for(j=low;j=high;j+)Aj=tmpj;findInvertedPairs(A,low,high)if(lowaj,那么說明需要調(diào)整次序，逆序數(shù)num=num+mid-i。fln二1;時(shí)間復(fù)雜度的迭代公式為T(n)因此算法的時(shí)間復(fù)雜度為T(n)=O(nlogn)；I2T(n/2)+O(n)n1;蠻力法的時(shí)間復(fù)雜度為O(n2)，當(dāng)n數(shù)目較

9、大時(shí)，分治法計(jì)算規(guī)模遠(yuǎn)小于蠻力法。2.為一個(gè)整數(shù)序列，中的整數(shù)如果在中出現(xiàn)次數(shù)多余，那么稱為多數(shù)元素。例如在序列中3是多數(shù)元素，因?yàn)槌霈F(xiàn)了4次，大于。求A的多數(shù)元素問題的蠻力算法復(fù)雜性如何？設(shè)計(jì)一個(gè)具有變治思想的算法，提高蠻力算法的效率，寫出偽代碼并分析其事件復(fù)雜性。采用減治的思想每一個(gè)減去一個(gè)元素，時(shí)間復(fù)雜度為O(n)，蠻力法的時(shí)間復(fù)雜度為0(n2)。動(dòng)態(tài)規(guī)劃題1.某工廠調(diào)查了解市場(chǎng)情況，估計(jì)在今后四個(gè)月內(nèi)，市場(chǎng)對(duì)其產(chǎn)品的需求量如下表所示。時(shí)期(月)需要量(產(chǎn)品單位)12233244已知：對(duì)每個(gè)月來講，生產(chǎn)一批產(chǎn)品的固定成本費(fèi)為3(千元)，若不生成，則為零。每生產(chǎn)單位產(chǎn)品的成本費(fèi)為1(千元)

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

11、k月的成本費(fèi),單位為(千元)，則=1,2,3,4;且x=0。1k=1,2,3;故指標(biāo)函數(shù)為令表示為由出發(fā)采用最優(yōu)生產(chǎn)方案到第4個(gè)月結(jié)束這段期間的產(chǎn)品成本。根據(jù)最優(yōu)化原理則有遞推公式其中：逆序計(jì)算的詳細(xì)步驟如下(1)當(dāng)k=4時(shí)，(2)當(dāng)k=3時(shí),當(dāng)當(dāng)當(dāng)當(dāng)當(dāng)當(dāng)當(dāng)(3)有當(dāng)當(dāng)?shù)米钚≈诞?dāng)小值。當(dāng)當(dāng)k=2時(shí)，因?yàn)榇藭r(shí),此時(shí),此時(shí),此時(shí),此時(shí),此時(shí),此時(shí)因?yàn)?在,在,在所以有：處取得最小值。處取得最小值處取得最小值。處取得最小值。處取得最小值。處取得最小值。處取得最小值。，且,在，且所以當(dāng)最小值。時(shí)，時(shí)時(shí)，時(shí)，處取得最小值。時(shí),在,且在處取得最小值。處取,在處取得最，且在,且在處取得當(dāng)時(shí)，,且在處取得最小

12、值。當(dāng)時(shí)，,且在處取得最小值。(4)當(dāng)k=1時(shí)，因?yàn)?所以有：當(dāng),且在處取得最小值。綜上所述，最優(yōu)的庫(kù)存方案為：第一月生產(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ù)額下(以萬元為單位)的利潤(rùn)如下表投資額盈利項(xiàng)目012345678項(xiàng)目105154080909598100項(xiàng)目20515406070737475項(xiàng)目30426404550515253請(qǐng)安排投資計(jì)劃，使總的利潤(rùn)最大。寫出你所設(shè)的狀態(tài)變量、決策變量、狀態(tài)轉(zhuǎn)移方程與遞推關(guān)系式和手工求解的詳細(xì)步驟及結(jié)構(gòu)解：狀態(tài)變量：xk表示留給項(xiàng)目k.n的投資

13、額，其中n為項(xiàng)目總個(gè)數(shù)，k=1.n.決策變量：uk表示投給項(xiàng)目k的投資額.允許決策集合：狀態(tài)轉(zhuǎn)移方程：遞推關(guān)系式：其中，表示項(xiàng)目k的投資額為uk時(shí)的盈利.針對(duì)本題，n=3，xk最大取8手工詳解過程：初始化k=3X3012345678f3(x3)0426404550515253k=2X2012345678f2(x2)052640607086100110k=1xi012345678f1(xj0526408090106120140最終結(jié)果：給項(xiàng)目1投資4萬元，項(xiàng)目2投資4萬元，項(xiàng)目3不投資，將獲得最大利潤(rùn)140萬元.仏用分支宦界法求解以下問題：（本題8分）L）某部門欲建立聯(lián)通分布于五個(gè)區(qū)的共50個(gè)站

14、點(diǎn)的有線吧贈(zèng)帕豐醴陸鼬線昭敷設(shè)費(fèi)用由對(duì)稱矩陣C蛤乩枉意兩站屜間敷設(shè)拔怖建設(shè)的地井黑巴蠶眾霧曹為也墮亟莖？便初需建設(shè)您能假i驚過加爍且需跨區(qū)敷設(shè)的線路總數(shù)口不超過WAX（各站M屬的區(qū)由同宣給出幾L說明你屋如何枸造搜累樹的要求崽5九斷“柵陣）2說明尊法遍歷搜索樹的愎則何時(shí)以及如阿蘭如分支丿鸞巳鸞爭(zhēng)乳禰設(shè)計(jì)的分支定界算法的睜界是什么，它為什么是疋確的和有攻初4.寫出偽代碼“線路題的某種深搜解法：1）可以根據(jù)線路（l1,l2,.,lm）的取舍構(gòu)建一棵m層二叉搜索樹。第i層的所有左分支表示鋪設(shè)線路li，右分支則表示不鋪設(shè)。如果存在可行解，遍歷此二叉搜索樹即可找到最優(yōu)解。2）前進(jìn)：當(dāng)前節(jié)點(diǎn)未被剪枝并且仍有

15、子節(jié)點(diǎn)即可繼續(xù)前進(jìn)。分支：先遍歷左分支，后遍歷右分支。回溯：左右分支都被遍歷時(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）按費(fèi)用從小到大排序所有路線l1,l2,.,lm計(jì)算子問題下界：1。費(fèi)用下界：剩余站點(diǎn)數(shù)量-最小花費(fèi)#累計(jì)最小的線路花費(fèi)

16、即可得到，下同2。地井?dāng)?shù)下界：剩余站點(diǎn)數(shù)量-最小地井?dāng)?shù)3?？鐓^(qū)線路數(shù)下界：剩余站點(diǎn)數(shù)量-最小跨區(qū)線路數(shù)search（空集，11）返回最優(yōu)結(jié)果defsearch（線路集合S,當(dāng)前線路1）:判斷線路集合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（SU1,1的下一條路線）search（S,1的下一條路線）五、用分支定界法求解以下問題：本題B分島國(guó)與B國(guó)之間尚耒應(yīng)接通崗a與A國(guó)直接

17、通商的有酣個(gè)國(guó)家CC1,C2C2O）：與心國(guó)j按通商的拘另外30個(gè)國(guó)家（C2I,C22,宀C5O）,上述個(gè)國(guó)家CC,C2*.,C5O）間并不是每?jī)蓚€(gè)國(guó)家都魚接通裔.任意西國(guó)乏間的貿(mào)易稅率由對(duì)稱矩陣R給出，其;中g(shù)代表兩國(guó)不能直接通商為國(guó)某公司與E國(guó)一公司欲通過某幾個(gè)屮間國(guó)家的公司完成一筆貿(mào)易，各個(gè)國(guó)家的進(jìn)出口貿(mào)易通關(guān)舒手續(xù)所需辦埋時(shí)間由向繪T給出請(qǐng)女拌一中轉(zhuǎn)貿(mào)揚(yáng)計(jì)劃.使得該交易所產(chǎn)生的向各屮轉(zhuǎn)國(guó)繳納的稅費(fèi)繪低且整個(gè)交易能堀在時(shí)間t內(nèi)完成.匚說明稱是如何構(gòu)趙搜索樹的.1要求是二叉搜索樹人2-說翱算法遍歷搜第樹的原則（何時(shí)以及如何前進(jìn)、分支、回溯、剪枝等等人乳你設(shè)計(jì)的分支定畀算法的界”是什么.它対

18、什么腿正硼的和有效的？4-寫出偽就碼”稅費(fèi)題的某種深搜解法：1）可以根據(jù)除A外的51個(gè)國(guó)家定義一棵若干層二叉搜索樹。每個(gè)節(jié)點(diǎn)的左分支表示選擇其代表的國(guó)家為下一個(gè)貿(mào)易順序上的國(guó)家，右分支則表示不選擇。構(gòu)造搜索樹需要兩個(gè)輔助變量，之前的貿(mào)易順序S（s為S的最后一個(gè)國(guó)家）和這一輪否決的國(guó)家V。任取可以和s國(guó)貿(mào)易的國(guó)家c（不屬于S和V）置于樹的當(dāng)前生成位置，然后用（S=S,c和V=空集）生成左子樹，用（S=S和V=VUc）生成右子樹。如果c不存在或者s=B則終止當(dāng)前子樹的生成。如此反復(fù)可以建立一棵二叉搜索樹。2）前進(jìn)：當(dāng)前節(jié)點(diǎn)未被剪枝并且仍有子節(jié)點(diǎn)即可繼續(xù)前進(jìn)。分支：先遍歷左分支，后遍歷右分支?；厮荩鹤笥曳种Ф急槐闅v時(shí)返回父節(jié)點(diǎn)。剪枝：剪枝條件如下：1。當(dāng)前稅費(fèi)+s國(guó)與B國(guó)貿(mào)易的最小稅費(fèi)=已知最優(yōu)方案的稅費(fèi)2。當(dāng)前時(shí)間+s國(guó)與B國(guó)貿(mào)易的最短時(shí)間t3）子問題的下界為稅費(fèi)下界和時(shí)間下界，均由dijkstra算法算法得到，表示某國(guó)與B國(guó)貿(mào)易的最小稅費(fèi)和最短時(shí)間。兩個(gè)結(jié)果均由弱化限制的方法得到，所以是正確的，計(jì)算復(fù)雜度也不高，當(dāng)然有效。父