1、式修理了火孚算法設計與分析大作業班 級：電子154姓 名：吳志勇學號：1049731503279任課老師：李瑞芳日期：2015.12.250-1背包問題的算法設計策略對比與分析0引言對于計算機科學來說，算法的概念是至關重要的。在一個大型軟件系統的開發中，設計出有效的 算法將起到決定性的作用。通俗的講，算法是解決問題的一種方法。也因此，算法分析與設計成為計算科學的核心問題之一，也是計算機科學與技術專業本科及研究生的一門重要的專業基礎課。算法 分析與設計是計算機軟件開發人員必修課，軟件的效率和穩定性取決于軟件中所采用的算法；對于一 般程序員和計算機專業學生，學習算法設計與分析課程，可以開闊編程思路

2、，編寫出優質程序。通過 老師的解析，培養我們怎樣分析算法的好“于 壞”，怎樣設計算法，并以廣泛用于計算機科學中的算法為例，對種類不同難度的算法設計進行系統的介紹與比較。本課程將培養學生嚴格的設計與分析算 法的思維方式，改變隨意拼湊算法的習慣。本課程要求具備離散數學、程序設計語言、數據結構等先 行課課程的知識。1算法復雜性分析的方法介紹算法復雜性的高低體現在運行該算法所需要的計算機資源的多少上，所需的資源越多，該算法的復雜性越高；反之，所需資源越少，該算法的復雜性越低。 對計算機資源，最重要的是時間與空間(即存儲器)資源。因此，算法的復雜性有時間復雜性T(n)與空間復雜性S(n)之分。算法復雜性

3、是算法運行所需要的計算機資源的量，這個量應集中反映算法的效率，并從運行該算 法的實際計算機中抽象出來，換句話說，這個量應該只依賴要解決的問題規模算法的輸入和算法本 身的函數。用C表示復雜性，N,I和A表示問題的規模、算法的輸入和算法本身規模，則有如下表達式：C=F(N,I,A) T=F(N , I,A) S=F(N , I,A)其中F(N,I,A)是一個三元函數。通常 A隱含在復雜性函數名當中，因此表達式中一般不寫Ao即：C=F(N,I) T=F(N,I) S=F(N,I)算法復雜性中時間與空間復雜性算法相似，所以以下算法復雜性主要以時間復雜性為例：算法的時間復雜性一般分為三種情況：最壞情況、

