1、算法是指解決問題的一種方法或一個過程。算法是若干指令的有窮序列，滿足性質：(1)輸入：有外部提供的量作為算法的輸入。(2)輸出：算法產生至少一個量作為輸出。(3)確定性：組成算法的每條指令是清晰，無歧義的。(4)有限性：算法中每條指令的執行次數是有限的，執行每條指令的時間也是有限的。程序是算法用某種程序設計語言的具體實現。程序可以不滿足算法的性質(4)。分治法的設計思想是，將一個難以直接解決的大問題，分割成一些規模較小的相同問題，以便各個擊破，分而治之。直接或間接地調用自身的算法稱為遞歸算法。用函數自身給出定義的函數稱為遞歸函數。1.階乘函數 階乘函數可遞歸地定義為： 邊界條件 遞歸方程邊界條

2、件與遞歸方程是遞歸函數的二個要素2.Fibonacci數列無窮數列1，1，2，3，5，8，13，21，34，55，稱為Fibonacci數列。它可以遞歸地定義為：當一個函數及它的一個變量是由函數自身定義時，稱這個函數是雙遞歸函數。Ackerman函數A(n，m)定義如下：Ackerman函數A(n，m)的自變量m的每一個值都定義了一個單變量函數：M=0時，A(n,0)=n+2M=1時，A(n,1)=A(A(n-1,1),0)=A(n-1,1)+2，和A(1,1)=2故A(n,1)=2*nM=2時，A(n,2)=A(A(n-1,2),1)=2A(n-1,2)，和A(1,2)=A(A(0,2),1

3、)=A(1,1)=2，故A(n,2)= 2n 。M=3時，類似的可以推出M=4時，A(n,4)的增長速度非常快，以至于沒有適當的數學式子來表示這一函數。定義單變量的Ackerman函數A(n)為，A(n)=A(n，n)。定義其擬逆函數(n)為：(n)=minkA(k)n。即(n)是使nA(k)成立的最小的k值。(n)在復雜度分析中常遇到。對于通常所見到的正整數n，有(n)4。但在理論上(n)沒有上界，隨著n的增加，它以難以想象的慢速度趨向正無窮大。6排列問題設計一個遞歸算法生成n個元素r1,r2,rn的全排列。設R=r1,r2,rn是要進行排列的n個元素，Ri=R-ri。集合X中元素的全排列記

4、為perm(X)。(ri)perm(X)表示在全排列perm(X)的每一個排列前加上前綴得到的排列。R的全排列可歸納定義如下： 當n=1時，perm(R)=(r)，其中r是集合R中唯一的元素；當n>1時，perm(R)由(r1)perm(R1)，(r2)perm(R2)，(rn)perm(Rn)構成。 7整數劃分問題在本例中，如果設p(n)為正整數n的劃分數，則難以找到遞歸關系，因此考慮增加一個自變量：將最大加數n1不大于m的劃分個數記作q(n,m)。可以建立q(n,m)的如下遞歸關系。(3) q(n,n)=1+q(n,n-1);正整數n的劃分由n1=n的劃分和n1n-1的劃分組成。(4

5、) q(n,m)=q(n,m-1)+q(n-m,m),n>m>1;正整數n的最大加數n1不大于m的劃分由n1=m的劃分和n1n-1 的劃分組成。8.Hanoi塔問題 設a,b,c是3個塔座。開始時，在塔座a上有一疊共n個圓盤，這些圓盤自下而上，由大到小地疊在一起。各圓盤從小到大編號為1,2,n,現要求將塔座a上的這一疊圓盤移到塔座b上，并仍按同樣順序疊置。在移動圓盤時應遵守以下移動規則：規則1：每次只能移動1個圓盤；規則2：任何時刻都不允許將較大的圓盤壓在較小的圓盤之上；規則3：在滿足移動規則1和2的前提下，可將圓盤移至a,b,c中任一塔座上。public static void

