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

1、算法設(shè)計(jì)與分析復(fù)習(xí)題1、分治法的基本思想：是將一個(gè)規(guī)模為N的問(wèn)題分解為K個(gè)規(guī)模較小的子問(wèn)題，這些子問(wèn)題互相獨(dú)立且與原問(wèn)題相同。遞歸地解這些子問(wèn)題，然后將各子問(wèn)題的解合并得到原問(wèn)題的解。2、貪心選擇性質(zhì)：指所求問(wèn)題的整體最優(yōu)解可以通過(guò)一系列局部最優(yōu)的選擇，3、什么是剪枝函數(shù)：回溯法搜索解空間樹(shù)時(shí)，通常采用兩種策略避免無(wú)效搜索，提高回溯法的搜索效率。其一是用約束函數(shù)在擴(kuò)展結(jié)點(diǎn)處剪去不滿足約束的子樹(shù)；其二是用限界函數(shù)剪去得不到最優(yōu)解的子樹(shù)。這兩類(lèi)函數(shù)統(tǒng)稱(chēng)為剪枝函數(shù)。4、分支限界法的基本思想：(1)分支限界法常以廣度優(yōu)先或以最小耗費(fèi)(最大效益)優(yōu)先的方式搜索問(wèn)題的解空間樹(shù)。(2)在分支限界法中，每一個(gè)

2、活結(jié)點(diǎn)只有一次機(jī)會(huì)成為擴(kuò)展結(jié)點(diǎn)。活結(jié)點(diǎn)一旦成為擴(kuò)展結(jié)點(diǎn)，就一次性產(chǎn)生其所有兒子結(jié)點(diǎn)。在這些兒子結(jié)點(diǎn)中，導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的兒子結(jié)點(diǎn)被舍棄，其余兒子結(jié)點(diǎn)被加入活結(jié)點(diǎn)表中。(3)此后，從活結(jié)點(diǎn)表中取下一結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)，并重復(fù)上述結(jié)點(diǎn)擴(kuò)展過(guò)程，這個(gè)過(guò)程一直持續(xù)到找到所需的解或活結(jié)點(diǎn)表這空時(shí)為止。5、什么是算法的復(fù)雜性：是該算法所需要的計(jì)算機(jī)資源的多少，它包括時(shí)間和空間資源。6、最優(yōu)子結(jié)構(gòu)性質(zhì)：該問(wèn)題的最優(yōu)解包含著其子問(wèn)題的最優(yōu)解。7、回溯法：是一個(gè)既帶有系統(tǒng)性又帶有跳躍性的搜索算法。這在問(wèn)題的解空間樹(shù)中，按深度優(yōu)先策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹(shù)。算法搜索至解空間樹(shù)的任一結(jié)點(diǎn)時(shí)，先判斷該

3、結(jié)點(diǎn)是否包含問(wèn)題的解。如果肯定不包含，則跳過(guò)對(duì)以該結(jié)點(diǎn)為根的子樹(shù)的搜索，逐層向其祖先結(jié)點(diǎn)回溯；否則，進(jìn)入該子樹(shù)，繼續(xù)按深度優(yōu)先策略搜索。8、什么是分支定界法：對(duì)有約束條件的最優(yōu)化問(wèn)題所有可行解定向、適當(dāng)?shù)剡M(jìn)行搜索。將可行解空間不斷地劃分為越來(lái)越小的子集（分支），并為每一個(gè)子集的解計(jì)算一個(gè)上界和下界（定界）。9、算法滿足的性質(zhì)：輸入、輸出、確定性、有限性。10、遞歸算法的優(yōu)點(diǎn)：結(jié)構(gòu)清晰，可讀性強(qiáng)，容易用數(shù)學(xué)歸納法來(lái)證明算法的正確性，因此它為設(shè)計(jì)算法、調(diào)試程序帶來(lái)很大方便。11、回溯法效率的因素：（1）產(chǎn)生xk的時(shí)間。（2）滿足顯約束的xk值的個(gè)數(shù)。（3）計(jì)算約束函數(shù)constraint的時(shí)間。

