第8章-縮小規(guī)模策略

1、1 1第第八八章章 縮小規(guī)模策略縮小規(guī)模策略小規(guī)模問題的解經過某種組合可以較容易地得到原問題的解。解決這類問題的求解方法有：分治與遞歸、動態(tài)規(guī)劃和貪心算法，這章將介紹分治與遞歸。p分治與遞歸策略p遞歸的典型應用p分治策略的應用2 2縮小規(guī)模策略將一個難以直接解決的大問題，分解成多個規(guī)模較小的子問題，以便各個擊破、分而治之。分治法：如果原問題可以分割為k個子問題，1kn，且這k個子問題都可解，并可利用子問題的解計算出原問題的解，則可以采用分治法。遞歸：分治法產生的子問題往往是原問題的較小模式，常使用遞歸技術。3 3一個直接或間接調用自身的算法稱為遞歸算法。遞歸策略u 定義u 特點n需少量的程序就

2、可描述出解題過程所需要的多次重復計算，大大地減少了程序的代碼量。n用有限的語句來定義對象的無限集合。u 使用條件n 原問題可以通過轉化為較小的子問題來解決，而子問題的求解方法與原問題相同，被處理的數(shù)據(jù)有規(guī)律地減少。n 當子問題減小至一定程度時，調用自身算法的過程終止。遞歸需要有邊界條件、遞歸推進部分和遞歸返回4 4遞歸策略u 整數(shù)劃分問題將一個正整數(shù)n表示為一系列正整數(shù)之和： n=n1+n2+nk,其中，n1n2nk1，k1。該表示稱為n的一個劃分；不同劃分的個數(shù)稱為劃分數(shù)，記為p(n)?！纠?】整數(shù)6的11種劃分。6；5+1；4+2，4+1+1；3+3，3+2+1，3+1+1+1;2+2+2

3、, 2+2+1+1, 2+1+1+1+1;1+1+1+1+1+1;5 5遞歸策略n分析在正整數(shù)n的所有不同劃分中，將最大加數(shù)n1不大于m的劃分個數(shù)記為q(n，m)，則可以建立如下的遞歸關系：(1) q(n，1) = 1，n1當最大加數(shù)n1不大于1時，只有一種劃分形式：n=1+1+1(2) q(n，m) = q(n，n)，mn最大加數(shù)n1不能大于n，因此q(1，m) = 1(3) q( n, n ) = 1 + q ( n, n-1)正整數(shù)n的劃分，由n1=n的劃分和n1n-1的劃分組成(4) q(n, m ) = q(n, m-1) + q (n-m, m), nm1正整數(shù)n的最大加數(shù)n1不大