6、hanoi(int n, int a, int b, int c) if (n > 0) hanoi(n-1, a, c, b); move(a,b); hanoi(n-1, c, b, a); 遞歸小結:優點：結構清晰，可讀性強，而且容易用數學歸納法來證明算法的正確性，因此它為設計算法、調試程序帶來很大方便。缺點：遞歸算法的運行效率較低，無論是耗費的計算時間還是占用的存儲空間都比非遞歸算法要多。分治法的適用條件分治法所能解決的問題一般具有以下幾個特征：1.該問題的規模縮小到一定的程度就可以容易地解決；2.該問題可以分解為若干個規模較小的相同問題，即該問題具有最優子結構性質3.利用該問題

7、分解出的子問題的解可以合并為該問題的解；4.該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子問題。 這條特征涉及到分治法的效率，如果各子問題是不獨立的，則分治法要做許多不必要的工作，重復地解公共的子問題，此時雖然也可用分治法，但一般用動態規劃較好。人們從大量實踐中發現，在用分治法設計算法時，最好使子問題的規模大致相同。即將一個問題分成大小相等的k個子問題的處理方法是行之有效的。這種使子問題規模大致相等的做法是出自一種平衡(balancing)子問題的思想，它幾乎總是比子問題規模不等的做法要好。9二分搜索技術給定已按升序排好序的n個元素a0:n-1，現要在這n個元素中找出一特定

8、元素x。二分搜索算法：public static int binarySearch(int a, int x, int n) / 在 a0 <= a1 <= . <= an-1 中搜索 x / 找到x時返回其在數組中的位置，否則返回-1 int left = 0; int right = n - 1; while (left <= right) int middle = (left + right)/2; if (x = amiddle) return middle; if (x > amiddle) left = middle + 1; else right =

9、 middle - 1; return -1; / 未找到x 算法復雜度分析：每執行一次算法的while循環， 待搜索數組的大小減少一半。因此，在最壞情況下，while循環被執行了O(logn) 次。循環體內運算需要O(1) 時間，因此整個算法在最壞情況下的計算時間復雜性為O(logn) 。合并排序：基本思想：將待排序元素分成大小大致相同的2個子集合，分別對2個子集合進行排序，最終將排好序的子集合合并成為所要求的排好序的集合。 最壞時間復雜度：O(nlogn) 平均時間復雜度：O(nlogn) 輔助空間：O(n)快速排序:最壞時間復雜度：O(n2) 平均時間復雜度：O(nlogn) 輔助空間：

10、O(n)或O(logn)動態規劃算法的基本要素（1）最優子結構性質（2）重疊子問題性質1利用問題的最優子結構性質，以自底向上的方式遞歸地從子問題的最優解逐步構造出整個問題的最優解。最優子結構是問題能用動態規劃算法求解的前提。2.遞歸算法求解問題時，每次產生的子問題并不總是新問題，有些子問題被反復計算多次。這種性質稱為子問題的重疊性質。 動態規劃算法，對每一個子問題只解一次，而后將其解保存在一個表格中，當再次需要解此子問題時，只是簡單地用常數時間查看一下結果。 通常不同的子問題個數隨問題的大小呈多項式增長。因此用動態規劃算法只需要多項式時間，從而獲得較高的解題效率。 備忘錄方法備忘錄方法的控制結

11、構與直接遞歸方法的控制結構相同，區別在于備忘錄方法為每個解過的子問題建立了備忘錄以備需要時查看，避免了相同子問題的重復求解。動態規劃基本步驟:1.找出最優解的性質，并刻劃其結構特征。2.遞歸地定義最優值。 3.以自底向上的方式計算出最優值。4.根據計算最優值時得到的信息，構造最優解。動態規劃基本思想是將待求解問題分解成若干個子問題，但是經分解得到的子問題往往不是互相獨立的。不同子問題的數目常常只有多項式量級。在用分治法求解時，有些子問題被重復計算了許多次。如果能夠保存已解決的子問題的答案，而在需要時再找出已求得的答案，就可以避免大量重復計算，從而得到多項式時間算法。 0/1背包問題 0/1背包

