算法分析總復(fù)習(xí)

1、總復(fù)習(xí),,第一章 緒 論,算法的概念。程序與算法的區(qū)別和聯(lián)系。算法的計(jì)算復(fù)雜性,算法和程序,算法是指解決問題的一種方法或一個過程。算法是若干指令的有窮序列，滿足性質(zhì)：(1)輸入 (2)輸出 (3)確定性 (4)有限性程序是算法用某種程序設(shè)計(jì)語言的具體實(shí)現(xiàn)。程序可以不滿足算法的性質(zhì)(4)。,算法復(fù)雜性分析,算法復(fù)雜性 = 算法所需要的計(jì)算機(jī)資源算法的時(shí)間復(fù)雜性T(n)；算法的空間復(fù)雜性S(n)。其中n是問題的規(guī)模（

2、輸入大小）。,漸近分析的記號,（1）漸近上界記號OO(g(n)) = { f(n) | 存在正常數(shù)c和n0使得對所有n? n0有：0 ? f(n) ? cg(n) }（2）漸近下界記號? ? (g(n)) = { f(n) | 存在正常數(shù)c和n0使得對所有n? n0有：0? cg(n) ? f(n) },遞歸的概念與分治策略。二分搜索技術(shù)； 大整數(shù)乘法；Strassen矩陣乘法；棋盤覆蓋；合并排序和快速排序；循環(huán)賽日程

3、；,第二章 遞歸與分治,分治策略算法思想,將要求解的較大規(guī)模的問題分割成k個更小規(guī)模的子問題。對這k個子問題分別求解。如果子問題的規(guī)模仍然不夠小，則再劃分為k個子問題，如此遞歸的進(jìn)行下去，直到問題規(guī)模足夠小，很容易求出其解為止。對這k個子問題分別求解。將求出的小規(guī)模的問題的解合并為一個更大規(guī)模的問題的解，自底向上逐步求出原來問題的解。,遞歸的概念,直接或間接地調(diào)用自身的算法稱為遞歸算法。用函數(shù)自身給出定義的函數(shù)稱為遞歸函數(shù)。由

4、分治法產(chǎn)生的子問題往往是原問題的較小模式，這些子問題與原問題類型一致而其規(guī)模卻不斷縮小，反復(fù)使用分治法后最終使子問題縮小到很容易直接求出其解。這自然導(dǎo)致遞歸過程的產(chǎn)生。,階乘函數(shù),Fibonacci數(shù)列,Ackerman函數(shù),在問題規(guī)模較大時(shí)，較難找到一般的方法，因此我們嘗試用遞歸技術(shù)來解決這個問題。,當(dāng)n=1時(shí)，問題比較簡單。此時(shí)，只要將編號為1的圓盤從塔座a直接移至塔座b上即可。當(dāng)n＞1時(shí)，需要利用塔座c作為輔助塔座。此時(shí)若能設(shè)法

5、將n-1個較小的圓盤依照移動規(guī)則從塔座a移至塔座c，然后，將剩下的最大圓盤從塔座a移至塔座b，最后，再設(shè)法將n-1個較小的圓盤依照移動規(guī)則從塔座c移至塔座b。由此可見，n個圓盤的移動問題可分為2次n-1個圓盤的移動問題，這又可以遞歸地用上述方法來做。由此可以設(shè)計(jì)出解Hanoi塔問題的遞歸算法如下。,Hanoi塔問題,,void hanoi(int n, int a, int b, int c) { if (n &g

6、t; 0) { hanoi(n-1, a, c, b); move(a,b); hanoi(n-1, c, b, a); } },分治法解決問題,分治法所能解決的問題一般具有以下幾個特征：該問題的規(guī)模縮小到一定的程度就可以容易地解決；該問題可以分解為若干個規(guī)模較小的相同問題，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)利用該問題分解出的子問題的解可以合并

7、為該問題的解；該問題所分解出的各個子問題是相互獨(dú)立的，即子問題之間不包含公共的子問題。,分治法的復(fù)雜性分析,一個分治法將規(guī)模為n的問題分成k個規(guī)模為n／m的子問題去解。設(shè)解規(guī)模為1的問題耗費(fèi)1個單位時(shí)間。再設(shè)將原問題分解為k個子問題以及將k個子問題的解合并為原問題的解需用f(n)個單位時(shí)間。用T(n)表示該分治法解規(guī)模為|P|=n的問題所需的計(jì)算時(shí)間，則有：,,通過迭代法求得方程的解：,二分搜索技術(shù),給定已按升序排好序的n個元素a[0

8、:n-1]，現(xiàn)要在這n個元素中找出一特定元素x。,分析：很顯然此問題分解出的子問題相互獨(dú)立，，子問題縮小到一定規(guī)模容易解，子問題的解就是原問題的解，子問題與原問題為相同問題，滿足分治法的四個適用條件。,int BinarySearch(Type a[], Type& x,int low,int high){ while (high >= low){ int mid = (low+high)/2;

9、 if (x == a[mid]) return mid; if (x < a[mid]) high = mid-1; else low = mid+1; } return -1;},時(shí)間復(fù)雜性為O(logn),大整數(shù)的乘法,設(shè)計(jì)一個有效的算法進(jìn)行兩個n位大整數(shù)的乘法運(yùn)算,分治法：X = a 2n/2 + b Y = c 2n/2 + d XY = ac 2n +