4、于m的劃分，由n1=m的劃分和n1m-1的劃分組成6 6遞歸策略1mn m)m,q(n) 1mq(n,mn ) 1nq(n,1mn n)q(n,1m1,n 1m)q(n, n計算q(n, m)的遞歸計算式7 7分治策略u基本思想將一個規(guī)模為n的問題分解為k個規(guī)模較小的子問題，這些子問題相互獨立且與原問題相同。遞歸求解這些子問題，并將子問題的解合并，則得到原問題解。u分治法求解問題的特征n(1) 問題的規(guī)?？s小到一定的程度就可容易解決n(2) 問題可分解為若干個規(guī)模較小的相同問題n(3) 利用原問題分解出的子問題的解可合并為原問題的解n(4) 問題所分解出的各個子問題是相互獨立的，即子問題之間不

5、包含公共的子問題8 8分治策略u分治法的一般步驟n分解 將要解決的問題劃分成若干規(guī)模較小的同類問題n求解 當子問題劃分得足夠小時，用較簡單的方法解決n合并 按原問題要求，將子問題的解逐層合并構成原問題解DataType Divide-and-Conquer (P) if ( |P| = n0 ) Adhoc( P ); divide P into smaller subinstances; P1, P2, , Pk; for ( i=1; i0) hanoi(n - 1, from, to, tmp); /將將from桿上的桿上的n-1塊金片移至塊金片移至tmp桿桿 printf(take %

6、d塊金片 from %c to %cn,n ,from,to); /將將from上的一塊金片移至上的一塊金片移至yo桿桿 hanoi(n - 1, tmp, from, to); /將將tmp桿上的桿上的n-1塊金片移至塊金片移至to桿上桿上 /Hanoi1313遞歸算法的典型應用u全排列問題n問題描述R=r1，r2，rn是要進行排列的n個元素，Ri=Rri。集合X中元素的全排列記為Perm(X)；(ri)Perm(X)表示在全排列Perm(X)的每一個排列前加上前綴ri得到的排列。R的全排列可遞歸定義為：(1) 當n=1時，Perm(R)=(r1)，r1是集合R中的唯一元素。(2) 當n1時

7、，Perm(R)由(r1)Perm(R1)，(r2)Perm(R2)，(rn)Perm(Rn)構成。1414遞歸算法的典型應用【例2】集合1,2,3的全排列。1515遞歸算法的典型應用n遞歸算法void Swap(int &a, int &b) int t = a; a = b; b = t; /Swapvoid Perm(int R, int k, int m ) /產生集合產生集合Rk:m的全的全排列排列 if (k=m) /Rk:m具有一個排列，將其輸出具有一個排列，將其輸出 for (int i=0; i=k; i+) printf(%d ,Ri); printf(n)

8、; else /R k:m具有多個排列并遞歸生成具有多個排列并遞歸生成 for (int i = k; ihigh時，查找失敗 將k與mid指向的記錄比較若k=rmid.key，則若krmid.key，則1818分治策略的應用n查找過程找211 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92highlowmid1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92lowhighmid查找成功1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 7

9、5 80 88 92lowhighmid211919分治策略的應用找661 2 3 4 5 6 7 8 9 10 5 10 19 21 31 37 42 48 50 55 highlowmid1 2 3 4 5 6 7 8 9 10 5 10 19 21 31 37 42 48 50 55 lowhighmidhighlow mid55high lowlowmid1 2 3 4 5 6 7 8 9 10 5 10 19 21 31 37 42 48 50 55 high查找失敗2020分治策略的應用n算法int BinerSerch(int R ,int x) int low,mid,high

10、; low=0; high=n-1; while(low=high) mid=(low+high)/2 ; if(x=Rmid) return mid; if(xRmid ) high=mid-1; else low=mid+1; return -1; 2121分治策略的應用n性能分析第i次比較 剩余 n/2i 若最后只剩一個，則n/2i=1，即i=log2n即比較次數(shù)O(log2n)時間復雜度 O(log2n)n 特點 表中元素需有序排列，且順序存儲。但對需頻繁插入或刪除操作的數(shù)據(jù)集來說，維護有序會有較大的工作量。2222分治策略的應用n查找判定樹 描述查找過程的二叉樹。樹中結點的數(shù)字表示該

11、結點在有序表中的位置（1n）。6391741025811【例3】 具有11個結點的折半查找判定樹。結論：在查找成功時進行的比較次數(shù)最多不超過樹的深度。 2323分治策略的應用【例4】建立具有13個結點的判定樹，并其成功查找的ASL。73101851224139611ASL=1/13 (1+22+34+46)=41/133.152424分治策略的應用u歸并排序n基本思想n兩路歸并 設初始序列含n個記錄，可看成n個有序子序列，各序列長度為1；再兩兩合并，如此重復，直至得到長度為n的有序序列。 兩兩合并，得到 n/2 個長度為2或1的有序子序列;將元素集合分割成n個（ 2）子集，對每個子集分別排序，

12、再將排好序的子集歸并為一個集合。若n為1，排序終止。2525分治策略的應用【例5】兩路歸并過程示例。2626分治策略的應用n算法兩個有序文件的合并void Merge(rectype R,rectype T,int low,int mid,int high) / RlowRlowmidmid與與Rmid+1Rmid+1highhigh是兩個有序文件是兩個有序文件 / 結果文件結果文件TlowTlowhighhigh int i, j, k; i=low; j=mid+1; k=low; while (i=mid) & (j=high) if (Ri.key=Rj.key) Tk+=Ri

13、+; else Tk+=Rj+; while (i=mid) Tk+=Ri+; while (j=high) Tk+=Rj+;2727分治策略的應用n算法一趟歸并void MergePass(rectype R , rectype T , int len) / 對對R R中中 n/n/lenlen 個有序子文件做一趟歸并，結果放個有序子文件做一趟歸并，結果放在在T T中中 int i, j; i=0 ; / i i向第一對子文件的起始點向第一對子文件的起始點 while (i+2 len 1n) /兩個長度為兩個長度為lenlen的有序子文件的有序子文件 Merge(R, T, i, i+le

14、n-1, i+2 len-1); i=i+2len; / i i指向下一對子文件的起始點指向下一對子文件的起始點 if (i+len-1)n-1) / 子文件個數(shù)子文件個數(shù)偶數(shù)偶數(shù), ,一一個長度小于個長度小于lenlen Merge(R, T, i, i+len-1, n-1); else / 子文件個數(shù)為奇數(shù)子文件個數(shù)為奇數(shù) for (j=i; jn; j+) Tj=Rj; 2828分治策略的應用n算法兩路歸并void MergeSort(rectype R ) / 對對R R進行二路歸并排序進行二路歸并排序 int len; len=1; while (len=temp.key) &am

15、p; (ij) j; if (ij) Ri+=Rj; / “交換交換”R”Ri i 和和Rj Rj while (Ri.key=temp.key) & (ij) i+; if (ij) Rj=Ri; / “交換交換”R”Ri i 和和Rj Rj while (i!=j); Ri=temp; / 基準基準temptemp已被最后定位已被最后定位 return i;3434分治策略的應用void QuickSort(rectype R , int s1, int t1) / 對對Rs1Rs1到到Rt1Rt1做快速排序做快速排序 int i; if (s1t1) / 只有一個記錄或無記錄時無須排序只有一個記錄或無記錄時無須排序 i=PARTITION(R, s1, t1); / 對對Rs1Rs1到到Rt1Rt1做劃分做劃分 QuickSort(R, s1, i 1); / 遞歸處理左區(qū)間遞歸處理左區(qū)間 QuickSort(R, i+1, t1); / 遞歸處理右區(qū)間遞歸處理右區(qū)間 3535分治策略的應用n算法評價