12、問題的求解過程一、動態規劃函數：物體被裝入背包的情況，。約束方程和目標函數：解向量。背包的載重量： ：前個物體中，能裝入載重量為的背包中的物體的最大價值，。動態規劃函數：（）（）二、求解過程 1、決策階段：第一階段，只裝入一個物體，確定在各種不同載重量的背包下，能夠得到的最大價值；第二階段，裝入前兩個物體，確定在各種不同載重量的背包下，能夠得到的最大價值；依此類推，直到第個階段。最后，便是在載重量為的背包下，裝入個物體時，能夠取得的最大價值。2、解向量的確定從的值向前倒推。遞推關系式：若 則（）若 則，（）例6.6 有5個物體，其重量分別為2,2,6,5,4，價值分別為6,3,5,4,6，背包

13、的載重量為10，求裝入背包的物體及其總價值計算結果，如圖6.7所示。圖6.7 5個物體的0/1背包問題的例子裝入背包的物體為。0-1背包問題給定n種物品和一背包。物品i的重量是wi，其價值為vi，背包的容量為C。問應如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大?0-1背包問題是一個特殊的整數規劃問題。設所給0-1背包問題的子問題的最優值為m(i，j)，即m(i，j)是背包容量為j，可選擇物品為i，i+1，n時0-1背包問題的最優值。由0-1背包問題的最優子結構性質，可以建立計算m(i，j)的遞歸式如下。算法復雜度分析：從m(i，j)的遞歸式容易看出，算法需要O(nc)計算時間。當背包

14、容量c很大時，算法需要的計算時間較多。例如，當c>2n時，算法需要(n2n)計算時間。 二叉搜索樹（1）若它的左子樹不空，則左子樹上所有節點的值均小于它的根節點的值；（2）若它的右子樹不空，則右子樹上所有節點的值均大于它的根節點的值；（3 它的左、右子樹也分別為二叉排序樹最優二叉搜索樹最優二叉搜索樹Tij的平均路長為pij，則所求的最優值為p1,n。由最優二叉搜索樹問題的最優子結構性質可建立計算pij的遞歸式如下記wi,jpi,j為m(i,j)，則m(1,n)=w1,np1,n=p1,n為所求的最優值。計算m(i,j)的遞歸式為注意到 可以得到O(n2)的算法多段圖的最短路徑問題定義6.

15、1 有向連通賦權圖，頂點集合劃分成個不相交的子集，使得中的任一邊，必有，。稱為多段圖。令，稱為源點，為收點。多段圖的最短路徑問題，是求從源點到達收點的最小花費的通路一、頂點編號：根據多段圖的個不相交的子集，把多段圖劃分為段，每一段包含頂點的一個子集。把頂點集合中的所有頂點，按照段的順序進行編號。子集中的頂點互不鄰接，它們之間的相互順序無關緊要。頂點個數為，頂點的編號為0，則收點的編號為，對中的任何一條邊，頂點的編號小于頂點的編號。二、決策過程數組元素：存放頂點到達收點的最小花費數組元素：存放頂點到達收點的最小花費通路上的前方頂點編號數組：存放從源點出發，到達收點的最短通路上的頂點編號第一階段，

16、確定第段的所有頂點到達收點的花費最小的通路。第二階段，用第一階段的信息，確定第段的所有頂點到達收點的花費最小的通路。如此依次進行，直到最后確定源點到達收點的花費最小的通路。最后，從源點的信息中，確定它的前方頂點編號，從的信息中，確定的前方頂點編號，如此遞推，直到收點。動態規劃函數：（）（）三、步驟：1. 對所有的，把初始化為最大值，初始化為-1；初始化為0；2. 令；3. 根據（和；4. ，若，轉3；否則，轉5；5. 令，；6. 如果，算法結束；否則，轉7；7. ，；轉6；例6.2 求解圖6.3所示的最短路徑問題。圖6.3 動態規劃方法求解多段圖的例子： ： ： ： ： ： ： ： ： 最后，