10、 (ad+bc) 2n/2 + bd復(fù)雜度沒有降低。為了降低時(shí)間復(fù)雜度，必須減少乘法的次數(shù)。XY = ac 2n + ((a-c)(b-d)+ac+bd) 2n/2 + bdXY = ac 2n + ((a+c)(b+d)-ac-bd) 2n/2 + bd,復(fù)雜度分析T(n)=O(nlog3) =O(n1.59)?較大的改進(jìn),Strassen矩陣乘法,將矩陣A，B和C中每一矩陣都分塊成4個大小相等的子矩陣。為了降低時(shí)間復(fù)雜

11、度，必須減少乘法的次數(shù)。,,,,,,,,,復(fù)雜度分析T(n)=O(nlog7) =O(n2.81)?較大的改進(jìn),棋盤覆蓋,覆蓋2k×2k 個方格組成的棋盤中除特殊方格以外的所有方格，且任何2個L型骨牌不得重疊覆蓋。,當(dāng)k>0時(shí)，將2k×2k棋盤分割為4個2k-1×2k-1 子棋盤。特殊方格必位于4個較小子棋盤之一中，其余3個子棋盤中無特殊方格。為了將這3個無特殊方格的子棋盤轉(zhuǎn)化為特殊棋盤，可以

12、用一個L型骨牌覆蓋這3個較小棋盤的會合處，從而將原問題轉(zhuǎn)化為4個較小規(guī)模的棋盤覆蓋問題。遞歸地使用這種分割，直至棋盤簡化為棋盤1×1。,棋盤覆蓋,,void chessBoard(int tr, int tc, int dr, int dc, int size) { if (size == 1) return; int t = tile++, // L型骨牌號 s = size/

13、2; // 子棋盤大小 // 覆蓋左上角子棋盤 if (dr < tr + s && dc < tc + s) // 特殊方格在此棋盤中 chessBoard(tr, tc, dr, dc, s); else { // 此棋盤中無特殊方格 board[tr + s - 1][tc + s - 1] = t; // 用 t 號骨牌覆

14、蓋右下角 chessBoard(tr, tc, tr+s-1, tc+s-1, s);} // 覆蓋其余方格 // 覆蓋右上角子棋盤 // 覆蓋左下角子棋盤 // 覆蓋右下角子棋盤 },復(fù)雜度分析T(n)=O(4k) 漸進(jìn)意義下的最優(yōu)算法,合并排序,基本思想：將待排序元素分成大小大致相同的2個子集合，分別對2個子集合進(jìn)行排序，最終將排好序的子集合合并成為所要求的排好

15、序的集合。,void MergeSort(Type a[], int left, int right) { if (left<right) {//至少有2個元素 int i=(left+right)/2; //取中點(diǎn) mergeSort(a, left, i); mergeSort(a, i+1, right); merge(a, b, left, i, righ

16、t); //合并到數(shù)組b copy(a, b, left, right); //復(fù)制回?cái)?shù)組a } },復(fù)雜度分析T(n)=O(nlogn) 漸進(jìn)意義下的最優(yōu)算法,快速排序,void QuickSort (Type a[], int p, int r){ if (p<r) { int q=Partition(a,p,r); QuickSort

17、 (a,p,q-1); //對左半段排序 QuickSort (a,q+1,r); //對右半段排序 }},最壞時(shí)間復(fù)雜度：O(n2)平均時(shí)間復(fù)雜度：O(nlogn)輔助空間：O(n)或O(logn),在快速排序中，記錄的比較和交換是從兩端向中間進(jìn)行的，關(guān)鍵字較大的記錄一次就能交換到后面單元，關(guān)鍵字較小的記錄一次就能交換到前面單元，記錄每次移動的距離較大，因而總的比較和移動次數(shù)較少。,循環(huán)賽日程安排

18、,按分治策略，將所有的選手分為兩半，n個選手的比賽日程表就可以通過為n/2個選手設(shè)計(jì)的比賽日程表來決定。遞歸地用對選手進(jìn)行分割，直到只剩下2個選手時(shí)，比賽日程表的制定就變得很簡單。這時(shí)只要讓這2個選手進(jìn)行比賽就可以了。Void Table(int a[][],int begin,int end){int n=end-begin;//待安排比賽的隊(duì)數(shù)if(n<=2) 安排兩隊(duì)比賽;else{Table(a

19、，begin，begin＋n/2); Table(a,begin+n/2＋1，end); Merge(a);} },動態(tài)規(guī)劃算法的概念及基本要素。矩陣連乘問題；最長公共子序列；流水作業(yè)調(diào)度；背包問題。,21,第三章 動態(tài)規(guī)劃,22,基本思想將待求解問題分解成若干個子問題。若子問題重復(fù)，保存已解決的子問題的答案，而在需要時(shí)再找出已求得的答案，就可以避免大量重復(fù)計(jì)算，

