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

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

2、件與遞歸方程是遞歸函數(shù)的二個(gè)要素2.Fibonacci數(shù)列無(wú)窮數(shù)列1，1，2，3，5，8，13，21，34，55，稱為Fibonacci數(shù)列。它可以遞歸地定義為：當(dāng)一個(gè)函數(shù)及它的一個(gè)變量是由函數(shù)自身定義時(shí)，稱這個(gè)函數(shù)是雙遞歸函數(shù)。Ackerman函數(shù)A(n，m)定義如下：Ackerman函數(shù)A(n，m)的自變量m的每一個(gè)值都定義了一個(gè)單變量函數(shù)：M=0時(shí)，A(n,0)=n+2M=1時(shí)，A(n,1)=A(A(n-1,1),0)=A(n-1,1)+2，和A(1,1)=2故A(n,1)=2*nM=2時(shí)，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時(shí)，類似的可以推出M=4時(shí)，A(n,4)的增長(zhǎng)速度非?？?，以至于沒有適當(dāng)?shù)臄?shù)學(xué)式子來(lái)表示這一函數(shù)。定義單變量的Ackerman函數(shù)A(n)為，A(n)=A(n，n)。定義其擬逆函數(shù)(n)為：(n)=minkA(k)n。即(n)是使nA(k)成立的最小的k值。(n)在復(fù)雜度分析中常遇到。對(duì)于通常所見到的正整數(shù)n，有(n)4。但在理論上(n)沒有上界，隨著n的增加，它以難以想象的慢速度趨向正無(wú)窮大。6排列問(wèn)題設(shè)計(jì)一個(gè)遞歸算法生成n個(gè)元素r1,r2,rn的全排列。設(shè)R=r1,r2,rn是要進(jìn)行排列的n個(gè)元素，Ri=R-ri。集合X中元素的全排列記

4、為perm(X)。(ri)perm(X)表示在全排列perm(X)的每一個(gè)排列前加上前綴得到的排列。R的全排列可歸納定義如下： 當(dāng)n=1時(shí)，perm(R)=(r)，其中r是集合R中唯一的元素；當(dāng)n>1時(shí)，perm(R)由(r1)perm(R1)，(r2)perm(R2)，(rn)perm(Rn)構(gòu)成。 7整數(shù)劃分問(wèn)題在本例中，如果設(shè)p(n)為正整數(shù)n的劃分?jǐn)?shù)，則難以找到遞歸關(guān)系，因此考慮增加一個(gè)自變量：將最大加數(shù)n1不大于m的劃分個(gè)數(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塔問(wèn)題 設(shè)a,b,c是3個(gè)塔座。開始時(shí)，在塔座a上有一疊共n個(gè)圓盤，這些圓盤自下而上，由大到小地疊在一起。各圓盤從小到大編號(hào)為1,2,n,現(xiàn)要求將塔座a上的這一疊圓盤移到塔座b上，并仍按同樣順序疊置。在移動(dòng)圓盤時(shí)應(yīng)遵守以下移動(dòng)規(guī)則：規(guī)則1：每次只能移動(dòng)1個(gè)圓盤；規(guī)則2：任何時(shí)刻都不允許將較大的圓盤壓在較小的圓盤之上；規(guī)則3：在滿足移動(dòng)規(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)點(diǎn)：結(jié)構(gòu)清晰，可讀性強(qiáng)，而且容易用數(shù)學(xué)歸納法來(lái)證明算法的正確性，因此它為設(shè)計(jì)算法、調(diào)試程序帶來(lái)很大方便。缺點(diǎn)：遞歸算法的運(yùn)行效率較低，無(wú)論是耗費(fèi)的計(jì)算時(shí)間還是占用的存儲(chǔ)空間都比非遞歸算法要多。分治法的適用條件分治法所能解決的問(wèn)題一般具有以下幾個(gè)特征：1.該問(wèn)題的規(guī)模縮小到一定的程度就可以容易地解決；2.該問(wèn)題可以分解為若干個(gè)規(guī)模較小的相同問(wèn)題，即該問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)3.利用該問(wèn)題

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