4、（4）計(jì)算上界函數(shù)bound的時(shí)間。（5）滿足約束函數(shù)和上界函數(shù)約束的所有xk的個(gè)數(shù)12、最常見(jiàn)的分支限界法有兩種：隊(duì)列式（FIFO）分支限界法和優(yōu)先隊(duì)列式分支限界法。13、 什么是算法, 算法具有的特性是什么？是解決問(wèn)題的方法和過(guò)程, 1） 輸入0個(gè)或多個(gè)信息 2） 輸出至少一個(gè)信息 3） 確定性：組成算法的每個(gè)指令是清晰的，無(wú)二義的，整個(gè)過(guò)程是確定的 4） 有限性：14、 什么是動(dòng)態(tài)規(guī)劃法：將問(wèn)題分解成多級(jí)或許多子問(wèn)題，然后順序求解子問(wèn)題，前一個(gè)子問(wèn)題的解為后一個(gè)子問(wèn)題的求解提供有用的信息。15、 什么是貪心法：從問(wèn)題某一初始或推測(cè)值出發(fā)，一步步的攀登給定目標(biāo)，盡可能快的去逼近更好的解，當(dāng)

5、達(dá)到某一步不能繼續(xù)時(shí)終止。16、遞歸算法的缺點(diǎn)：運(yùn)行效率較低，耗費(fèi)的計(jì)算時(shí)間和占用的存儲(chǔ)空間都多。為了達(dá)到此目的，根據(jù)具體程序的特點(diǎn)對(duì)遞歸調(diào)用工作棧進(jìn)行簡(jiǎn)化，盡量減少棧操作，壓縮棧存儲(chǔ)空間以達(dá)到節(jié)省計(jì)算時(shí)間和存儲(chǔ)空間的目的。17、合并排序的時(shí)間復(fù)雜度是：T(n)=O(nlogn)。18、快速排序的時(shí)間復(fù)雜度是：T(n)=O(nlogn)。19、動(dòng)態(tài)規(guī)劃算法的基本要素：最優(yōu)子結(jié)構(gòu)性質(zhì)和子問(wèn)題重疊性質(zhì)。20、貪心算法的基本要素：貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。選擇題1、二分搜索算法是利用（分治策略 ）實(shí)現(xiàn)的算法。A、分治策略 B、動(dòng)態(tài)規(guī)劃法 C、貪心法 D、回溯法2、下列不是動(dòng)態(tài)規(guī)劃算法基本步驟的是

6、（D ）。A、找出最優(yōu)解的性質(zhì) B、構(gòu)造最優(yōu)解 C、算出最優(yōu)解 D、定義最優(yōu)解3、下列算法中通常以深度優(yōu)先方式系統(tǒng)搜索問(wèn)題解的是（c ）。A、備忘錄法 B、動(dòng)態(tài)規(guī)劃法 C、貪心法 D、回溯法4、最大效益優(yōu)先是（C ）的搜索方式。A、分支界限法 B、動(dòng)態(tài)規(guī)劃法 C、貪心法 D、回溯法5、0-1背包問(wèn)題的回溯算法所需的計(jì)算時(shí)間為（ b）O（n2n） B、O（nlogn） C、O（2n） D、O（n）簡(jiǎn)答題1、寫(xiě)出設(shè)計(jì)流水作業(yè)調(diào)度算法的主要步驟。2、舉例說(shuō)明貪心算法與動(dòng)態(tài)規(guī)劃算法的的主要差別。3、寫(xiě)出用回溯法搜索子集樹(shù)的一般算法。4、簡(jiǎn)述利用貪心算法解決“單源最短路徑”問(wèn)題的基本思想。5、簡(jiǎn)述分治法

7、的基本思想。6、寫(xiě)出設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法的主要步驟。7、簡(jiǎn)述分支限界法與回溯法的異同。8、寫(xiě)出用回溯法搜索排列樹(shù)的算法。算法題：01背包問(wèn)題：給定n種物品和一背包，物品i的重量是wi，其價(jià)值為vi，背包的容量為C。問(wèn)應(yīng)該如何裝入背包中物品的總價(jià)值最大？寫(xiě)出用分支限界算法解決該問(wèn)題的算法。例題1.選擇范例（1）分支限界法與回溯法都是在問(wèn)題的解空間樹(shù)T上搜索問(wèn)題的解，二者（）。A求解目標(biāo)不同，搜索方式相同B求解目標(biāo)不同，搜索方式也不同C求解目標(biāo)相同，搜索方式不同D求解目標(biāo)相同，搜索方式也相同（2）下列是動(dòng)態(tài)規(guī)劃算法基本要素的是（ ）。A、最優(yōu)子結(jié)構(gòu) B、構(gòu)造最優(yōu)解 C、算出最優(yōu)解 D、定義最優(yōu)解（3）