20、從而得到多項(xiàng)式時(shí)間算法。,算法思想,動態(tài)規(guī)劃算法的基本要素（1）最優(yōu)子結(jié)構(gòu)性質(zhì)（2）重疊子問題性質(zhì),動態(tài)規(guī)劃基本步驟,分析最優(yōu)值的性質(zhì)，得到最優(yōu)值的遞歸定義；自底向上地計(jì)算子問題的最優(yōu)值，逐步得到原問題的最優(yōu)值，并記錄計(jì)算過程；由最優(yōu)值的計(jì)算過程出構(gòu)造原問題的最優(yōu)解；,矩陣連乘問題,為方便描述，將Ai×Ai+1……×Aj記作Ai,j；設(shè)最優(yōu)解的最后一步乘法是A1,k×Ak+1,n，則顯然，A

21、1,k和Ak+1,n應(yīng)分別是該子式的最優(yōu)解——最優(yōu)子結(jié)構(gòu)；總計(jì)算量是這兩個子式的計(jì)算量加上子式結(jié)果相乘的計(jì)算量；,解決問題,建立遞歸關(guān)系設(shè)計(jì)算A[i:j]，1≤i≤j≤n，所需要的最少數(shù)乘次數(shù)m[i,j]，則原問題的最優(yōu)值為m[1,n] 當(dāng)i=j時(shí)，A[i:j]=Ai，因此m[i,i]=0,i=1,2,…,n當(dāng)i<j時(shí)其中k為最佳順序中兩個子序列的中間斷開點(diǎn),這里 的維數(shù)為,m[i,j]為：,解決

22、問題,計(jì)算最優(yōu)值由遞歸式分析，計(jì)算最少的乘積次數(shù)。為了避免重復(fù)的計(jì)算，從m[i,i]出發(fā)，依次計(jì)算m[i,i+1] 、 m[i,i+2] 、... m[i,j] ，同時(shí)記錄s[i,j] ；過程如下：,解決問題,,解決問題,設(shè)P[0…n]向量為各矩陣的維數(shù)，P[i]為Ai的列數(shù)，P[0]為A1的行數(shù)；初始化m[i][i] = 0；i = 1…nr循環(huán)從2到n，計(jì)算m[i][i+r]：i(行下標(biāo))循環(huán)從1到n-r+1：j(

23、列下標(biāo)) = i+r-1； m[i][j]=min{ m[i][k]+m[k+1][j]+P[i-1]P[k]P[j] | k=i..j-1 } 并紀(jì)錄：s[i][j] = k;,void MatrixChain(int *p,int n,int** m,int** s){for(int i=1;i<=n;i++) m[i][i]=0;for(int r=2;r<=n;r++)//計(jì)算矩陣序列長度為r

24、時(shí)所需乘法次數(shù) for(int i=1;i<=n-r+1;i++)//從i開始長r的序列所需乘法次數(shù) {int j=i+r-1;m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];s[i][j]=i;//以i號矩陣為分隔點(diǎn)for(int k=i+1;k<j;k++)//k陣為分隔點(diǎn)時(shí)乘法次數(shù){int t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];

25、if(t<m[i][j]){m[i][j]=t;s[i][j]=k;//以k號矩陣為分隔點(diǎn) }} }},算法復(fù)雜度分析：算法matrixChain的主要計(jì)算量取決于算法中對r，i和k的3重循環(huán)。循環(huán)體內(nèi)的計(jì)算量為O(1)，而3重循環(huán)的總次數(shù)為O(n3)。因此算法的計(jì)算時(shí)間上界為O(n3)。算法所占用的空間顯然為O(n2)。,最長公共子序列,若給定序列X={x1,x2

26、,…,xm}，則序列Z={z1,z2,…,zk}是X的子序列是指存在一個嚴(yán)格遞增下標(biāo)序列{i1,i2,…,ik}使得對于所有j=1,2,…,k有：zj=xij。,最優(yōu)子結(jié)構(gòu)性質(zhì)：2個序列的最長公共子序列包含了這2個序列的前綴的最長公共子序列。,最長公共子序列的結(jié)構(gòu),設(shè)序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最長公共子序列為Z={z1,z2,…,zk} ，則(1)若xm=yn，則zk=xm=yn，且zk-1是xm

27、-1和yn-1的最長公共子序列。(2)若xm≠yn且zk≠xm，則Z是xm-1和Y的最長公共子序列。(3)若xm≠yn且zk≠yn，則Z是X和yn-1的最長公共子序列。,子問題的遞歸結(jié)構(gòu),由最長公共子序列問題的最優(yōu)子結(jié)構(gòu)性質(zhì)建立子問題最優(yōu)值的遞歸關(guān)系。用c[i][j]記錄兩序列的最長公共子序列的長度。其中， Xi={x1,x2,…,xi}；Yj={y1,y2,…,yj}。建立遞歸關(guān)系如下：,,計(jì)算最優(yōu)值,在所考慮的子問題空間中，總共

28、有? (mn)個不同的子問題，因此，用動態(tài)規(guī)劃算法自底向上地計(jì)算最優(yōu)值能提高算法的效率。,void LCSLength(int m,int n,char *x,char *y,int **c,int **b){ int i，j; for (i = 1; i =c[i][j-1]) { c[i][j]=c[i-1][j]; b[i][j]=2;} el

29、se { c[i][j]=c[i][j-1]; b[i][j]=3; }}},算法復(fù)雜度分析：算法LCSlength的主要計(jì)算量取決于算法中對i和j的2重循環(huán)。循環(huán)體內(nèi)的計(jì)算量為O(1)，而2重循環(huán)的總次數(shù)為O(n2)。因此算法的計(jì)算時(shí)間上界為O(n2)。算法所占用的空間顯然為O(n2)。,構(gòu)造最長公共子序列void LCS(int i，int j，char *x，int **b){ if (i ==0 || j==0

30、) return; if (b[i][j]== 1){ LCS(i-1，j-1，x，b); printf(“%c”,x[i]); } else if (b[i][j]== 2) LCS(i-1，j，x，b); else LCS(i，j-1，x，b);},流水作業(yè)調(diào)度,n個作業(yè){1，2，…，n}要在由2臺機(jī)器M1和M2組成的流水線上完成

