計算機算法分析與設(shè)計

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

2、件與遞歸方程是遞歸函數(shù)的二個要素2.Fibonacci數(shù)列無窮數(shù)列1，1，2，3，5，8，13，21，34，55，稱為Fibonacci數(shù)列。它可以遞歸地定義為：當一個函數(shù)及它的一個變量是由函數(shù)自身定義時，稱這個函數(shù)是雙遞歸函數(shù)。Ackerman函數(shù)A(n，m)定義如下：Ackerman函數(shù)A(n，m)的自變量m的每一個值都定義了一個單變量函數(shù)：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)的增長速度非?？?，以至于沒有適當?shù)臄?shù)學(xué)式子來表示這一函數(shù)。定義單變量的Ackerman函數(shù)A(n)為，A(n)=A(n，n)。定義其擬逆函數(shù)(n)為：(n)=minkA(k)n。即(n)是使nA(k)成立的最小的k值。(n)在復(fù)雜度分析中常遇到。對于通常所見到的正整數(shù)n，有(n)4。但在理論上(n)沒有上界，隨著n的增加，它以難以想象的慢速度趨向正無窮大。6排列問題設(shè)計一個遞歸算法生成n個元素r1,r2,rn的全排列。設(shè)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)構(gòu)成。 7整數(shù)劃分問題在本例中，如果設(shè)p(n)為正整數(shù)n的劃分數(shù)，則難以找到遞歸關(guān)系，因此考慮增加一個自變量：將最大加數(shù)n1不大于m的劃分個數(shù)記作q(n,m)?？梢越(n,m)的如下遞歸關(guān)系。(3) q(n,n)=1+q(n,n-1);正整數(shù)n的劃分由n1=n的劃分和n1n-1的劃分組成。(4

5、) q(n,m)=q(n,m-1)+q(n-m,m),n>m>1;正整數(shù)n的最大加數(shù)n1不大于m的劃分由n1=m的劃分和n1n-1 的劃分組成。8.Hanoi塔問題 設(shè)a,b,c是3個塔座。開始時，在塔座a上有一疊共n個圓盤，這些圓盤自下而上，由大到小地疊在一起。各圓盤從小到大編號為1,2,n,現(xiàn)要求將塔座a上的這一疊圓盤移到塔座b上，并仍按同樣順序疊置。在移動圓盤時應(yīng)遵守以下移動規(guī)則：規(guī)則1：每次只能移動1個圓盤；規(guī)則2：任何時刻都不允許將較大的圓盤壓在較小的圓盤之上；規(guī)則3：在滿足移動規(guī)則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); 遞歸小結(jié):優(yōu)點：結(jié)構(gòu)清晰，可讀性強，而且容易用數(shù)學(xué)歸納法來證明算法的正確性，因此它為設(shè)計算法、調(diào)試程序帶來很大方便。缺點：遞歸算法的運行效率較低，無論是耗費的計算時間還是占用的存儲空間都比非遞歸算法要多。分治法的適用條件分治法所能解決的問題一般具有以下幾個特征：1.該問題的規(guī)?？s小到一定的程度就可以容易地解決；2.該問題可以分解為若干個規(guī)模較小的相同問題，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)3.利用該問題

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

8、元素x。二分搜索算法：public static int binarySearch(int a, int x, int n) / 在 a0 <= a1 <= . <= an-1 中搜索 x / 找到x時返回其在數(shù)組中的位置，否則返回-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 算法復(fù)雜度分析：每執(zhí)行一次算法的while循環(huán)， 待搜索數(shù)組的大小減少一半。因此，在最壞情況下，while循環(huán)被執(zhí)行了O(logn) 次。循環(huán)體內(nèi)運算需要O(1) 時間，因此整個算法在最壞情況下的計算時間復(fù)雜性為O(logn) 。合并排序：基本思想：將待排序元素分成大小大致相同的2個子集合，分別對2個子集合進行排序，最終將排好序的子集合合并成為所要求的排好序的集合。 最壞時間復(fù)雜度：O(nlogn) 平均時間復(fù)雜度：O(nlogn) 輔助空間：O(n)快速排序:最壞時間復(fù)雜度：O(n2) 平均時間復(fù)雜度：O(nlogn) 輔助空間：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

24、到頂點的最短路徑中的前一頂點1. 置，；2. ，若，則，；否則，；3. 尋找，使得，則；就是到的距離；4. ，；5. 若，算法結(jié)束；否則，轉(zhuǎn)6；6. 對與相鄰接的所有頂點，如果，直接轉(zhuǎn)3；否則，令，轉(zhuǎn)3；例5.3 在圖5.3的有向賦權(quán)圖中，求頂點到其它所有頂點的距離。如果用鄰接表來存放頂點之間的距離，則鄰接表如圖5.4所示。圖5.3 頂點a到其它所有頂點的最短距離的有向賦權(quán)圖圖5.4 圖5.3中所表示的賦權(quán)圖的鄰接表表5.1表示對上面的有向賦權(quán)圖，執(zhí)行狄斯奎諾算法時，每一輪循環(huán)的執(zhí)行過程。從頂點到其它所有頂點的路徑，如圖5.5所示。 表5.1 狄斯奎諾算法的執(zhí)行過程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的路徑最小生成樹 設(shè)G =(V,E)是無向連通帶權(quán)圖，即一個網(wǎng)絡(luò)。E中每條邊(v,w)的權(quán)為cvw。如果G的子圖G是一棵包含G的所有頂點的樹，則稱G為G的生成樹。生成樹上各邊權(quán)的總和稱為該生成樹的耗費。在G的所有生成樹中，耗費最小的生成樹稱為G的最小生成樹。最小生成樹性質(zhì)：設(shè)G=(V,E)是連通帶權(quán)圖，U是V的真子集。如果(u,v)ÎE，且uÎU，vÎV

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

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

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

29、 按權(quán)的遞增順序查看等價于對優(yōu)先隊列執(zhí)行removeMin運算?？梢杂枚褜崿F(xiàn)這個優(yōu)先隊列。 對一個由連通分支組成的集合不斷進行修改，需要用到抽象數(shù)據(jù)類型并查集UnionFind所支持的基本運算。當圖的邊數(shù)為e時，Kruskal算法所需的計算時間是 。當 時，Kruskal算法比Prim算法差，但當 時，Kruskal算法卻比Prim算法好得多?；厮莘ㄟm用于解一些組合數(shù)相當大的問題。回溯法在問題的解空間樹中，按深度優(yōu)先策略，從根結(jié)點出發(fā)搜索解空間樹。算法搜索至解空間樹的任意一點時，先判斷該結(jié)點是否包含問題的解。如果肯定不包含，則跳過對該結(jié)點為根的子樹的搜索，逐層向其祖先結(jié)點回溯；否則，進入該子樹

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

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

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艘輪船。如果有，找出一種裝載方案。容易證明，如果一個給定裝載問題有解，則采用下面的策略可得到最優(yōu)裝載方案。(1)首先將第一艘輪船盡可能裝滿；(2)將剩余的集裝箱裝上第二艘輪船。將第一艘輪船盡可能裝滿等價于選取全體集裝箱的一個子集，使該子集中集裝箱重量之和最接近。由此可知，裝載問題等價于以下特殊的0-1背包問題。用回溯法設(shè)計解裝載問題的O(2n)計算時間算法。在某些情況下該算法優(yōu)于動態(tài)規(guī)劃算法。n后問題解向量：(x1, x2, , xn) 顯約束：xi=1,2, ,n隱約束：1)不同列：xi

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

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

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

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