8、Strassen矩陣乘法是利用（ ）實(shí)現(xiàn)的算法。A、分治策略 B、動(dòng)態(tài)規(guī)劃法 C、貪心法 D、回溯法（4）下面不是分支界限法搜索方式的是（ ）。A、廣度優(yōu)先 B、最小耗費(fèi)優(yōu)先 C、最大效益優(yōu)先 D、深度優(yōu)先2.判斷范例（1）所有的遞歸函數(shù)都能找到對(duì)應(yīng)的非遞歸定義。（2）滿足最優(yōu)子結(jié)構(gòu)性質(zhì)必滿足貪心選擇性質(zhì)。（3）滿足貪心選擇性質(zhì)必滿足最優(yōu)子結(jié)構(gòu)性質(zhì)。（4）狀態(tài)空間樹(shù)中，只有展開(kāi)了所有子結(jié)點(diǎn)的結(jié)點(diǎn)才稱(chēng)為死結(jié)點(diǎn)。(5)變治法是基于變換的思想。分兩個(gè)階段工作，即“變”階段和“治”階段.變治法的三種類(lèi)型：1)實(shí)例化簡(jiǎn)(instance simplification)2)改變表現(xiàn)(representat

9、ion change)3)問(wèn)題化簡(jiǎn)(problem reduction)。例如AVL樹(shù)，多路查找樹(shù)都是實(shí)例化簡(jiǎn)的具體應(yīng)用。(6)時(shí)空權(quán)衡是指在算法的設(shè)計(jì)中，對(duì)算法的時(shí)間和空間作出權(quán)衡。常見(jiàn)的以空間換取時(shí)間的方法有：輸入增強(qiáng)（計(jì)數(shù)排序，串匹配算法的改進(jìn)）預(yù)構(gòu)造（散列法，B樹(shù)） (7)動(dòng)態(tài)規(guī)劃算法基本思想是將待求解問(wèn)題分解成若干個(gè)子問(wèn)題，并且經(jīng)分解得到的子問(wèn)題是互相獨(dú)立的。求解時(shí)有些子問(wèn)題被重復(fù)計(jì)算了許多次。2解釋下面術(shù)語(yǔ)哈密爾頓環(huán)貪心算法分枝限界方法0/1背包問(wèn)題算法3.簡(jiǎn)答范例簡(jiǎn)述回溯法求解問(wèn)題的一般步驟。簡(jiǎn)述狀態(tài)空間樹(shù)的廣度優(yōu)先展開(kāi)方法。狀態(tài)空間樹(shù)中的活結(jié)點(diǎn)、E-結(jié)點(diǎn)、死結(jié)點(diǎn)簡(jiǎn)述用回溯法設(shè)計(jì)

10、算法的步驟。舉例說(shuō)明最小生成樹(shù)在實(shí)際中的應(yīng)用。4.分析設(shè)計(jì)題上課反復(fù)講、反復(fù)強(qiáng)調(diào)的幾個(gè)問(wèn)題，要求懂原理，會(huì)設(shè)計(jì)（關(guān)鍵是思路，表達(dá)方法可以是語(yǔ)言、偽代碼、代碼），會(huì)進(jìn)行復(fù)雜度分析。建議：答題時(shí)不要把所有的東西寫(xiě)一大段，適當(dāng)分步驟、分要點(diǎn)，如XXX算法原理做什么，怎么做做什么，怎么做做什么，怎么做等8. 以下是分?jǐn)?shù)背包問(wèn)題的貪心算法算法 GREEDY_KANPSACK輸入：表示背包容量的實(shí)數(shù)C, 物品數(shù)n, 表示n個(gè)物品的體積和價(jià)值的實(shí)數(shù)數(shù)組s1.n和v1.n。輸出：裝入背包物品的最大總價(jià)值maxv和相應(yīng)的最優(yōu)解x1.n。 for i=1 to n yi=vi/si /求n個(gè)物品的單位體積價(jià)值y1.n。 end for /對(duì)y1.n按降序地址排序，排序結(jié)果返回到數(shù)組d1.n /中, 使得yd1=yd2=ydn。 d=sort(y, n) for i=1 to n xi=0 /對(duì)x1.n初始化。 i=1; maxv=0; rc=C /以下rc表示當(dāng)前背包的剩余容量。while _ a