31、加工。每個作業(yè)加工的順序都是先在M1上加工，然后在M2上加工。M1和M2加工作業(yè)i所需的時(shí)間分別為ai和bi。流水作業(yè)調(diào)度問題要求確定這n個作業(yè)的最優(yōu)加工順序，使得從第一個作業(yè)在機(jī)器M1上開始加工，到最后一個作業(yè)在機(jī)器M2上加工完成所需的時(shí)間最少。,分析：設(shè)全部作業(yè)的集合為N={1，2，…，n}。S?N是N的作業(yè)子集。在一般情況下，機(jī)器M1開始加工S中作業(yè)時(shí)，機(jī)器M2還在加工其它作業(yè)，要等時(shí)間t后才可利用。將這種情況下完成S中作業(yè)

32、所需的最短時(shí)間記為T(S,t)。流水作業(yè)調(diào)度問題的最優(yōu)值為T(N,0)。,對于流水作業(yè)調(diào)度問題，必存在最優(yōu)調(diào)度? ，使得作業(yè)?(i)和?(i+1)滿足Johnson不等式。進(jìn)一步還可以證明，調(diào)度滿足Johnson法則當(dāng)且僅當(dāng)對任意i<j有,流水作業(yè)調(diào)度的Johnson法則,如果作業(yè)i和j滿足min{bi,aj}≥min{bj,ai}，則稱作業(yè)i和j滿足Johnson不等式。,所有滿足Johnson法則的調(diào)度均為最優(yōu)調(diào)度。,算法描述

33、,流水作業(yè)調(diào)度問題的Johnson算法(1)令(2)將N1中作業(yè)依ai的非減序排序；將N2中作業(yè)依bi的非增序排序；(3)N1中作業(yè)接N2中作業(yè)構(gòu)成滿足Johnson法則的最優(yōu)調(diào)度。,,算法復(fù)雜度分析：算法的主要計(jì)算時(shí)間花在對作業(yè)集的排序。因此，在最壞情況下算法所需的計(jì)算時(shí)間為O(nlogn)。所需的空間為O(n)。,38,0-1背包問題,給定n種物品和一背包。物品i的重量是wi，其價(jià)值為vi，背包的容量為C。問應(yīng)如何選擇裝入背