17、得到最短的路徑為0，2，3，5，8，9，費用是15。貪心算法的基本要素貪心選擇性質和最優子結構性質。 所謂貪心選擇性質是指所求問題的整體最優解可以通過一系列局部最優的選擇，即貪心選擇來達到。這是貪心算法可行的第一個基本要素，也是貪心算法與動態規劃算法的主要區別。動態規劃算法通常以自底向上的方式解各子問題，而貪心算法則通常以自頂向下的方式進行，以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問題簡化為規模更小的子問題。 最優子結構性質 當一個問題的最優解包含其子問題的最優解時，稱此問題具有最優子結構性質。問題的最優子結構性質是該問題可用動態規劃算法或貪心算法求解的關鍵特征。 0-1背包問

18、題： 給定n種物品和一個背包。物品i的重量是Wi，其價值為Vi，背包的容量為C。應如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大?在選擇裝入背包的物品時，對每種物品i只有2種選擇，即裝入背包或不裝入背包。不能將物品i裝入背包多次，也不能只裝入部分的物品i。背包問題：與0-1背包問題類似，所不同的是在選擇物品i裝入背包時，可以選擇物品i的一部分，而不一定要全部裝入背包，1in。這2類問題都具有最優子結構性質，極為相似，但背包問題可以用貪心算法求解，而0-1背包問題卻不能用貪心算法求解。 用貪心算法解背包問題的基本步驟： 首先計算每種物品單位重量的價值Vi/Wi，然后，依貪心選擇策略，將盡

19、可能多的單位重量價值最高的物品裝入背包。若將這種物品全部裝入背包后，背包內的物品總重量未超過C，則選擇單位重量價值次高的物品并盡可能多地裝入背包。依此策略一直地進行下去，直到背包裝滿為止。算法knapsack的主要計算時間在于將各種物品依其單位重量的價值從大到小排序。因此，算法的計算時間上界為O（nlogn）。當然，為了證明算法的正確性，還必須證明背包問題具有貪心選擇性質。最優裝載有一批集裝箱要裝上一艘載重量為c的輪船。其中集裝箱i的重量為Wi。最優裝載問題要求確定在裝載體積不受限制的情況下，將盡可能多的集裝箱裝上輪船。最優裝載問題可用貪心算法求解。采用重量最輕者先裝的貪心選擇策略，可產生最優

20、裝載問題的最優解。算法loading的主要計算量在于將集裝箱依其重量從小到大排序，故算法所需的計算時間為 O(nlogn)。哈夫曼編碼對每一個字符規定一個0,1串作為其代碼，并要求任一字符的代碼都不是其它字符代碼的前綴。這種編碼稱為前綴碼。表示最優前綴碼的二叉樹總是一棵完全二叉樹，即樹中任一結點都有2個兒子結點。平均碼長定義為： 使平均碼長達到最小的前綴碼編碼方案稱為給定編碼字符集C的最優前綴碼。構造哈夫曼編碼哈夫曼提出構造最優前綴碼的貪心算法，由此產生的編碼方案稱為哈夫曼編碼。哈夫曼算法以自底向上的方式構造表示最優前綴碼的二叉樹T。算法以|C|個葉結點開始，執行|C|1次的“合并”運算后產生

21、最終所要求的樹T。 算法huffmanTree用最小堆實現優先隊列Q。初始化優先隊列需要O(n)計算時間，由于最小堆的removeMin和put運算均需O(logn)時間，n1次的合并總共需要O(nlogn)計算時間。因此，關于n個字符的哈夫曼算法的計算時間為O(nlogn) 。哈夫曼算法的正確性：要證明哈夫曼算法的正確性，只要證明最優前綴碼問題具有貪心選擇性質和最優子結構性質。 (1)貪心選擇性質(2)最優子結構性質單源最短路徑給定帶權有向圖G =(V,E)，其中每條邊的權是非負實數。另外，還給定V中的一個頂點，稱為源。現在要計算從源到所有其它各頂點的最短路長度。這里路的長度是指路上各邊權之

