算法分析總復習

1、總復習,,第一章 緒 論,算法的概念。程序與算法的區(qū)別和聯(lián)系。算法的計算復雜性,算法和程序,算法是指解決問題的一種方法或一個過程。算法是若干指令的有窮序列，滿足性質：(1)輸入 (2)輸出 (3)確定性 (4)有限性程序是算法用某種程序設計語言的具體實現(xiàn)。程序可以不滿足算法的性質(4)。,算法復雜性分析,算法復雜性 = 算法所需要的計算機資源算法的時間復雜性T(n)；算法的空間復雜性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ù)乘法；Strassen矩陣乘法；棋盤覆蓋；合并排序和快速排序；循環(huán)賽日程

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

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

5、將n-1個較小的圓盤依照移動規(guī)則從塔座a移至塔座c，然后，將剩下的最大圓盤從塔座a移至塔座b，最后，再設法將n-1個較小的圓盤依照移動規(guī)則從塔座c移至塔座b。由此可見，n個圓盤的移動問題可分為2次n-1個圓盤的移動問題，這又可以遞歸地用上述方法來做。由此可以設計出解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ī)?？s小到一定的程度就可以容易地解決；該問題可以分解為若干個規(guī)模較小的相同問題，即該問題具有最優(yōu)子結構性質利用該問題分解出的子問題的解可以合并

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

8、:n-1]，現(xiàn)要在這n個元素中找出一特定元素x。,分析：很顯然此問題分解出的子問題相互獨立，，子問題縮小到一定規(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;},時間復雜性為O(logn),大整數(shù)的乘法,設計一個有效的算法進行兩個n位大整數(shù)的乘法運算,分治法：X = a 2n/2 + b Y = c 2n/2 + d XY = ac 2n +

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

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

12、用一個L型骨牌覆蓋這3個較小棋盤的會合處，從而將原問題轉化為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);} // 覆蓋其余方格 // 覆蓋右上角子棋盤 // 覆蓋左下角子棋盤 // 覆蓋右下角子棋盤 },復雜度分析T(n)=O(4k) 漸進意義下的最優(yōu)算法,合并排序,基本思想：將待排序元素分成大小大致相同的2個子集合，分別對2個子集合進行排序，最終將排好序的子集合合并成為所要求的排好

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

16、t); //合并到數(shù)組b copy(a, b, left, right); //復制回數(shù)組a } },復雜度分析T(n)=O(nlogn) 漸進意義下的最優(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); //對右半段排序 }},最壞時間復雜度：O(n2)平均時間復雜度：O(nlogn)輔助空間：O(n)或O(logn),在快速排序中，記錄的比較和交換是從兩端向中間進行的，關鍵字較大的記錄一次就能交換到后面單元，關鍵字較小的記錄一次就能交換到前面單元，記錄每次移動的距離較大，因而總的比較和移動次數(shù)較少。,循環(huán)賽日程安排

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

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

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

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

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

23、列下標) = 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 } 并紀錄：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++)//計算矩陣序列長度為r

24、時所需乘法次數(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號矩陣為分隔點for(int k=i+1;k<j;k++)//k陣為分隔點時乘法次數(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號矩陣為分隔點 }} }},算法復雜度分析：算法matrixChain的主要計算量取決于算法中對r，i和k的3重循環(huán)。循環(huán)體內的計算量為O(1)，而3重循環(huán)的總次數(shù)為O(n3)。因此算法的計算時間上界為O(n3)。算法所占用的空間顯然為O(n2)。,最長公共子序列,若給定序列X={x1,x2

26、,…,xm}，則序列Z={z1,z2,…,zk}是X的子序列是指存在一個嚴格遞增下標序列{i1,i2,…,ik}使得對于所有j=1,2,…,k有：zj=xij。,最優(yōu)子結構性質：2個序列的最長公共子序列包含了這2個序列的前綴的最長公共子序列。,最長公共子序列的結構,設序列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的最長公共子序列。,子問題的遞歸結構,由最長公共子序列問題的最優(yōu)子結構性質建立子問題最優(yōu)值的遞歸關系。用c[i][j]記錄兩序列的最長公共子序列的長度。其中， Xi={x1,x2,…,xi}；Yj={y1,y2,…,yj}。建立遞歸關系如下：,,計算最優(yōu)值,在所考慮的子問題空間中，總共