8、元素x。二分搜索算法：public static int binarySearch(int a, int x, int n) / 在 a0 <= a1 <= . <= an-1 中搜索 x / 找到x時(shí)返回其在數(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)運(yùn)算需要O(1) 時(shí)間，因此整個(gè)算法在最壞情況下的計(jì)算時(shí)間復(fù)雜性為O(logn) 。合并排序：基本思想：將待排序元素分成大小大致相同的2個(gè)子集合，分別對(duì)2個(gè)子集合進(jìn)行排序，最終將排好序的子集合合并成為所要求的排好序的集合。 最壞時(shí)間復(fù)雜度：O(nlogn) 平均時(shí)間復(fù)雜度：O(nlogn) 輔助空間：O(n)快速排序:最壞時(shí)間復(fù)雜度：O(n2) 平均時(shí)間復(fù)雜度：O(nlogn) 輔助空間：

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

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

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

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

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

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

16、確定第段的所有頂點(diǎn)到達(dá)收點(diǎn)的花費(fèi)最小的通路。第二階段，用第一階段的信息，確定第段的所有頂點(diǎn)到達(dá)收點(diǎn)的花費(fèi)最小的通路。如此依次進(jìn)行，直到最后確定源點(diǎn)到達(dá)收點(diǎn)的花費(fèi)最小的通路。最后，從源點(diǎn)的信息中，確定它的前方頂點(diǎn)編號(hào)，從的信息中，確定的前方頂點(diǎn)編號(hào)，如此遞推，直到收點(diǎn)。動(dòng)態(tài)規(guī)劃函數(shù)：（）（）三、步驟：1. 對(duì)所有的，把初始化為最大值，初始化為-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所示的最短路徑問(wèn)題。圖6.3 動(dòng)態(tài)規(guī)劃方法求解多段圖的例子： ： ： ： ： ： ： ： ： 最后，

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

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

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

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

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

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

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

24、到頂點(diǎn)的最短路徑中的前一頂點(diǎn)1. 置，；2. ，若，則，；否則，；3. 尋找，使得，則；就是到的距離；4. ，；5. 若，算法結(jié)束；否則，轉(zhuǎn)6；6. 對(duì)與相鄰接的所有頂點(diǎn)，如果，直接轉(zhuǎn)3；否則，令，轉(zhuǎn)3；例5.3 在圖5.3的有向賦權(quán)圖中，求頂點(diǎn)到其它所有頂點(diǎn)的距離。如果用鄰接表來(lái)存放頂點(diǎn)之間的距離，則鄰接表如圖5.4所示。圖5.3 頂點(diǎn)a到其它所有頂點(diǎn)的最短距離的有向賦權(quán)圖圖5.4 圖5.3中所表示的賦權(quán)圖的鄰接表表5.1表示對(duì)上面的有向賦權(quán)圖，執(zhí)行狄斯奎諾算法時(shí)，每一輪循環(huán)的執(zhí)行過(guò)程。從頂點(diǎn)到其它所有頂點(diǎn)的路徑，如圖5.5所示。 表5.1 狄斯奎諾算法的執(zhí)行過(guò)程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 各個(gè)頂點(diǎn)到頂點(diǎn)a的路徑最小生成樹 設(shè)G =(V,E)是無(wú)向連通帶權(quán)圖，即一個(gè)網(wǎng)絡(luò)。E中每條邊(v,w)的權(quán)為cvw。如果G的子圖G是一棵包含G的所有頂點(diǎn)的樹，則稱G為G的生成樹。生成樹上各邊權(quán)的總和稱為該生成樹的耗費(fèi)。在G的所有生成樹中，耗費(fèi)最小的生成樹稱為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)為其中一條邊。這個(gè)性質(zhì)有時(shí)也稱為MST性質(zhì)。 普里姆（Prim）算法頂點(diǎn)集為，與頂點(diǎn),相關(guān)聯(lián)的邊為，權(quán)用表示，是最小花費(fèi)生成樹的邊集。維護(hù)兩個(gè)頂點(diǎn)集合和，開始時(shí)：令，。選取,，并且最小的和；，。重復(fù)上述步驟，直到為空，或找到條邊為止。步驟：1，；2. 如果為空，算法結(jié)束；否則，轉(zhuǎn)3；3. 尋找使,，并且最小的和；4. ，；轉(zhuǎn)2；圖5.9 普里姆算法的工作過(guò)程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最小的邊，將頂點(diǎn)j添加到S中。這個(gè)過(guò)程一直進(jìn)行到S=V時(shí)為止。在這個(gè)過(guò)程中選取到的所有邊恰好構(gòu)成G的一棵最小生成樹。 在上述Prim算法中，還應(yīng)當(dāng)考慮如何有效地找出滿足條件iÎS,jÎV-S，且權(quán)cij最小的邊(i,j)。實(shí)現(xiàn)這個(gè)目的的較簡(jiǎn)單的辦法是設(shè)置2個(gè)數(shù)組closest和lowcost。在Prim算法執(zhí)行過(guò)程中，先找出V-S中使lowcost值最小的頂點(diǎn)j，然后根據(jù)數(shù)組closest選取邊(j,closestj)，最后將j添加到S中，并對(duì)closest和lowcost作必要的修改。用這

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

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

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

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