22、和。這個問題通常稱為單源最短路徑問題。算法基本思想：dijkstra算法是解單源最短路徑問題的貪心算法。基本思想是，設置頂點集合S并不斷地作貪心選擇來擴充這個集合。一個頂點屬于集合S當且僅當從源到該頂點的最短路徑長度已知。初始時，S中僅含有源。設u是G的某一個頂點，把從源到u且中間只經過S中頂點的路稱為從源到u的特殊路徑，并用數組dist記錄當前每個頂點所對應的最短特殊路徑長度。Dijkstra算法每次從V-S中取出具有最短特殊路長度的頂點u，將u添加到S中，同時對數組dist作必要的修改。一旦S包含了所有V中頂點，dist就記錄了從源到所有其它頂點之間的最短路徑長度。Dijkstra算法的迭

23、代過程： 迭代Sudist2dist3dist4dist5初始1-10maxint3010011,2210603010021,2,441050309031,2,4,331050306041,2,4,3,5510503060計算復雜性：對于具有n個頂點和e條邊的帶權有向圖，如果用帶權鄰接矩陣表示這個圖，那么Dijkstra算法的主循環體需要 時間。這個循環需要執行n-1次，所以完成循環需要 時間。算法的其余部分所需要時間不超過 。解最短路徑的狄斯奎諾（Dijkstra）算法是中的邊，是邊的長度。劃分為兩個集合和：中所包含的頂點，它們到的距離已經確定；中所包含的頂點，它們到的距離尚未確定。是從頂點

24、到頂點的最短路徑中的前一頂點1. 置，；2. ，若，則，；否則，；3. 尋找，使得，則；就是到的距離；4. ，；5. 若，算法結束；否則，轉6；6. 對與相鄰接的所有頂點，如果，直接轉3；否則，令，轉3；例5.3 在圖5.3的有向賦權圖中，求頂點到其它所有頂點的距離。如果用鄰接表來存放頂點之間的距離，則鄰接表如圖5.4所示。圖5.3 頂點a到其它所有頂點的最短距離的有向賦權圖圖5.4 圖5.3中所表示的賦權圖的鄰接表表5.1表示對上面的有向賦權圖，執行狄斯奎諾算法時，每一輪循環的執行過程。從頂點到其它所有頂點的路徑，如圖5.5所示。 表5.1 狄斯奎諾算法的執行過程1a1441b2a,b341

25、03c3a,b,c49674d4a,b,c,d9676f5a,b,c,d,f87117g6a,b,c,d,f,g8108e7a,b,c,d,f,g,e99h8a,b,c,d,f,g,e,h圖5.5 各個頂點到頂點a的路徑最小生成樹 設G =(V,E)是無向連通帶權圖，即一個網絡。E中每條邊(v,w)的權為cvw。如果G的子圖G是一棵包含G的所有頂點的樹，則稱G為G的生成樹。生成樹上各邊權的總和稱為該生成樹的耗費。在G的所有生成樹中，耗費最小的生成樹稱為G的最小生成樹。最小生成樹性質：設G=(V,E)是連通帶權圖，U是V的真子集。如果(u,v)ÎE，且uÎU，vÎV

26、-U，且在所有這樣的邊中，(u,v)的權cuv最小，那么一定存在G的一棵最小生成樹，它以(u,v)為其中一條邊。這個性質有時也稱為MST性質。 普里姆（Prim）算法頂點集為，與頂點,相關聯的邊為，權用表示，是最小花費生成樹的邊集。維護兩個頂點集合和，開始時：令，。選取,，并且最小的和；，。重復上述步驟，直到為空，或找到條邊為止。步驟：1，；2. 如果為空，算法結束；否則，轉3；3. 尋找使,，并且最小的和；4. ，；轉2；圖5.9 普里姆算法的工作過程Prim算法 設G=(V,E)是連通帶權圖，V=1,2,n。構造G的最小生成樹的Prim算法的基本思想是：首先置S=1，然后，只要S是V的真子

27、集，就作如下的貪心選擇：選取滿足條件iÎS，jÎV-S，且cij最小的邊，將頂點j添加到S中。這個過程一直進行到S=V時為止。在這個過程中選取到的所有邊恰好構成G的一棵最小生成樹。 在上述Prim算法中，還應當考慮如何有效地找出滿足條件iÎS,jÎV-S，且權cij最小的邊(i,j)。實現這個目的的較簡單的辦法是設置2個數組closest和lowcost。在Prim算法執行過程中，先找出V-S中使lowcost值最小的頂點j，然后根據數組closest選取邊(j,closestj)，最后將j添加到S中，并對closest和lowcost作必要的修改。用這