34、包的物品，使得裝入背包中物品的總價(jià)值最大?,,,,,在考慮0-1背包問題時(shí)，應(yīng)比較選擇該物品和不選擇該物品所導(dǎo)致的最終方案，然后再作出最好選擇。由此就導(dǎo)出許多互相重疊的子問題,可用動態(tài)規(guī)劃算法求解。,39,0-1背包問題,0-1背包問題,40,設(shè)所給0-1背包問題的子問題,,,m(i，j)是背包容量為j，可選擇物品為i，i+1，…，n時(shí)0-1背包問題的最優(yōu)值。,,,0-1背包問題,41,由0-1背包問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，可以建立計(jì)算m(

35、i，j)的遞歸式如下。,0-1背包問題,42,Void Knapsack(Type v, int w, int c, int n, Type** m){ int jMax=min(w[n]-1, c); for (int j=0;j1;i--){ jMax=min(w[i]-1,c); for(int j=0;j<=jMax;j++) m[i][j]=m[i+1][j]; for(int

36、j=w[i];j<=c;j++) m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]); },43,m[1][c]=m[2][c];If(c>=w[1]) m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]);}Void TraceBack(Type** m,int w,int c,int n,int x){ for(int i=

37、1;i<n;i++) if(m[i][c]==m[i+1][c]) x[i]=0; else{ x[i]=1; c-=w[i];} x[n]=(m[n][c])?1:0;},算法復(fù)雜度分析：從m(i，j)的遞歸式容易看出，算法需要O(nc)計(jì)算時(shí)間。當(dāng)背包容量c很大時(shí)，算法需要的計(jì)算時(shí)間較多。例如，當(dāng)c>2n時(shí)，算法需要Ω(n2n)計(jì)算時(shí)間。,貪心算法的概念及基本要素 活動安排問題；最優(yōu)裝載問題

38、；哈夫曼編碼；,第 四 章 貪心算法,貪心算法基本思想和性質(zhì),貪心算法總是作出在當(dāng)前看來最好的選擇。也就是說貪心算法并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選擇。當(dāng)然，希望貪心算法得到的最終結(jié)果也是整體最優(yōu)的。（1）最優(yōu)子結(jié)構(gòu)性質(zhì)（2）貪心選擇性質(zhì),活動安排問題,設(shè)有n個活動的集合E={1,2,…,n}，其中每個活動都要求使用同一資源，而在同一時(shí)間內(nèi)只有一個活動能使用這一資源。每個活動i都有一個要求使用該

39、資源的起始時(shí)間si和一個結(jié)束時(shí)間fi,且si <fi 。如果選擇了活動i，則它在半開時(shí)間區(qū)間[si, fi)內(nèi)占用資源。若區(qū)間[si, fi)與區(qū)間[sj, fj)不相交，則稱活動i與活動j是相容的。也就是說，當(dāng)si≥fj或sj≥fi時(shí)，活動i與活動j相容。,活動安排問題,貪心解法：將所有活動按結(jié)束時(shí)間排序，得到活動集合E={e1,e2…en}；先將e1選入結(jié)果集合A中，即A={e1}；依次掃描每一個活動ei：如果ei的開

40、始時(shí)間晚于最后一個選入A的活動ej的結(jié)束時(shí)間，則將ei選入A中，否則放棄ei；,活動安排問題,void GreedySelector(int n, Type s[], Type f[], bool A[]){ A[1]=true; int j=1; for (int i=2;i=f[j]) { A[i]=true; j=i; } else A[i]=false;

41、 } },活動安排問題的貪心算法GreedySelector,最優(yōu)裝載,有一批集裝箱要裝上一艘載重量為c的輪船。其中集裝箱i的重量為Wi。最優(yōu)裝載問題要求確定在裝載體積不受限制的情況下，將盡可能多的集裝箱裝上輪船。最優(yōu)裝載問題可用貪心算法求解。采用重量最輕者先裝的貪心選擇策略，可產(chǎn)生最優(yōu)裝載問題的最優(yōu)解。,最優(yōu)裝載,void Loading(int x[], Type w[], Type c, int n){

42、 int *t = new int [n+1]; Sort(w, t, n); for (int i = 1; i <= n; i++) x[i] = 0; for (int i = 1; i <= n && w[t[i]] <= c; i++) {x[t[i]] = 1; c -= w[t[i]]

43、;}},哈夫曼編碼,構(gòu)造哈夫曼編碼哈夫曼提出構(gòu)造最優(yōu)前綴碼的貪心算法，由此產(chǎn)生的編碼方案稱為哈夫曼編碼。哈夫曼算法以自底向上的方式構(gòu)造表示最優(yōu)前綴碼的二叉樹T。,select(HuffmanTree* s, int n, int& s1, int& s2),{s[0] = new HTNode;s[0]->weight = (unsigned long)(-1L); s1 = s2 = 0

44、;for(int i = 1; i weight != 0 && s[i]->parent == NULL){if (s[i]->weight weight){ s2 = s1; s1 = i;}else if (s[i]->weight weight){ s2 = i; } }delete s[0];},建Huffman樹,int

45、s1, s2;for(int i = num + 1; i weight = s[s1]->weight + s[s2]->weight;p->parent = NULL; p->lchild = s[s1]; p->rchild = s[s2];s[s1]->parent = s[s2]->parent = p; s[i] = p;},從葉