28、有? (mn)個不同的子問題，因此，用動態(tài)規(guī)劃算法自底向上地計算最優(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; }}},算法復雜度分析：算法LCSlength的主要計算量取決于算法中對i和j的2重循環(huán)。循環(huán)體內的計算量為O(1)，而2重循環(huán)的總次數(shù)為O(n2)。因此算法的計算時間上界為O(n2)。算法所占用的空間顯然為O(n2)。,構造最長公共子序列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è)調度,n個作業(yè){1，2，…，n}要在由2臺機器M1和M2組成的流水線上完成

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

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

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

34、包的物品，使得裝入背包中物品的總價值最大?,,,,,在考慮0-1背包問題時，應比較選擇該物品和不選擇該物品所導致的最終方案，然后再作出最好選擇。由此就導出許多互相重疊的子問題,可用動態(tài)規(guī)劃算法求解。,39,0-1背包問題,0-1背包問題,40,設所給0-1背包問題的子問題,,,m(i，j)是背包容量為j，可選擇物品為i，i+1，…，n時0-1背包問題的最優(yōu)值。,,,0-1背包問題,41,由0-1背包問題的最優(yōu)子結構性質，可以建立計算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;},算法復雜度分析：從m(i，j)的遞歸式容易看出，算法需要O(nc)計算時間。當背包容量c很大時，算法需要的計算時間較多。例如，當c>2n時，算法需要Ω(n2n)計算時間。,貪心算法的概念及基本要素 活動安排問題；最優(yōu)裝載問題

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

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

40、始時間晚于最后一個選入A的活動ej的結束時間，則將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)裝載問題可用貪心算法求解。采用重量最輕者先裝的貪心選擇策略，可產生最優(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、;}},哈夫曼編碼,構造哈夫曼編碼哈夫曼提出構造最優(yō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,問題的所有的解構造成樹的結構，稱解空間樹?；厮莘ň褪菑母Y點出發(fā)按深度優(yōu)先策略搜索整個解空間樹，得到一個或者所有解。這種方法適用于解一些組合數(shù)相當大的問題。當算法搜索至解空間樹的任意一點時，先判斷該結點是否包含問題的解。如果不包含，則跳過對該結點為根的子樹的搜索，向其結點回溯；否則，進入該子樹，繼續(xù)按深度優(yōu)先策略搜索。,回溯法的一般方法,57,回溯法的基本步驟,(1)針對所給問題，定義問

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

50、一個王后，因此為了簡化狀態(tài)空間樹，采用逐行布局的方式，即每個布局有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,復雜度分析 N皇后問題的復雜度取決于回溯算法的調用次數(shù),隨著N值的增加,回溯算法的調用次數(shù)也增加,而且其增加的速度非常的快.當把一個皇后放進棋盤中的某一行中時,回溯算法將被調用以試探是否會和已有的皇后沖突,對

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

53、 置頂點顏色 如果已經(jīng)是最后一個頂點 得到一個解 回溯，繼續(xù)尋找下一個解 否則（未到最后） 準備處理下一個頂點 否則（沒有找到可以設置的顏色） 回溯到上一個頂點，并去除該頂點的顏色,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); }},,,復雜度分析圖m可著色問題的解空間樹中內結點個數(shù)是對于每一個內結點，在最壞情況下，用ok檢查當前擴展結點的每一個兒子所相應的顏色可用性需耗時O(mn)。因此，回溯法總的時間耗費是,64,問題：有一個售貨員要開車到N個指定的城市去推銷貨物，他必須經(jīng)過全部N個城市并且每個城市僅經(jīng)過一次?，F(xiàn)在他有一張n個城市的地圖并知道各個城市之間的公路里程，試問他應該如何選取最短的行程從家里出發(fā)

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

57、 準備處理下一個鄰接頂點 否則 回溯到上一個頂點，并去除該頂點的分支,旅行售貨員問題,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、 // 是否可進入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]);} }},復雜度分析算法backtrack在最壞情況下可能需要更新當前最優(yōu)解O((n-1)!)次，每次更新bestc需計算時間O(n)，從而整個算法的計算時間復雜性為O(n!)。,67,分支限界法的剪枝搜

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

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

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

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

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

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

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

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

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