28、個辦法實現的Prim算法所需的計算時間為 Kruskal算法：Kruskal算法構造G的最小生成樹的基本思想是，首先將G的n個頂點看成n個孤立的連通分支。將所有的邊按權從小到大排序。然后從第一條邊開始，依邊權遞增的順序查看每一條邊，并按下述方法連接2個不同的連通分支：當查看到第k條邊(v,w)時，如果端點v和w分別是當前2個不同的連通分支T1和T2中的頂點時，就用邊(v,w)將T1和T2連接成一個連通分支，然后繼續查看第k+1條邊；如果端點v和w在當前的同一個連通分支中，就直接再查看第k+1條邊。這個過程一直進行到只剩下一個連通分支時為止。 關于集合的一些基本運算可用于實現Kruskal算法。

29、 按權的遞增順序查看等價于對優先隊列執行removeMin運算。可以用堆實現這個優先隊列。 對一個由連通分支組成的集合不斷進行修改，需要用到抽象數據類型并查集UnionFind所支持的基本運算。當圖的邊數為e時，Kruskal算法所需的計算時間是 。當 時，Kruskal算法比Prim算法差，但當 時，Kruskal算法卻比Prim算法好得多。回溯法適用于解一些組合數相當大的問題。回溯法在問題的解空間樹中，按深度優先策略，從根結點出發搜索解空間樹。算法搜索至解空間樹的任意一點時，先判斷該結點是否包含問題的解。如果肯定不包含，則跳過對該結點為根的子樹的搜索，逐層向其祖先結點回溯；否則，進入該子樹

30、，繼續按深度優先策略搜索。問題的解向量：回溯法希望一個問題的解能夠表示成一個n元式(x1,x2,xn)的形式。顯約束：對分量xi的取值限定。隱約束：為滿足問題的解而對不同分量之間施加的約束。解空間：對于問題的一個實例，解向量滿足顯式約束條件的所有多元組，構成了該實例的一個解空間。生成問題狀態的基本方法擴展結點:一個正在產生兒子的結點稱為擴展結點活結點:一個自身已生成但其兒子還沒有全部生成的節點稱做活結點死結點:一個所有兒子已經產生的結點稱做死結點深度優先的問題狀態生成法：如果對一個擴展結點R，一旦產生了它的一個兒子C，就把C當做新的擴展結點。在完成對子樹C（以C為根的子樹）的窮盡搜索之后，將R

31、重新變成擴展結點，繼續生成R的下一個兒子（如果存在）寬度優先的問題狀態生成法：在一個擴展結點變成死結點之前，它一直是擴展結點回溯法：為了避免生成那些不可能產生最佳解的問題狀態，要不斷地利用限界函數(bounding function)來處死那些實際上不可能產生所需解的活結點，以減少問題的計算量。具有限界函數的深度優先生成法稱為回溯法回溯法的基本思想(1)針對所給問題，定義問題的解空間；(2)確定易于搜索的解空間結構；(3)以深度優先方式搜索解空間，并在搜索過程中用剪枝函數避免無效搜索。常用剪枝函數：用約束函數在擴展結點處剪去不滿足約束的子樹；用限界函數剪去得不到最優解的子樹。子集樹與排列樹遍歷