4、最好情況和平均情況。下面描述算法復雜性時 都是用的簡化的復雜性算法分析，引入了漸近意義的記號O,Q,。，和o。C表示漸近上界Q表示漸近下界：。表示同階即：f ( n)= Qg(n)且 f(n)= Q ( g(n)2常見的算法分析設計策略介紹2.1遞歸與分治策略分治法的設計思想是，將一個難以直接解決的大問題，分割成一些規模較小的相同問題，以 便各個擊破，分而治之。直接或間接地調用自身的算法稱為遞歸算法。用函數自身給出定義的函數稱為遞歸函數。由分治法產生的子問題往往是原問題的較小模式，這就為使用遞歸技術提供了方便。在這種情況下，反復應用分治手段，可以使子問題與原問題類型一致而其規模卻不斷縮小，最終

5、使子問 題縮小到很容易直接求出其解。這自然導致遞歸過程的產生。分治與遞歸像一對攣生兄弟，經常同時應用在算法設計之中，并由此產生許多高效算法。遞歸算法舉例：Fibonacci 數歹U無窮數列1, 1, 2, 3, 5, 8, 13, 21, 34, 55,，稱為Fibonacci數列。它可以遞歸地定義為：1n = 0F(n) = 1n = 1F(n -1) F(n -2) n 1第n個Fibonacci數可遞歸地計算如下:int fibonacci (int n)(if (n = 1) return 1;return fibonacci (n-1)+ fibonacci (n-2);從上看出:遞

6、歸算法的有點為：結構清晰，可讀性強，而且容易用數學歸納法來證明算法的正確性，因此它為設計算法、 調試程序帶來很大方便。缺點為：遞歸算法的運行效率較低，無論是耗費的計算時間還是占用的存儲空間都比非遞 歸算法要多。分治算法：一個分治法將規模為n的問題分成k個規模為n/m勺子問題去解。設分解閥值 n0=1 ,且adhoc解 規模為1的問題耗費1個單位時間。再設將原問題分解為k個子問題以及用merge將k個子問題的解合 并為原問題的解需用f(n)個單位時間。用T(n)表示該分治法解規模為|P|=n的問題所需的計算時 間，則有：O(1)T(n)= kT(n/m) f (n)通過迭代法求得方程的解: 算法

7、舉例：logmn-110g 一 kjjT(n) = n m kj f(n/mj)二分搜索技術：給定已按升序排好序的n個元素a0:n-1j0 ,現要在這n個元素中找出一特定元素X。據此容易設計出 二。搜索算法:template 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 = m+1;return -1;算法復雜度分析：每執行一次算法的while循環，待搜索數組的大小減少一半。因此，在

8、最壞情況下， while循環被執行了 O(logn)次。循環體內運算需要 0(1)時間，因此整個算法在最壞情況下 的計算時間復雜性為O(logn)。快速排序法：在快速排序中，記錄的比較和交換是從兩端向中間進行的，關鍵字較大的記錄一次就 能交換到后面單元，關鍵字較小的記錄一次就能交換到前面單元，記錄每次移動的距離較大,因而總的比較和移動次數較少。void Quicksort (Type a, int p, int r) (if (Pr) int q=Partition(a,p,r);QuickSort (a,p,q-1); /對左半段排序QuickSort (a,q+1,r); /對右半段排序

9、復雜性分析： 最壞時間復雜度：O(n2)平均時間復雜度：O(nlogn) 輔助空間：O(n)或O(logn)2.2 動態規劃動態規劃算法與分治法類似，其基本思想也是將待求解問題分解成若干個子問題但是經分解 得到的子問題往往不是互相獨立的。不同子問題的數目常常只有多項式量級。在用分治法求解時， 有些子問題被重復計算了許多次。如果能夠保存已解決的子問題的答案，而在需要時再找出已求得 的答案，就可以避免大量重復計算，從而得到多項式時間算法。方法步驟：1 )找出最優解的性質，并刻劃其結構特征。2)遞歸地定義最優值。3)以自底向上的方式計算出最優值。4)根據計算最優值時得到的信息，構造最優解。舉例：矩陣

10、連成問題基本要素：1)最優子結構2)重疊子問題3)備忘錄方法將矩陣連乘積簡記為Ai:j,這里i wj考察計算Ai:j的最優計算次序。設這個計算次序在矩陣Ak和Ak+1之間將矩陣鏈斷開，i wkj ,則其相應完全加括號方式為：(AA書.人)(入引八七.3)計算量：Ai:k的計算量加上 Ak+1:j的計算量，再加上Ai:k和Ak+1:j相乘的計算量。算法如下：void MatrixChain(int *p , int n , int *m , int *s) (for (int i = 1; i = n; i+) mii = 0;for (int r = 2; r = n; r+)for (int

11、 i = 1; i = n - r+1; i+) int j=i+r-1;mij = mi+1j+ pi-1*pi*pj;sij = i;for (int k = i+1; k j; k+) int t = mik + mk+1j + pi-1*pk*pj;if (t mij) mij = t; sij = k;算法復雜度分析：算法matrixChain的主要計算量取決于算法中對r, i和k的3重循環。循環體內的計算量為O(1),而3重循環的總次數為O(n3)。因此算法的計算時間上界為O(n3)。算法所占用的空間顯然為 O(n2)。2.3 貪心算法顧名思義，貪心算法總是作出在當前看來最好的選擇

12、。也就是說貪心算法并不從整體最優考慮，它所作出的選擇只是在某種意義上的局部最優選擇。當然，希望貪心算法得到的最終結果也是 整體最優的。雖然貪心算法不能對所有問題都得到整體最優解，但對許多問題它能產生整體最優解。 如單源最短路經問題，最小生成樹問題等。在一些情況下，即使貪心算法不能得到整體最優解，其 最終結果卻是最優解的很好近似。可用貪心算法解決的問題的性質：1)貪心選擇性質2)最優子結構性質舉例：最優裝載問題有一批集裝箱要裝上一艘載重量為c的輪船。其中集裝箱i的重量為Wio最優裝載問題要求確定在裝載體積不受限制的情況下，將盡可能多的集裝箱裝上輪船。 算法描述最優裝載問題可用貪心算法求解。采用重