32、子集樹需O(2n)計(jì)算時(shí)間 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!)計(jì)算時(shí)間 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); 裝載問(wèn)題有一批共n個(gè)集裝箱要裝上2艘載重量分別為c

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

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

35、點(diǎn)個(gè)數(shù)是對(duì)于每一個(gè)內(nèi)結(jié)點(diǎn)，在最壞情況下，用ok檢查當(dāng)前擴(kuò)展結(jié)點(diǎn)的每一個(gè)兒子所相應(yīng)的顏色可用性需耗時(shí)O(mn)。因此，回溯法總的時(shí)間耗費(fèi)是 連續(xù)郵資問(wèn)題假設(shè)國(guó)家發(fā)行了n種不同面值的郵票，并且規(guī)定每張信封上最多只允許貼m張郵票。連續(xù)郵資問(wèn)題要求對(duì)于給定的n和m的值，給出郵票面值的最佳設(shè)計(jì)，在1張信封上可貼出從郵資1開始，增量為1的最大連續(xù)郵資區(qū)間。例如，當(dāng)n=5和m=4時(shí)，面值為(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，接下來(lái)xi的可取值范圍是xi-1+1:r+1?；厮莘ㄐ史治鐾ㄟ^(guò)前面具體實(shí)例的討論容易看出，回溯算法的效率在很大程度上依賴于以下因素：(1)產(chǎn)生xk的時(shí)間；(2)滿足顯約束的xk值的個(gè)數(shù)；(3)計(jì)算約束函數(shù)constraint的時(shí)間；(4)計(jì)算上界函數(shù)bound的時(shí)間；(5)滿足約束函數(shù)和上界函數(shù)約束的所有xk的個(gè)數(shù)。好的約束函數(shù)能顯著地減少所生成的結(jié)點(diǎn)數(shù)。但這樣的約束函數(shù)往往計(jì)算量較大。因此，在選擇約束函數(shù)時(shí)通常存在生成結(jié)點(diǎn)數(shù)與約束函數(shù)計(jì)算量之間的折衷。分支限界法分支限界法與回溯法（1）求解目標(biāo)：回溯法的求解目標(biāo)是找出解空間樹中滿足約束條件的所有解，而分支限界法的求解目標(biāo)則

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