32、子集樹需O(2n)計算時間 void backtrack (int t) if (t>n) output(x); else for (int i=0;i<=1;i+) xt=i; if (legal(t) backtrack(t+1); 遍歷排列樹需要O(n!)計算時間 void backtrack (int t) if (t>n) output(x); else for (int i=t;i<=n;i+) swap(xt, xi); if (legal(t) backtrack(t+1); swap(xt, xi); 裝載問題有一批共n個集裝箱要裝上2艘載重量分別為c

33、1和c2的輪船，其中集裝箱i的重量為wi，且裝載問題要求確定是否有一個合理的裝載方案可將這個集裝箱裝上這2艘輪船。如果有，找出一種裝載方案。容易證明，如果一個給定裝載問題有解，則采用下面的策略可得到最優裝載方案。(1)首先將第一艘輪船盡可能裝滿；(2)將剩余的集裝箱裝上第二艘輪船。將第一艘輪船盡可能裝滿等價于選取全體集裝箱的一個子集，使該子集中集裝箱重量之和最接近。由此可知，裝載問題等價于以下特殊的0-1背包問題。用回溯法設計解裝載問題的O(2n)計算時間算法。在某些情況下該算法優于動態規劃算法。n后問題解向量：(x1, x2, , xn) 顯約束：xi=1,2, ,n隱約束：1)不同列：xi

34、¹xj 2)不處于同一正、反對角線：|i-j|¹|xi-xj|0-1背包問題解空間：子集樹 可行性約束函數：圖的m著色問題給定無向連通圖G和m種不同的顏色。用這些顏色為圖G的各頂點著色，每個頂點著一種顏色。是否有一種著色法使G中每條邊的2個頂點著不同顏色。這個問題是圖的m可著色判定問題。若一個圖最少需要m種顏色才能使圖中每條邊連接的2個頂點著不同顏色，則稱這個數m為該圖的色數。求一個圖的色數m的問題稱為圖的m可著色優化問題。解向量：(x1, x2, , xn)表示頂點i所著顏色xi 可行性約束函數：頂點i與已著色的相鄰頂點顏色不重復。復雜度分析圖m可著色問題的解空間樹中內結

35、點個數是對于每一個內結點，在最壞情況下，用ok檢查當前擴展結點的每一個兒子所相應的顏色可用性需耗時O(mn)。因此，回溯法總的時間耗費是 連續郵資問題假設國家發行了n種不同面值的郵票，并且規定每張信封上最多只允許貼m張郵票。連續郵資問題要求對于給定的n和m的值，給出郵票面值的最佳設計，在1張信封上可貼出從郵資1開始，增量為1的最大連續郵資區間。例如，當n=5和m=4時，面值為(1,3,11,15,32)的5種郵票可以貼出郵資的最大連續郵資區間是1到70。 解向量：用n元組x1:n表示n種不同的郵票面值，并約定它們從小到大排列。x1=1是唯一的選擇。 可行性約束函數：已選定x1:i-1，最大連續

36、郵資區間是1:r，接下來xi的可取值范圍是xi-1+1:r+1。回溯法效率分析通過前面具體實例的討論容易看出，回溯算法的效率在很大程度上依賴于以下因素：(1)產生xk的時間；(2)滿足顯約束的xk值的個數；(3)計算約束函數constraint的時間；(4)計算上界函數bound的時間；(5)滿足約束函數和上界函數約束的所有xk的個數。好的約束函數能顯著地減少所生成的結點數。但這樣的約束函數往往計算量較大。因此，在選擇約束函數時通常存在生成結點數與約束函數計算量之間的折衷。分支限界法分支限界法與回溯法（1）求解目標：回溯法的求解目標是找出解空間樹中滿足約束條件的所有解，而分支限界法的求解目標則

37、是找出滿足約束條件的一個解，或是在滿足約束條件的解中找出在某種意義下的最優解。 （2）搜索方式的不同：回溯法以深度優先的方式搜索解空間樹，而分支限界法則以廣度優先或以最小耗費優先的方式搜索解空間樹。 分支限界法常以廣度優先或以最小耗費（最大效益）優先的方式搜索問題的解空間樹。 在分支限界法中，每一個活結點只有一次機會成為擴展結點。活結點一旦成為擴展結點，就一次性產生其所有兒子結點。在這些兒子結點中，導致不可行解或導致非最優解的兒子結點被舍棄，其余兒子結點被加入活結點表中。此后，從活結點表中取下一結點成為當前擴展結點，并重復上述結點擴展過程。這個過程一直持續到找到所需的解或活結點表為空時為止。 常見的兩種分支限界法：（1）隊列式(FIFO)分支限界法： 按照隊列先進先出（FIFO）原則選取下一個節點為擴展節點。 （2）優先隊列式分支限界法： 按照優先隊列中規定的優