算法設(shè)計與分析d卷及答案

1、算法設(shè)計與分析試題D及答案1 .填空題：(第小題每題4分，共20分)1 .一個算法的優(yōu)劣通常用 時間復(fù)雜度和空間復(fù)雜度 來度量。2 .遞歸函數(shù)的兩大基本要素是遞歸方程 和 邊界條件。3 .貪心算法和動態(tài)規(guī)劃算法都要求問題具有共同的性質(zhì)是最優(yōu)子結(jié)構(gòu)性質(zhì) 。4 .實例特征是指_決定問題規(guī)模的因素，如輸入數(shù)的大小及數(shù)據(jù)的數(shù)量等 。5 .在回溯法中，一個問題的解空間是指一個大的決策可由若干小的決策組成， 所有可能的決策序列 構(gòu)成該問題的解空間。具有 限界函數(shù) 的深度優(yōu)先生成法稱為回溯法。2 .簡答題：(每題5分，共20分)1 .分支限界法與回溯法的不同主要表現(xiàn)在兩個方面。(1)求解目標(biāo)：回溯法的求解目

2、標(biāo)是找出解空間樹中滿足約束條件的所有解，而分支限界 法的求解目標(biāo)則是找出滿足約束條件的一個解，或是在滿足約束條件的解中找出在某種意 義下的最優(yōu)解。(2)搜索方式的不同：回溯法常以深度優(yōu)先的方式搜索解空間樹，而分支限界法則以廣度 優(yōu)先或以最小耗費(fèi)優(yōu)先的方式搜索解空間樹。2 .給定如下二分搜索算法，請分析算法的復(fù)雜性。int BinarySearch(Type a口，const Type& x, int l, int r)while (r >= l)int m = (l+r)/2;if (x = am) return m;if (x < am) r = m-1; else l

3、= m+1;return -1;每執(zhí)行一次算法的 while循環(huán)，待搜索數(shù)組的大小減少一半。因此，在最壞情況下，while循環(huán)被執(zhí)行了 O(logn)、次。循環(huán)體內(nèi)運(yùn)算需要O(1)時間，因此整個算法在最壞情況下的計算時間復(fù)雜性為 O(logn)3 .什么是貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)？當(dāng)一個問題的最優(yōu)解包含其子問題的最優(yōu)解時，稱此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。所謂貪心選擇性質(zhì)是指所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心 選擇來達(dá)到。4.動態(tài)規(guī)劃算法的基本思想是什么？它和分治法有什么區(qū)別和聯(lián)系？答：動態(tài)規(guī)劃算法的基本思想為：該方法的思路也是將待求解的大問題分成規(guī)模較小的子問題，但所得的

4、各子問題之間有重復(fù)子問題，為了避免子問題的重復(fù)計算，可依自底向上的方式計算最優(yōu)值，并根據(jù)子問題的最優(yōu)值合并得到更大問題的最優(yōu)值，進(jìn)而可 構(gòu)造出所求問題的最優(yōu)解。分 治 法 也是將待求解的大問題分成若干個規(guī)模較小的相同子問題，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。規(guī)模縮小到一定的程度就可以容易地解決。所分解出的各個子問題是相互獨(dú)立的，即子問題之間不包含公共的子問題；利用該問題分解出的子問題的解可以合 并為該問題的解。三算法分析解答題：( (每小題20 分 , 共 60 分) )1 .給定給的n個作業(yè)1 , 2, 3,，n,每個作業(yè)所需處理的時間是Ti, T2,，Tn.請設(shè)計一個算法，給出作業(yè)調(diào)度方案，使

5、n個作業(yè)在盡可能短的時間內(nèi)由m臺機(jī)器加工處理完成。約定，每個作業(yè)均可在任何一臺機(jī)器上加工處理，但未完工前不允許中斷處理。作業(yè)不能拆分成更小的子作業(yè)。寫出求解問題的貪心算法。解：這個問題是NP完全問題，到目前為止還沒有有效的解法。對于這一類問題，用貪心選擇策略有時可以設(shè)計出較好的近似算法。采用最長處理時間作業(yè)優(yōu)先的貪心選擇策略可以設(shè)計出解多機(jī)調(diào)度問題的較好的近似算法。int Min(int E,m)k=0;min=maxint;for(i=1;i<=m;i+) if Ei< min min=Ei;k=i return k;void treat(int T,int Q, int E,

6、int n, int m)Sort(T, t, n); / h(i)=作業(yè) i 的排序序號, 按需要的處理時間的升序排序。for (int i = 1; i <= m; i+) Ei=0;for (int j = 1; j <=n; i+) Qij = -1; for (int i = 1; i <= n; i+) k=Min(E,m) ;Qkhi = i; / 作業(yè) i 分配給機(jī)器k 處理Ek+=Ti; Totalt=0;for (int i = 1; i <= m; i+) if Totalt < Ei Totalt = Ei;/ Totalt= 由m臺機(jī)器加

7、工處理完 n個作業(yè)所需的時間。2 .給定n種物品和一背包。物品i的重量是wi,其價值為vi ,背包的容量為 C。問應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大?請寫出動態(tài)規(guī)劃算法求解0-1 背 包問題。解答：1）定義最優(yōu)值設(shè)m（i, j）是背包容量為j ,可選擇物品為i , i+1 ,，n時0-1背包問題的最優(yōu)解的值。由 0-1 背包問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，可以建立計算m（i ， j） 的遞歸式如下：m(i,j)maxm(i 1, j),m(i 1, j m(i 1,j)wi) vi cjwii ii (1)0 jwivnjwnm(n,j)0n 0 j nwn(2)2) 計算最優(yōu)值v

8、oid knapsack(int v , int w , int c, int m )int n=v.length-1;int jMax=min(wn-1,c);/進(jìn)行(1)式賦值for( int j=0; j<=jMax; j+) mnj=0;for( int j=wn; j<=c; j+) mnj=vn;/進(jìn)行(2)式賦值for( int i=n-1; i>1; i-) /當(dāng)0<=j<wn/ j 為背包容量/當(dāng) wn <= j ， m(n,j) 賦值jMax=min(wi-1,c);for( int j=0; j<=jMax; j+) mij=mi

9、+1j;for(int j=wi; j<=c; j+)/當(dāng)0<=j<wi/當(dāng) wi <= j <= cmij=max(mi+1j, mi+1j-wi+vi);m1c=m2c;/當(dāng)0<=j<w1if (c>=w1)/當(dāng)w1 <= jm1c=max(m1c, m2c-w1+v1);3) 根據(jù)最優(yōu)值計算最優(yōu)解void traceback( int m , int w , int c, int x ) int n=w.length-1;for(int i=1; i<n; i+)if (mic=mi+1c) xi=0;else xi=1; c-=wi; xn=(mnc>0)? 1:0;/物品 i 沒有被選擇33 .設(shè)有n件工作分配給n個人。將工作i分配給j個人所需的費(fèi)用為 Cj .現(xiàn)要求為每 個人都分配1件不同的工作，并使總費(fèi)用達(dá)到最小。1）畫出該問題的解空間樹;2）設(shè)計回溯算法求解該問題解答：1）該問題的解空間樹是一棵排列樹，4件工作分配給4個人的排列樹如下:2)參考代碼如下：Void backtrack(int t)if ( t>n ) Compute。；elsefor (int j=t; j<=n; j+)swap(rt,rj);backtrack(t