13、量最輕者先裝的貪心選擇策略，可產生最優裝 載問題的最優解。具體算法描述如下。templatevoid Loading (int x, Type w口，Type c, int n)int *t = new int n+1;Sort(w, t, n);for (int i = 1; i = n; i+) xi = 0;for (int i = 1; i = n & wti half)|(t*(t-1)/2-counthalf) return;if (tn) sum+;elsefor (int i=0;i2;i+) p1t=i;count+=i;for (int j=2;j=t;j+) pjt-j+

14、1=pj-1t-j+1Apj-1t-j+2;count+=pjt-j+1;)Backtrack(t+1);for (int j=2；j=t；j+)count-=pjt-j+1;count-=i;復雜度分析計算可行性約束需要 O(n)時間，在最壞情況下有O(2n)個結點需要計算可行性約束，故解符號三角形問題的回溯算法所需的計算時間為O(n2n)。2.5分支限界法分支限界法常以廣度優先或以最小耗費(最大效益)優先的方式搜索問題的解空間樹。在分支限界法中，每一個活結點只有一次機會成為擴展結點。活結點一旦成為擴展結點，就一 次性產生其所有兒子結點。在這些兒子結點中，導致不可行解或導致非最優解的兒子結點

15、被舍棄， 其余兒子結點被加入活結點表中。此后，從活結點表中取下一結點成為當前擴展結點，并重復上述結點擴展過程。這個過程一 直持續到找到所需的解或活結點表為空時為止。常見的兩種分支限界法：(1)隊列式(FIFO)分支限界法按照隊列先進先出(FIFO)原則選取下一個節點為擴展節點。(2)優先隊列式分支限界法按照優先隊列中規定的優先級選取優先級最高的節點成為當前擴展節點。舉例:0-1背包問題算法思想：首先，要對輸入數據進行預處理，將各物品依其單位重量價值從大到小進行排列。在下面描述的優先隊列分支限界法中，節點的優先級由已裝袋的物品價值加上剩下的最大單位重量價值的物品裝滿剩余容量的價值和。算法首先檢查

16、當前擴展結點的左兒子結點的可行性。如果該左兒子結點是可行結點，則將 它加入到子集樹和活結點優先隊列中。當前擴展結點的右兒子結點一定是可行結點，僅當右兒子 結點滿足上界約束時才將它加入子集樹和活結點優先隊列。當擴展到葉節點時為問題的最優值。 部分算法如下：while (i != n+1) /非葉結點/檢查當前擴展結點的左兒子結點Typew wt = cw + wi;if (wt bestp) bestp = cp+pi;AddLiveNode(up, cp+pi, cw+wi, true, i+1);up = Bound(i+1);/檢查當前擴展結點的右兒子結點if (up = bestp) /

17、右子樹可能含最優解AddLiveNode(up, cp, cw, false, i+1);/取下一個擴展節點(略)3結合0-1背包問題詳述動態規劃、貪心算法、回溯法、分支限界法解決問題的過程0-1背包問題： 給定n#物品和一背包。物品i的重量是wi,其價值為vi ,背包的容量為Co問應如 何選擇裝入背包的物品，使得裝入背包中物品的總價值最大？動態規劃算法：n設所給0-1背包問題的子問題max z vk xkk =i, n WkXk & jk =iXk 0,1, i k 三 n的最優值為m(i , j),即m(i , j)是背包容量為j ,可選擇物品為i , i+1 ,，n 時0-1背包問題的最