46、子到根逆向求每個元素的編碼,for(int i = 1; i parent; f != NULL; c = f, f = f->parent) {if (f->rchild == c) code = ‘1’; else code = ‘0’;

47、 codes.push (code);//壓入 }printf(“重為%d的元素的編碼為：”,s[i]->weight);for(codes.top!=0) printf(“%c”,codes.pop()); printf(“\n”); },回溯法解題的算法框架n后問題；圖的m著色問題

48、旅行售貨員問題,55,第五章 回溯法,56,問題的所有的解構(gòu)造成樹的結(jié)構(gòu)，稱解空間樹?；厮莘ň褪菑母Y(jié)點(diǎn)出發(fā)按深度優(yōu)先策略搜索整個解空間樹，得到一個或者所有解。這種方法適用于解一些組合數(shù)相當(dāng)大的問題。當(dāng)算法搜索至解空間樹的任意一點(diǎn)時(shí)，先判斷該結(jié)點(diǎn)是否包含問題的解。如果不包含，則跳過對該結(jié)點(diǎn)為根的子樹的搜索，向其結(jié)點(diǎn)回溯；否則，進(jìn)入該子樹，繼續(xù)按深度優(yōu)先策略搜索。,回溯法的一般方法,57,回溯法的基本步驟,(1)針對所給問題，定義問

49、題的解空間；(2)確定易于搜索的解空間結(jié)構(gòu)；(3)以深度優(yōu)先方式搜索解空間，并在搜索過程中用剪枝函數(shù)避免無效搜索。,剪枝函數(shù)：用約束函數(shù)在擴(kuò)展結(jié)點(diǎn)處剪去不滿足約束的子樹。用限界函數(shù)剪去得不到最優(yōu)解的子樹。,問題：在一個n×n的棋盤上布置n個王后，使其相互不能攻擊（不能在同行、同列、同斜線）；問題的狀態(tài)即棋盤的布局狀態(tài)，解空間樹的根為空棋盤，每個布局的下一步可能布局為該布局結(jié)點(diǎn)的子結(jié)點(diǎn)；由于可以預(yù)知，在每行中有且只有

50、一個王后，因此為了簡化狀態(tài)空間樹，采用逐行布局的方式，即每個布局有n個子結(jié)點(diǎn)；,58,N皇后問題,回溯過程分析1、從空棋盤起，逐行放置棋子。2、在一個布局中放下一個棋子，即推演到另一個布局。3、如果某一行中沒有可合法放置棋子的位置，則回溯到上一行，重新布放上一行的棋子。,59,N皇后問題,boolean place (int k) { for (int j=1;jn) sum++; else

51、 for (int i=1;i<=n;i++) { x[t]=i; if (place(t)) backtrack(t+1); } },60,復(fù)雜度分析 N皇后問題的復(fù)雜度取決于回溯算法的調(diào)用次數(shù),隨著N值的增加,回溯算法的調(diào)用次數(shù)也增加,而且其增加的速度非常的快.當(dāng)把一個皇后放進(jìn)棋盤中的某一行中時(shí),回溯算法將被調(diào)用以試探是否會和已有的皇后沖突,對

52、于每一行來說最多將檢測N個位置,所以時(shí)間復(fù)雜度為NN.,N皇后問題,61,圖的m著色問題,給定無向連通圖G和m種不同的顏色。用這些顏色為圖G的各頂點(diǎn)著色，每個頂點(diǎn)著一種顏色。是否有一種著色法使G中每條邊的2個頂點(diǎn)著不同顏色?分析：把著色問題安排到一棵圖的頂點(diǎn)構(gòu)成的樹中，利用試探和回溯去求解。,算法描述：初始化（起始狀態(tài)）；從第一個頂點(diǎn)開始 由當(dāng)前頂點(diǎn)安排下一個頂點(diǎn)可設(shè)置的顏色 如果找到了可以設(shè)置的顏色

53、 置頂點(diǎn)顏色 如果已經(jīng)是最后一個頂點(diǎn) 得到一個解 回溯，繼續(xù)尋找下一個解 否則（未到最后） 準(zhǔn)備處理下一個頂點(diǎn) 否則（沒有找到可以設(shè)置的顏色） 回溯到上一個頂點(diǎn)，并去除該頂點(diǎn)的顏色,62,圖的m著色問題,63,圖的m著色問題,void Backtrac

54、k(int t){ if (t>n) { sum++; for (int i=1; i<=n; i++) cout << x[i] << ' '; cout << endl; } else for (int i=1;i<=m;i++) { x[t]=i; if (Ok(t))

55、Backtrack(t+1); }},,,復(fù)雜度分析圖m可著色問題的解空間樹中內(nèi)結(jié)點(diǎn)個數(shù)是對于每一個內(nèi)結(jié)點(diǎn)，在最壞情況下，用ok檢查當(dāng)前擴(kuò)展結(jié)點(diǎn)的每一個兒子所相應(yīng)的顏色可用性需耗時(shí)O(mn)。因此，回溯法總的時(shí)間耗費(fèi)是,64,問題：有一個售貨員要開車到N個指定的城市去推銷貨物，他必須經(jīng)過全部N個城市并且每個城市僅經(jīng)過一次?，F(xiàn)在他有一張n個城市的地圖并知道各個城市之間的公路里程，試問他應(yīng)該如何選取最短的行程從家里出發(fā)

56、對N個城市旅行一遍并再回到家中。,旅行售貨員問題,65,算法描述：初始化（起始狀態(tài)）；從圖的第一個頂點(diǎn)開始 由當(dāng)前頂點(diǎn)找下一個鄰接的頂點(diǎn) 如果比最小代價(jià)小 放當(dāng)前頂點(diǎn)城市到最短路徑中 如果已經(jīng)是最后一個頂點(diǎn) 得到一個解 撤掉該子，繼續(xù)尋找下一個解 否則（未到最后）

57、 準(zhǔn)備處理下一個鄰接頂點(diǎn) 否則 回溯到上一個頂點(diǎn)，并去除該頂點(diǎn)的分支,旅行售貨員問題,66,void Backtrack(int i){ if (i == n) { if (a[x[n-1]][x[n]] != NoEdge && a[x[n]][1] != NoEdge && (cc + a[x[n-1]][x[n]] + a[x[

58、n]][1] < bestc || bestc == NoEdge)) { for (int j = 1; j <= n; j++) bestx[j] = x[j]; bestc = cc + a[x[n-1]][x[n]] + a[x[n]][1];} } else { for (int j = i; j <= n; j++)

59、 // 是否可進(jìn)入x[j]子樹? if (a[x[i-1]][x[j]] != NoEdge && (cc + a[x[i-1]][x[i]] < bestc || bestc == NoEdge)) { // 搜索子樹 Swap(x[i], x[j]); cc += a[x[i-1]][x[i]];

60、 Backtrack(i+1); cc -= a[x[i-1]][x[i]]; Swap(x[i], x[j]);} }},復(fù)雜度分析算法backtrack在最壞情況下可能需要更新當(dāng)前最優(yōu)解O((n-1)!)次，每次更新bestc需計(jì)算時(shí)間O(n)，從而整個算法的計(jì)算時(shí)間復(fù)雜性為O(n!)。,67,分支限界法的剪枝搜

61、索策略分支限界法的算法分類裝載問題；0-1背包問題； 旅行售貨員問題；,第六章 分支限界法,分支限界法與回溯法的不同,（1）求解目標(biāo)：回溯法的求解目標(biāo)是找出解空間樹中滿足約束條件的所有解，而分支限界法的求解目標(biāo)則是找出滿足約束條件的一個解，或是在滿足約束條件的解中找出最優(yōu)解。,（2）搜索方式的不同：回溯法以深度優(yōu)先的方式搜索解空間樹，而分支限界法則以廣度優(yōu)先或以最小耗費(fèi)優(yōu)先的方式搜索解空間樹。,分支限界法的基本思想,分支限

62、界法的搜索策略是：在擴(kuò)展結(jié)點(diǎn)處，先生成其所有的兒子結(jié)點(diǎn)（分支），然后再從當(dāng)前的活結(jié)點(diǎn)表中選擇下一個擴(kuò)展結(jié)點(diǎn)。為了有效地選擇下一擴(kuò)展結(jié)點(diǎn)，以加速搜索的進(jìn)程，在每一活結(jié)點(diǎn)處，計(jì)算一個函數(shù)值（優(yōu)先級），并根據(jù)這些已計(jì)算出的函數(shù)值，從當(dāng)前活結(jié)點(diǎn)表中選擇一個最有利的結(jié)點(diǎn)作為擴(kuò)展結(jié)點(diǎn)，使搜索朝著解空間樹上有最優(yōu)解的分支推進(jìn)，以便盡快地找出一個最優(yōu)解。,分支限界法的分類,（1）隊(duì)列式(FIFO)分支限界法 按照隊(duì)列先進(jìn)先出（FIFO）原則選

63、取下一個節(jié)點(diǎn)為擴(kuò)展節(jié)點(diǎn)。,（2）優(yōu)先隊(duì)列式分支限界法 按照優(yōu)先隊(duì)列中規(guī)定的優(yōu)先級選取優(yōu)先級最高的節(jié)點(diǎn)成為當(dāng)前擴(kuò)展節(jié)點(diǎn)。,從活結(jié)點(diǎn)表中選擇下一擴(kuò)展結(jié)點(diǎn)的不同方式導(dǎo)致不同的分支限界法。常見的兩種分支限界法,0-1背包問題,0-1背包問題： 給定n種物品和一個背包。物品i的重量是Wi，其價(jià)值為Vi，背包的容量為C。應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大?,首先，要對輸入數(shù)據(jù)進(jìn)行預(yù)處理，將各物品依其單位重