18、優值。由0-1背包問題的最優子結構性質，可以建立計算m(i, j)的遞歸式如下。m(i, j)=max m(im(i 1, j)0 - jwim(n, j);算法復雜度分析：vr0j - Wn0 M jWn1, j),m(i 1, j - Wi) Vij - Wic很大時，算法需要從m(i, j)的遞歸式容易看出，算法需要 O(nc)計算時間。當背包容量 的計算時間較多。例如，當c2n時，算法需要Q(n2n)計算時間。改進算法：由m(i,j)的遞歸式容易證明，在一般情況下，對每一個確定的i(1 &i &n),函數m(i,j) 是關于變量j的階梯狀單調不減函數。跳躍點是這一類函數的描述特征。在一

19、般情況下， 函數m(i,j)由其全部跳躍點唯一確定。對每一個確定的i(1 & i & n),用一個表pi存儲函數m(i , j)的全部跳躍點。表pi可依計算m(i , j)的遞歸式遞歸地由表pi+1計算，初始時 pn+1=(0 , 0)。函數m(i,j)是由函數m(i+1,j)與函數m(i+1,j-wi)+vi作maxi算得到的。因此，函數m(i,j)的全部跳躍點包含于函數m(i+1 , j)的跳躍點集pi+1與函數m(i+1 ,j-wi)+vi 的跳躍點集qi+1的并集中。易知，(s,t) eqi+1當且僅當wiMsc且 (s-wi,t-vi) Wpi+1。因此，容易由pi+1 向定跳躍點集

20、qi+1 如下qi+1=pi+1二(wi,vi尸(j+wi,m(i,j)+vi)|(j,m(i,j)pi+1另一方面,設(a, b)和(c, d)是pi+1 =qi+1中的2個跳躍點，則當 6 a且db 時，(c , d)受控于(a, b),從而(c , d)不是pi中的跳躍點。除受控跳躍點外， pi+1 =qi+1中的其它跳躍點均為pi中的跳躍點。由此可見，在遞歸地由表pi+1計算表pi時，可先由pi+1計算出qi+1,然 后合并表pi+1和表qi+1,并清除其中的受控跳躍點得到表pi。改進后復雜性分析：上述算法的主要計算量在于計算跳躍點集pi(1 i n) 0由于qi+1=pi+1畬(wi

21、 ,vi),故計算 qi+1需要 O(|pi+1|) 計算時間。合并 pi+1和qi+1 并消除受控跳躍點也需要O(|pi+1|)計算時間。從跳躍點集pi的定義可以看出，pi中的跳躍點相應于xi,xn的0/1賦值。因此，pi中跳躍點個數不超過2n-i+1。由此可 見，算法計算跳躍點集pi所花費的計算時間為 從而，改進后算法的計算時間復雜性為 O(2n)。當所給物品的重量wi(1 &i&n)是整數時， |pi|c+1,(1 i n)0在這種情況下，改進后算法的計算時間復雜性為 O(minnc,2n)。貪心算法：在選擇裝入背包的物品時，對每種物品i只有2種選擇，即裝入背包或不裝入背包。不 能將物品i裝入背包多次，也不能只裝入部分的物品i。貪心算法的兩條性質，可以放入物 品的部分，使它適合背包問題。不適合 0-1背包問題，所以不能用貪心算法計算。 回溯法： 回溯法的三個條件： 解空間：子集樹n可行性約束函數：、wi xi - C1i =1上界函數：templateTypep Knap二 BoundQnt i)/計算上界Typew cleft = c - cw; /乘 U 余容量Typep b =