64、量價(jià)值從大到小進(jìn)行排列。,在使用優(yōu)先隊(duì)列分支限界法中，節(jié)點(diǎn)的優(yōu)先級由已裝袋的物品價(jià)值加上剩下的最大單位重量價(jià)值的物品裝滿剩余容量的價(jià)值和。,0-1背包問題,算法描述:初始化，將物品按照單位價(jià)值的從大到小順序排列；從第一個物品開始 左兒子加入后可否滿足控制約束將頂點(diǎn)i加入到最大優(yōu)先隊(duì)列中 修改最大價(jià)值,修改上界條件 否則檢查右兒子可否滿足條件將右兒子加入優(yōu)先隊(duì)列修改上界條件取下一擴(kuò)展結(jié)點(diǎn)當(dāng)隊(duì)列為空時(shí)輸出當(dāng)

65、前記錄的路徑,裝載問題,有一批共n個集裝箱要裝上2艘載重量分別為C1和C2的輪船，其中集裝箱i的重量為Wi，且,裝載問題要求確定是否有一個合理的裝載方案可將這n個集裝箱裝上這2艘輪船。如果有，找出一種裝載方案。,容易證明：如果一個給定裝載問題有解，則采用下面的策略可得到最優(yōu)裝載方案。 (1)首先將第一艘輪船盡可能裝滿；(2)將剩余的集裝箱裝上第二艘輪船。,隊(duì)列式分支限界法 算法描述：未搜索到樹的結(jié)束檢查左兒子結(jié)點(diǎn)是否

66、滿足約束條件左兒子加入擴(kuò)展隊(duì)列根據(jù)當(dāng)前修改當(dāng)前最優(yōu)解（可裝載的最大重量）右兒子結(jié)點(diǎn)總是可行的，加入隊(duì)列取下一擴(kuò)展結(jié)點(diǎn) 判斷是否同層結(jié)點(diǎn)尾部（－1） 如果隊(duì)空返回最優(yōu)解（可裝載的最大重量） 加入同層結(jié)點(diǎn)尾部標(biāo)志 取下一擴(kuò)展結(jié)點(diǎn) 進(jìn)入下一層,75,旅行售貨員問題,1. 問題描述,某售貨員要到若干城市去推銷商品，已知各城市之間的

67、路程(或旅費(fèi))。他要選定一條從駐地出發(fā)，經(jīng)過每個城市一次，最后回到駐地，使總的路程最小。 旅行售貨員問題的解空間可以組織成一棵樹，從樹的根結(jié)點(diǎn)到任一葉結(jié)點(diǎn)的路徑定義了圖的一條周游路線。旅行售貨員問題要在圖G中找出費(fèi)用最小的周游路線。這里可以用優(yōu)先隊(duì)列式實(shí)現(xiàn)方式。,76,旅行售貨員問題,2. 算法描述,在實(shí)現(xiàn)過程中，使用一個最小優(yōu)先隊(duì)列來記錄活節(jié)點(diǎn)，隊(duì)列中每個節(jié)點(diǎn)的類型為MinHeapNode。x [ 0 : n - 1 ]為解

68、的結(jié)構(gòu)，cc為解空間樹中從根 節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的耗費(fèi)，lcost為該節(jié)點(diǎn)子樹中任意葉節(jié)點(diǎn)中的最小耗費(fèi)， rcost為從頂點(diǎn)x [ s : n - 1 ]出發(fā)的所有邊的最小耗費(fèi)之和。圖中每個頂點(diǎn)的最小費(fèi)用出邊并用minout記錄。b＝cc＋rcost為當(dāng)前結(jié)點(diǎn)的下界。,77,旅行售貨員問題,2. 算法描述,算法中循環(huán)的終止條件是樹的一個葉結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)。當(dāng)s=n-1時(shí)，已找到的回路前綴是x[0:n-1]，它已包含圖G的所有n個頂點(diǎn)。

69、因此，當(dāng)s=n-1時(shí)，相應(yīng)的擴(kuò)展結(jié)點(diǎn)表示一個葉結(jié)點(diǎn)。此時(shí)該葉結(jié)點(diǎn)所相應(yīng)的回路的費(fèi)用等于cc和當(dāng)前葉節(jié)點(diǎn)下界lcost的值。剩余的活結(jié)點(diǎn)的lcost值不小于已找到的回路的費(fèi)用。它們都不可能導(dǎo)致費(fèi)用更小的回路。因此已找到的葉結(jié)點(diǎn)所相應(yīng)的回路是一個最小費(fèi)用旅行售貨員回路，算法可以結(jié)束。 算法結(jié)束時(shí)返回找到的最小費(fèi)用，相應(yīng)的最優(yōu)解也可得到。,產(chǎn)生偽隨機(jī)數(shù)的算法數(shù)值隨機(jī)化算法的設(shè)計(jì)思想 拉斯維加斯算法的設(shè)計(jì)思想舍伍德算法的設(shè)計(jì)思想,第