1、.,1,中國(guó)計(jì)算機(jī)學(xué)會(huì)“21世紀(jì)大學(xué)本科計(jì)算機(jī)專業(yè)系列教材”算法設(shè)計(jì)與分析,王曉東編著,.,2,主要內(nèi)容介紹,第1章算法引論第2章遞歸與分治策略第3章動(dòng)態(tài)規(guī)劃第4章貪心算法第5章回溯法第6章分支限界法,.,3,主要內(nèi)容介紹（續(xù)）,第7章概率算法第8章NP完全性理論第9章近似算法第10章算法優(yōu)化策略,.,4,第1章算法引論,1.1算法與程序1.2表達(dá)算法的抽象機(jī)制1.3描述算法1.4算法復(fù)雜性分析,本章主要知識(shí)點(diǎn)：,.,5,1.1算法與程序,輸入：有零個(gè)或多個(gè)外部量作為算法的輸入。輸出：算法產(chǎn)生至少一個(gè)量作為輸出。確定性：組成算法的每條指令清晰、無(wú)歧義。有限性：算法中每條指令的執(zhí)行次數(shù)有限，執(zhí)行

2、每條指令的時(shí)間也有限。,是算法用某種程序設(shè)計(jì)語(yǔ)言的具體實(shí)現(xiàn)。程序可以不滿足算法的性質(zhì)(4)即有限性。,是滿足下述性質(zhì)的指令序列。,算法：,程序：,.,6,1.從機(jī)器語(yǔ)言到高級(jí)語(yǔ)言的抽象,1.2表達(dá)算法的抽象機(jī)制,高級(jí)程序設(shè)計(jì)語(yǔ)言的主要好處是：,（4）把繁雜瑣碎的事務(wù)交給編譯程序，所以自動(dòng)化程度高，開發(fā)周期短，程序員可以集中時(shí)間和精力從事更重要的創(chuàng)造性勞動(dòng)，提高程序質(zhì)量。,（1）高級(jí)語(yǔ)言更接近算法語(yǔ)言，易學(xué)、易掌握，一般工程技術(shù)人員只需要幾周時(shí)間的培訓(xùn)就可以勝任程序員的工作；,（2）高級(jí)語(yǔ)言為程序員提供了結(jié)構(gòu)化程序設(shè)計(jì)的環(huán)境和工具，使得設(shè)計(jì)出來(lái)的程序可讀性好，可維護(hù)性強(qiáng)，可靠性高；,（3）高級(jí)語(yǔ)

3、言不依賴于機(jī)器語(yǔ)言，與具體的計(jì)算機(jī)硬件關(guān)系不大，因而所寫出來(lái)的程序可植性好、重用率高；,.,7,2.抽象數(shù)據(jù)類型,1.2表達(dá)算法的抽象機(jī)制,抽象數(shù)據(jù)類型是算法的一個(gè)數(shù)據(jù)模型連同定義在該模型上并作為算法構(gòu)件的一組運(yùn)算。,抽象數(shù)據(jù)類型帶給算法設(shè)計(jì)的好處有：,（1）算法頂層設(shè)計(jì)與底層實(shí)現(xiàn)分離；（2）算法設(shè)計(jì)與數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)隔開，允許數(shù)據(jù)結(jié)構(gòu)自由選擇；（3）數(shù)據(jù)模型和該模型上的運(yùn)算統(tǒng)一在ADT中，便于空間和時(shí)間耗費(fèi)的折衷；（4）用抽象數(shù)據(jù)類型表述的算法具有很好的可維護(hù)性；（5）算法自然呈現(xiàn)模塊化；（6）為自頂向下逐步求精和模塊化提供有效途徑和工具；（7）算法結(jié)構(gòu)清晰，層次分明，便于算法正確性的證明和復(fù)雜

4、性的分析。,.,8,在本書中，采用Java語(yǔ)言描述算法。1.Java程序結(jié)構(gòu),1.3描述算法,以下，對(duì)Java語(yǔ)言的若干重要特性作簡(jiǎn)要概述。,（1）Java程序的兩種類型：應(yīng)用程序和applet區(qū)別：應(yīng)用程序的主方法為main，其可在命令行中用命令語(yǔ)句java應(yīng)用程序名來(lái)執(zhí)行；applet的主方法為init，其必須嵌入HTML文件，由Web瀏覽器或applet閱讀器來(lái)執(zhí)行。,（2）包：java程序和類可以包(packages)的形式組織管理。,（3）import語(yǔ)句：在java程序中可用import語(yǔ)句加載所需的包。例如，importjava.io.*;語(yǔ)句加載java.io包。,.,9,1.

5、3描述算法,2.Java數(shù)據(jù)類型,Java對(duì)兩種數(shù)據(jù)類型的不同處理方式：,s=newString(“Welcome”);Strings=newString(“Welcome”);,.,10,1.3描述算法,表格1-1Java基本數(shù)據(jù)類型,.,11,1.3描述算法,3.方法,在Java中，執(zhí)行特定任務(wù)的函數(shù)或過(guò)程統(tǒng)稱為方法(methods)。例如，java的Math類給出的常見(jiàn)數(shù)學(xué)計(jì)算的方法如下表所示：,.,12,1.3描述算法,3.方法,計(jì)算表達(dá)式值的自定義方法ab描述如下：,publicstaticintab(inta,intb)return(a+b+Math.abs(a-b)/2;,（1）

6、方法參數(shù)：Java中所有方法的參數(shù)均為值參數(shù)。上述方法ab中，a和b是形式參數(shù)，在調(diào)用方法時(shí)通過(guò)實(shí)際參數(shù)賦值。,（2）方法重載：Java允許方法重載，即允許定義有不同簽名的同名方法。上述方法ab可重載為：,publicstaticdoubleab(doublea,doubleb)return(a+b+Math.abs(a-b)/2.0;,.,13,1.3描述算法,4.異常,Java的異常提供了一種處理錯(cuò)誤的方法。當(dāng)程序發(fā)現(xiàn)一個(gè)錯(cuò)誤，就引發(fā)一個(gè)異常，以便在合適地方捕獲異常并進(jìn)行處理。,通常用try塊來(lái)定義異常處理。每個(gè)異常處理由一個(gè)catch語(yǔ)句組成。,publicstaticvoidmain(

7、Stringargs)tryf();catch(exception1)異常處理;catch(exception2)異常處理;finallyfinally塊;,.,14,1.3描述算法,5.Java的類,(4)訪問(wèn)修飾,Java的類一般由4個(gè)部分組成：,(1)類名,(2)數(shù)據(jù)成員,(3)方法,.,15,1.3描述算法,6.通用方法,下面的方法swap用于交換一維整型數(shù)組a的位置i和位置j處的值。,publicstaticvoidswap(inta,inti,intj)inttemp=ai;ai=aj;aj=temp;,publicstaticvoidswap(objecta,inti,intj)

8、objecttemp=ai;ai=aj;aj=temp;,該方法只適用于整型數(shù)組,該方法具有通用性，適用于Object類型及其所有子類,以上方法修改如下：,.,16,1.3描述算法,6.通用方法,（1）Computable界面,publicstaticComputablesum(Computablea,intn)if(a.length=0)returnnull;Computablesum=(Computable)a0.zero();for(inti=0;im1;正整數(shù)n的最大加數(shù)n1不大于m的劃分由n1=m的劃分和n1n-1的劃分組成。,(3)q(n,n)=1+q(n,n-1);正整數(shù)n的劃分

9、由n1=n的劃分和n1n-1的劃分組成。,2.1遞歸的概念,例5整數(shù)劃分問(wèn)題前面的幾個(gè)例子中，問(wèn)題本身都具有比較明顯的遞歸關(guān)系，因而容易用遞歸函數(shù)直接求解。在本例中，如果設(shè)p(n)為正整數(shù)n的劃分?jǐn)?shù)，則難以找到遞歸關(guān)系，因此考慮增加一個(gè)自變量：將最大加數(shù)n1不大于m的劃分個(gè)數(shù)記作q(n,m)?？梢越(n,m)的如下遞歸關(guān)系。,.,39,2.1遞歸的概念,例5整數(shù)劃分問(wèn)題前面的幾個(gè)例子中，問(wèn)題本身都具有比較明顯的遞歸關(guān)系，因而容易用遞歸函數(shù)直接求解。在本例中，如果設(shè)p(n)為正整數(shù)n的劃分?jǐn)?shù)，則難以找到遞歸關(guān)系，因此考慮增加一個(gè)自變量：將最大加數(shù)n1不大于m的劃分個(gè)數(shù)記作q(n,m)?？梢越?/p>

10、立q(n,m)的如下遞歸關(guān)系。,正整數(shù)n的劃分?jǐn)?shù)p(n)=q(n,n)。,.,40,.,41,2.1遞歸的概念,例6Hanoi塔問(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中任一塔座上。,.,42,在問(wèn)題規(guī)模較大時(shí)，較難找到一般的方法，因此我們嘗試用遞歸技術(shù)來(lái)解決這個(gè)問(wèn)

11、題。,當(dāng)n=1時(shí)，問(wèn)題比較簡(jiǎn)單。此時(shí)，只要將編號(hào)為1的圓盤從塔座a直接移至塔座b上即可。當(dāng)n1時(shí)，需要利用塔座c作為輔助塔座。此時(shí)若能設(shè)法將n-1個(gè)較小的圓盤依照移動(dòng)規(guī)則從塔座a移至塔座c，然后，將剩下的最大圓盤從塔座a移至塔座b，最后，再設(shè)法將n-1個(gè)較小的圓盤依照移動(dòng)規(guī)則從塔座c移至塔座b。由此可見(jiàn)，n個(gè)圓盤的移動(dòng)問(wèn)題可分為2次n-1個(gè)圓盤的移動(dòng)問(wèn)題，這又可以遞歸地用上述方法來(lái)做。由此可以設(shè)計(jì)出解Hanoi塔問(wèn)題的遞歸算法如下。,2.1遞歸的概念,例6Hanoi塔問(wèn)題,publicstaticvoidhanoi(intn,inta,intb,intc)if(n0)hanoi(n-1,a,c

12、,b);move(a,b);hanoi(n-1,c,b,a);,思考題：如果塔的個(gè)數(shù)變?yōu)閍,b,c,d四個(gè)，現(xiàn)要將n個(gè)圓盤從a全部移動(dòng)到d，移動(dòng)規(guī)則不變，求移動(dòng)步數(shù)最小的方案。,.,43,遞歸小結(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ǔ)空間都比非遞歸算法要多。,.,44,遞歸小結(jié),解決方法：在遞歸算法中消除遞歸調(diào)用，使其轉(zhuǎn)化為非遞歸算法。1.采用一個(gè)用戶定義的棧來(lái)模擬系統(tǒng)的遞歸調(diào)用工作棧。該方法通用性強(qiáng)，但本質(zhì)上還是遞歸，只不過(guò)人工做了本來(lái)由編譯器做的事情，優(yōu)化效

13、果不明顯。2.用遞推來(lái)實(shí)現(xiàn)遞歸函數(shù)。3.通過(guò)Cooper變換、反演變換能將一些遞歸轉(zhuǎn)化為尾遞歸，從而迭代求出結(jié)果。后兩種方法在時(shí)空復(fù)雜度上均有較大改善，但其適用范圍有限。,.,45,分治法的適用條件,分治法所能解決的問(wèn)題一般具有以下幾個(gè)特征：該問(wèn)題的規(guī)模縮小到一定的程度就可以容易地解決；該問(wèn)題可以分解為若干個(gè)規(guī)模較小的相同問(wèn)題，即該問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)利用該問(wèn)題分解出的子問(wèn)題的解可以合并為該問(wèn)題的解；該問(wèn)題所分解出的各個(gè)子問(wèn)題是相互獨(dú)立的，即子問(wèn)題之間不包含公共的子問(wèn)題。,因?yàn)閱?wèn)題的計(jì)算復(fù)雜性一般是隨著問(wèn)題規(guī)模的增加而增加，因此大部分問(wèn)題滿足這個(gè)特征。,這條特征是應(yīng)用分治法的前提，它也是大多

14、數(shù)問(wèn)題可以滿足的，此特征反映了遞歸思想的應(yīng)用,能否利用分治法完全取決于問(wèn)題是否具有這條特征，如果具備了前兩條特征，而不具備第三條特征，則可以考慮貪心算法或動(dòng)態(tài)規(guī)劃。,這條特征涉及到分治法的效率，如果各子問(wèn)題是不獨(dú)立的，則分治法要做許多不必要的工作，重復(fù)地解公共的子問(wèn)題，此時(shí)雖然也可用分治法，但一般用動(dòng)態(tài)規(guī)劃較好。,.,46,分治法的基本步驟,divide-and-conquer(P)if(|P|=n0)adhoc(P);/解決小規(guī)模的問(wèn)題dividePintosmallersubinstancesP1,P2,.,Pk；/分解問(wèn)題for(i=1,i=k,i+)yi=divide-and-conq

15、uer(Pi);/遞歸的解各子問(wèn)題returnmerge(y1,.,yk);/將各子問(wèn)題的解合并為原問(wèn)題的解人們從大量實(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ī)模不等的做法要好。,.,47,分治法的復(fù)雜性分析,一個(gè)分治法將規(guī)模為n的問(wèn)題分成k個(gè)規(guī)模為nm的子問(wèn)題去解。設(shè)分解閥值n0=1，且adhoc解規(guī)模為1的問(wèn)題耗費(fèi)1個(gè)單位時(shí)間。再設(shè)將原問(wèn)題分解為k個(gè)子問(wèn)題以及用merge將k個(gè)子問(wèn)題的解合并為原問(wèn)題的解需用f(n

16、)個(gè)單位時(shí)間。用T(n)表示該分治法解規(guī)模為|P|=n的問(wèn)題所需的計(jì)算時(shí)間，則有：,通過(guò)迭代法求得方程的解：,注意：遞歸方程及其解只給出n等于m的方冪時(shí)T(n)的值，但是如果認(rèn)為T(n)足夠平滑，那么由n等于m的方冪時(shí)T(n)的值可以估計(jì)T(n)的增長(zhǎng)速度。通常假定T(n)是單調(diào)上升的，從而當(dāng)min=tr+s,復(fù)雜度分析T(n)=O(4k)漸進(jìn)意義下的最優(yōu)算法,.,60,合并排序,基本思想：將待排序元素分成大小大致相同的2個(gè)子集合，分別對(duì)2個(gè)子集合進(jìn)行排序，最終將排好序的子集合合并成為所要求的排好序的集合。,publicstaticvoidmergeSort(Comparablea,intle

17、ft,intright)if(left=j)break;MyMath.swap(a,i,j);ap=aj;aj=x;returnj;,初始序列,j-;,5,7,5,2,6,8,i+;,5,6,5,2,7,8,j-;,5,2,5,6,7,8,i+;,完成,5,2,567,8,.,65,privatestaticintrandomizedPartition(intp,intr)inti=random(p,r);MyMath.swap(a,i,p);returnpartition(p,r);,快速排序,快速排序算法的性能取決于劃分的對(duì)稱性。通過(guò)修改算法partition，可以設(shè)計(jì)出采用隨機(jī)選擇策略的

18、快速排序算法。在快速排序算法的每一步中，當(dāng)數(shù)組還沒(méi)有被劃分時(shí)，可以在ap:r中隨機(jī)選出一個(gè)元素作為劃分基準(zhǔn)，這樣可以使劃分基準(zhǔn)的選擇是隨機(jī)的，從而可以期望劃分是較對(duì)稱的。,最壞時(shí)間復(fù)雜度：O(n2)平均時(shí)間復(fù)雜度：O(nlogn)輔助空間：O(n)或O(logn)穩(wěn)定性：不穩(wěn)定,.,66,線性時(shí)間選擇,給定線性序集中n個(gè)元素和一個(gè)整數(shù)k，1kn，要求找出這n個(gè)元素中第k小的元素,privatestaticComparablerandomizedSelect(intp,intr,intk)if(p=r)returnap;inti=randomizedpartition(p,r),j=i-p+1;

19、if(k=j)returnrandomizedSelect(p,i,k);elsereturnrandomizedSelect(i+1,r,k-j);,在最壞情況下，算法randomizedSelect需要O(n2)計(jì)算時(shí)間但可以證明，算法randomizedSelect可以在O(n)平均時(shí)間內(nèi)找出n個(gè)輸入元素中的第k小元素。,.,67,線性時(shí)間選擇,如果能在線性時(shí)間內(nèi)找到一個(gè)劃分基準(zhǔn)，使得按這個(gè)基準(zhǔn)所劃分出的2個(gè)子數(shù)組的長(zhǎng)度都至少為原數(shù)組長(zhǎng)度的倍(01是某個(gè)正常數(shù))，那么就可以在最壞情況下用O(n)時(shí)間完成選擇任務(wù)。,例如，若=9/10，算法遞歸調(diào)用所產(chǎn)生的子數(shù)組的長(zhǎng)度至少縮短1/10。所以

20、，在最壞情況下，算法所需的計(jì)算時(shí)間T(n)滿足遞歸式T(n)T(9n/10)+O(n)。由此可得T(n)=O(n)。,.,68,將n個(gè)輸入元素劃分成n/5個(gè)組，每組5個(gè)元素，只可能有一個(gè)組不是5個(gè)元素。用任意一種排序算法，將每組中的元素排好序，并取出每組的中位數(shù)，共n/5個(gè)。遞歸調(diào)用select來(lái)找出這n/5個(gè)元素的中位數(shù)。如果n/5是偶數(shù)，就找它的2個(gè)中位數(shù)中較大的一個(gè)。以這個(gè)元素作為劃分基準(zhǔn)。,線性時(shí)間選擇,設(shè)所有元素互不相同。在這種情況下，找出的基準(zhǔn)x至少比3(n-5)/10個(gè)元素大，因?yàn)樵诿恳唤M中有2個(gè)元素小于本組的中位數(shù)，而n/5個(gè)中位數(shù)中又有(n-5)/10個(gè)小于基準(zhǔn)x。同理，基準(zhǔn)

21、x也至少比3(n-5)/10個(gè)元素小。而當(dāng)n75時(shí)，3(n-5)/10n/4所以按此基準(zhǔn)劃分所得的2個(gè)子數(shù)組的長(zhǎng)度都至少縮短1/4。,.,69,privatestaticComparableselect(intp,intr,intk)if(r-p5)/用某個(gè)簡(jiǎn)單排序算法對(duì)數(shù)組ap:r排序;bubbleSort(p,r);returnap+k-1;/將ap+5*i至ap+5*i+4的第3小元素/與ap+i交換位置;/找中位數(shù)的中位數(shù)，r-p-4即上面所說(shuō)的n-5for(inti=0;i=(r-p-4)/5;i+)ints=p+5*i,t=s+4;for(intj=0;j3;j+)bubble(s

22、,t-j);MyMath.swap(a,p+i,s+2);Comparablex=select(p,p+(r-p-4)/5,(r-p+6)/10);inti=partition(p,r,x),j=i-p+1;if(k=j)returnselect(p,i,k);elsereturnselect(i+1,r,k-j);,復(fù)雜度分析T(n)=O(n),上述算法將每一組的大小定為5，并選取75作為是否作遞歸調(diào)用的分界點(diǎn)。這2點(diǎn)保證了T(n)的遞歸式中2個(gè)自變量之和n/5+3n/4=19n/20=n，01。這是使T(n)=O(n)的關(guān)鍵之處。當(dāng)然，除了5和75之外，還有其他選擇。,.,70,最接近點(diǎn)對(duì)

23、問(wèn)題,給定平面上n個(gè)點(diǎn)的集合S，找其中的一對(duì)點(diǎn)，使得在n個(gè)點(diǎn)組成的所有點(diǎn)對(duì)中，該點(diǎn)對(duì)間的距離最小。,.,71,最接近點(diǎn)對(duì)問(wèn)題,如果S的最接近點(diǎn)對(duì)是p3,q3，即|p3-q3|d，則p3和q3兩者與m的距離不超過(guò)d，即p3(m-d,m，q3(m,m+d。由于在S1中，每個(gè)長(zhǎng)度為d的半閉區(qū)間至多包含一個(gè)點(diǎn)（否則必有兩點(diǎn)距離小于d），并且m是S1和S2的分割點(diǎn)，因此(m-d,m中至多包含S中的一個(gè)點(diǎn)。由圖可以看出，如果(m-d,m中有S中的點(diǎn)，則此點(diǎn)就是S1中最大點(diǎn)。因此，我們用線性時(shí)間就能找到區(qū)間(m-d,m和(m,m+d中所有點(diǎn)，即p3和q3。從而我們用線性時(shí)間就可以將S1的解和S2的解合并成為

24、S的解。,能否在線性時(shí)間內(nèi)找到p3,q3？,.,72,最接近點(diǎn)對(duì)問(wèn)題,下面來(lái)考慮二維的情形。,選取一垂直線l:x=m來(lái)作為分割直線。其中m為S中各點(diǎn)x坐標(biāo)的中位數(shù)。由此將S分割為S1和S2。遞歸地在S1和S2上找出其最小距離d1和d2，并設(shè)d=mind1,d2，S中的最接近點(diǎn)對(duì)或者是d，或者是某個(gè)p,q，其中pP1且qP2。能否在線性時(shí)間內(nèi)找到p,q？,.,73,最接近點(diǎn)對(duì)問(wèn)題,考慮P1中任意一點(diǎn)p，它若與P2中的點(diǎn)q構(gòu)成最接近點(diǎn)對(duì)的候選者，則必有distance(p，q)d。滿足這個(gè)條件的P2中的點(diǎn)一定落在一個(gè)d2d的矩形R中由d的意義可知，P2中任何2個(gè)S中的點(diǎn)的距離都不小于d。由此可以推

25、出矩形R中最多只有6個(gè)S中的點(diǎn)。因此，在分治法的合并步驟中最多只需要檢查6n/2=3n個(gè)候選者,能否在線性時(shí)間內(nèi)找到p3,q3？,證明:將矩形R的長(zhǎng)為2d的邊3等分，將它的長(zhǎng)為d的邊2等分，由此導(dǎo)出6個(gè)(d/2)(2d/3)的矩形。若矩形R中有多于6個(gè)S中的點(diǎn)，則由鴿舍原理易知至少有一個(gè)(d/2)(2d/3)的小矩形中有2個(gè)以上S中的點(diǎn)。設(shè)u，v是位于同一小矩形中的2個(gè)點(diǎn)，則distance(u,v)d。這與d的意義相矛盾。,.,74,為了確切地知道要檢查哪6個(gè)點(diǎn)，可以將p和P2中所有S2的點(diǎn)投影到垂直線l上。由于能與p點(diǎn)一起構(gòu)成最接近點(diǎn)對(duì)候選者的S2中點(diǎn)一定在矩形R中，所以它們?cè)谥本€l上的投

26、影點(diǎn)距p在l上投影點(diǎn)的距離小于d。由上面的分析可知，這種投影點(diǎn)最多只有6個(gè)。因此，若將P1和P2中所有S中點(diǎn)按其y坐標(biāo)排好序，則對(duì)P1中所有點(diǎn)，對(duì)排好序的點(diǎn)列作一次掃描，就可以找出所有最接近點(diǎn)對(duì)的候選者。對(duì)P1中每一點(diǎn)最多只要檢查P2中排好序的相繼6個(gè)點(diǎn)。,最接近點(diǎn)對(duì)問(wèn)題,.,75,最接近點(diǎn)對(duì)問(wèn)題,publicstaticdoublecpair2(S)n=|S|;if(nm2.d1=cpair2(S1);d2=cpair2(S2);3.dm=min(d1,d2);,4.設(shè)P1是S1中距垂直分割線l的距離在dm之內(nèi)的所有點(diǎn)組成的集合；P2是S2中距分割線l的距離在dm之內(nèi)所有點(diǎn)組成的集合；將P1

27、和P2中點(diǎn)依其y坐標(biāo)值排序；并設(shè)X和Y是相應(yīng)的已排好序的點(diǎn)列；5.通過(guò)掃描X以及對(duì)于X中每個(gè)點(diǎn)檢查Y中與其距離在dm之內(nèi)的所有點(diǎn)(最多6個(gè))可以完成合并；當(dāng)X中的掃描指針逐次向上移動(dòng)時(shí)，Y中的掃描指針可在寬為2dm的區(qū)間內(nèi)移動(dòng)；設(shè)dl是按這種掃描方式找到的點(diǎn)對(duì)間的最小距離；6.d=min(dm,dl);returnd;,復(fù)雜度分析T(n)=O(nlogn),.,76,設(shè)計(jì)一個(gè)滿足以下要求的比賽日程表：(1)每個(gè)選手必須與其他n-1個(gè)選手各賽一次；(2)每個(gè)選手一天只能賽一次；(3)循環(huán)賽一共進(jìn)行n-1天。,按分治策略，將所有的選手分為兩半，n個(gè)選手的比賽日程表就可以通過(guò)為n/2個(gè)選手設(shè)計(jì)的比賽

28、日程表來(lái)決定。遞歸地用對(duì)選手進(jìn)行分割，直到只剩下2個(gè)選手時(shí)，比賽日程表的制定就變得很簡(jiǎn)單。這時(shí)只要讓這2個(gè)選手進(jìn)行比賽就可以了。,.,77,循環(huán)賽日程表,設(shè)計(jì)一個(gè)滿足以下要求的比賽日程表：(1)每個(gè)選手必須與其他n-1個(gè)選手各賽一次；(2)每個(gè)選手一天只能賽一次；(3)循環(huán)賽一共進(jìn)行n-1天。,按分治策略，將所有的選手分為兩半，n個(gè)選手的比賽日程表就可以通過(guò)為n/2個(gè)選手設(shè)計(jì)的比賽日程表來(lái)決定。遞歸地用對(duì)選手進(jìn)行分割，直到只剩下2個(gè)選手時(shí)，比賽日程表的制定就變得很簡(jiǎn)單。這時(shí)只要讓這2個(gè)選手進(jìn)行比賽就可以了。,.,78,第3章動(dòng)態(tài)規(guī)劃,.,79,動(dòng)態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問(wèn)

29、題分解成若干個(gè)子問(wèn)題,.,80,算法總體思想,動(dòng)態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問(wèn)題分解成若干個(gè)子問(wèn)題,.,81,但是經(jīng)分解得到的子問(wèn)題往往不是互相獨(dú)立的。不同子問(wèn)題的數(shù)目常常只有多項(xiàng)式量級(jí)。在用分治法求解時(shí)，有些子問(wèn)題被重復(fù)計(jì)算了許多次。,算法總體思想,.,82,如果能夠保存已解決的子問(wèn)題的答案，而在需要時(shí)再找出已求得的答案，就可以避免大量重復(fù)計(jì)算，從而得到多項(xiàng)式時(shí)間算法。,算法總體思想,T(n),Thosewhocannotrememberthepastaredoomedtorepeatit.-GeorgeSantayana,ThelifeofReason,BookI:Int

30、roductionandReasoninCommonSense(1905),.,83,動(dòng)態(tài)規(guī)劃基本步驟,找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。遞歸地定義最優(yōu)值。以自底向上的方式計(jì)算出最優(yōu)值。根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解。,.,84,完全加括號(hào)的矩陣連乘積,（1）單個(gè)矩陣是完全加括號(hào)的；（2）矩陣連乘積是完全加括號(hào)的，則可表示為2個(gè)完全加括號(hào)的矩陣連乘積和的乘積并加括號(hào)，即,16000,10500,36000,87500,34500,完全加括號(hào)的矩陣連乘積可遞歸地定義為：設(shè)有四個(gè)矩陣，它們的維數(shù)分別是：總共有五中完全加括號(hào)的方式,.,85,矩陣連乘問(wèn)題,給定n個(gè)矩陣，其中與是可乘的，。考

31、察這n個(gè)矩陣的連乘積由于矩陣乘法滿足結(jié)合律，所以計(jì)算矩陣的連乘可以有許多不同的計(jì)算次序。這種計(jì)算次序可以用加括號(hào)的方式來(lái)確定。若一個(gè)矩陣連乘積的計(jì)算次序完全確定，也就是說(shuō)該連乘積已完全加括號(hào)，則可以依此次序反復(fù)調(diào)用2個(gè)矩陣相乘的標(biāo)準(zhǔn)算法計(jì)算出矩陣連乘積,.,86,矩陣連乘問(wèn)題,給定n個(gè)矩陣A1,A2,An，其中Ai與Ai+1是可乘的，i=1,2,n-1。如何確定計(jì)算矩陣連乘積的計(jì)算次序，使得依此次序計(jì)算矩陣連乘積需要的數(shù)乘次數(shù)最少。,窮舉法：列舉出所有可能的計(jì)算次序，并計(jì)算出每一種計(jì)算次序相應(yīng)需要的數(shù)乘次數(shù)，從中找出一種數(shù)乘次數(shù)最少的計(jì)算次序。,算法復(fù)雜度分析：對(duì)于n個(gè)矩陣的連乘積，設(shè)其不同的

32、計(jì)算次序?yàn)镻(n)。由于每種加括號(hào)方式都可以分解為兩個(gè)子矩陣的加括號(hào)問(wèn)題：(A1.Ak)(Ak+1An)可以得到關(guān)于P(n)的遞推式如下：,.,87,矩陣連乘問(wèn)題,窮舉法動(dòng)態(tài)規(guī)劃,將矩陣連乘積簡(jiǎn)記為Ai:j，這里ij,考察計(jì)算Ai:j的最優(yōu)計(jì)算次序。設(shè)這個(gè)計(jì)算次序在矩陣Ak和Ak+1之間將矩陣鏈斷開，ikj，則其相應(yīng)完全加括號(hào)方式為,計(jì)算量：Ai:k的計(jì)算量加上Ak+1:j的計(jì)算量，再加上Ai:k和Ak+1:j相乘的計(jì)算量,.,88,分析最優(yōu)解的結(jié)構(gòu),特征：計(jì)算Ai:j的最優(yōu)次序所包含的計(jì)算矩陣子鏈Ai:k和Ak+1:j的次序也是最優(yōu)的。矩陣連乘計(jì)算次序問(wèn)題的最優(yōu)解包含著其子問(wèn)題的最優(yōu)解。這種

33、性質(zhì)稱為最優(yōu)子結(jié)構(gòu)性質(zhì)。問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問(wèn)題可用動(dòng)態(tài)規(guī)劃算法求解的顯著特征。,.,89,建立遞歸關(guān)系,設(shè)計(jì)算Ai:j，1ijn，所需要的最少數(shù)乘次數(shù)mi,j，則原問(wèn)題的最優(yōu)值為m1,n當(dāng)i=j時(shí)，Ai:j=Ai，因此，mi,i=0，i=1,2,n當(dāng)ij時(shí)，可以遞歸地定義mi,j為：,這里的維數(shù)為,的位置只有種可能,.,90,計(jì)算最優(yōu)值,對(duì)于1ijn不同的有序?qū)?i,j)對(duì)應(yīng)于不同的子問(wèn)題。因此，不同子問(wèn)題的個(gè)數(shù)最多只有由此可見(jiàn)，在遞歸計(jì)算時(shí)，許多子問(wèn)題被重復(fù)計(jì)算多次。這也是該問(wèn)題可用動(dòng)態(tài)規(guī)劃算法求解的又一顯著特征。用動(dòng)態(tài)規(guī)劃算法解此問(wèn)題，可依據(jù)其遞歸式以自底向上的方式進(jìn)行計(jì)算。在計(jì)算過(guò)

34、程中，保存已解決的子問(wèn)題答案。每個(gè)子問(wèn)題只計(jì)算一次，而在后面需要時(shí)只要簡(jiǎn)單查一下，從而避免大量的重復(fù)計(jì)算，最終得到多項(xiàng)式時(shí)間的算法,.,91,用動(dòng)態(tài)規(guī)劃法求最優(yōu)解,publicstaticvoidmatrixChain(intp,intm,ints)intn=p.length-1;for(inti=1;i=n;i+)mii=0;for(intr=2;r=n;r+)for(inti=1;i=n-r+1;i+)intj=i+r-1;mij=mi+1j+pi-1*pi*pj;sij=i;for(intk=i+1;kj;k+)intt=mik+mk+1j+pi-1*pk*pj;if(t0)return

35、mij;if(i=j)return0;intu=lookupChain(i+1,j)+pi-1*pi*pj;sij=i;for(intk=i+1;kj;k+)intt=lookupChain(i,k)+lookupChain(k+1,j)+pi-1*pk*pj;if(tu)u=t;sij=k;mij=u;returnu;,.,95,最長(zhǎng)公共子序列,若給定序列X=x1,x2,xm，則另一序列Z=z1,z2,zk，是X的子序列是指存在一個(gè)嚴(yán)格遞增下標(biāo)序列i1,i2,ik使得對(duì)于所有j=1,2,k有：zj=xij。例如，序列Z=B，C，D，B是序列X=A，B，C，B，D，A，B的子序列，相應(yīng)的遞增下

36、標(biāo)序列為2，3，5，7。給定2個(gè)序列X和Y，當(dāng)另一序列Z既是X的子序列又是Y的子序列時(shí)，稱Z是序列X和Y的公共子序列。給定2個(gè)序列X=x1,x2,xm和Y=y1,y2,yn，找出X和Y的最長(zhǎng)公共子序列。,.,96,最長(zhǎng)公共子序列的結(jié)構(gòu),設(shè)序列X=x1,x2,xm和Y=y1,y2,yn的最長(zhǎng)公共子序列為Z=z1,z2,zk，則(1)若xm=yn，則zk=xm=yn，且zk-1是xm-1和yn-1的最長(zhǎng)公共子序列。(2)若xmyn且zkxm，則Z是xm-1和Y的最長(zhǎng)公共子序列。(3)若xmyn且zkyn，則Z是X和yn-1的最長(zhǎng)公共子序列。,由此可見(jiàn)，2個(gè)序列的最長(zhǎng)公共子序列包含了這2個(gè)序列的前綴

37、的最長(zhǎng)公共子序列。因此，最長(zhǎng)公共子序列問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。,.,97,子問(wèn)題的遞歸結(jié)構(gòu),由最長(zhǎng)公共子序列問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)建立子問(wèn)題最優(yōu)值的遞歸關(guān)系。用cij記錄序列和的最長(zhǎng)公共子序列的長(zhǎng)度。其中，Xi=x1,x2,xi；Yj=y1,y2,yj。當(dāng)i=0或j=0時(shí)，空序列是Xi和Yj的最長(zhǎng)公共子序列。故此時(shí)Cij=0。其他情況下，由最優(yōu)子結(jié)構(gòu)性質(zhì)可建立遞歸關(guān)系如下：,.,98,計(jì)算最優(yōu)值,由于在所考慮的子問(wèn)題空間中，總共有(mn)個(gè)不同的子問(wèn)題，因此，用動(dòng)態(tài)規(guī)劃算法自底向上地計(jì)算最優(yōu)值能提高算法的效率。,AlgorithmlcsLength(x,y,b)1:mx.length-1;2:n

38、y.length-1;3:ci0=0;c0i=0;4:for(inti=1;i=cij-1)10:cij=ci-1j;11:bij=2;12:else13:cij=cij-1;14:bij=3;,構(gòu)造最長(zhǎng)公共子序列Algorithmlcs(inti,intj,charx,intb)if(i=0|j=0)return;if(bij=1)lcs(i-1,j-1,x,b);System.out.print(xi);elseif(bij=2)lcs(i-1,j,x,b);elselcs(i,j-1,x,b);,.,99,算法的改進(jìn),在算法lcsLength和lcs中，可進(jìn)一步將數(shù)組b省去。事實(shí)上，數(shù)組

39、元素cij的值僅由ci-1j-1，ci-1j和cij-1這3個(gè)數(shù)組元素的值所確定。對(duì)于給定的數(shù)組元素cij，可以不借助于數(shù)組b而僅借助于c本身在時(shí)間內(nèi)確定cij的值是由ci-1j-1，ci-1j和cij-1中哪一個(gè)值所確定的。如果只需要計(jì)算最長(zhǎng)公共子序列的長(zhǎng)度，則算法的空間需求可大大減少。事實(shí)上，在計(jì)算cij時(shí)，只用到數(shù)組c的第i行和第i-1行。因此，用2行的數(shù)組空間就可以計(jì)算出最長(zhǎng)公共子序列的長(zhǎng)度。進(jìn)一步的分析還可將空間需求減至O(min(m,n)。,.,100,凸多邊形最優(yōu)三角剖分,用多邊形頂點(diǎn)的逆時(shí)針序列表示凸多邊形，即P=v0,v1,vn-1表示具有n條邊的凸多邊形。若vi與vj是多邊

40、形上不相鄰的2個(gè)頂點(diǎn)，則線段vivj稱為多邊形的一條弦。弦將多邊形分割成2個(gè)多邊形vi,vi+1,vj和vj,vj+1,vi。多邊形的三角剖分是將多邊形分割成互不相交的三角形的弦的集合T。給定凸多邊形P，以及定義在由多邊形的邊和弦組成的三角形上的權(quán)函數(shù)w。要求確定該凸多邊形的三角剖分，使得即該三角剖分中諸三角形上權(quán)之和為最小。,.,101,三角剖分的結(jié)構(gòu)及其相關(guān)問(wèn)題,一個(gè)表達(dá)式的完全加括號(hào)方式相應(yīng)于一棵完全二叉樹，稱為表達(dá)式的語(yǔ)法樹。例如，完全加括號(hào)的矩陣連乘積(A1(A2A3)(A4(A5A6)所相應(yīng)的語(yǔ)法樹如圖(a)所示。凸多邊形v0,v1,vn-1的三角剖分也可以用語(yǔ)法樹表示。例如，圖(

41、b)中凸多邊形的三角剖分可用圖(a)所示的語(yǔ)法樹表示。矩陣連乘積中的每個(gè)矩陣Ai對(duì)應(yīng)于凸(n+1)邊形中的一條邊vi-1vi。三角剖分中的一條弦vivj，ij，對(duì)應(yīng)于矩陣連乘積Ai+1:j。,.,102,最優(yōu)子結(jié)構(gòu)性質(zhì),凸多邊形的最優(yōu)三角剖分問(wèn)題有最優(yōu)子結(jié)構(gòu)性質(zhì)。事實(shí)上，若凸(n+1)邊形P=v0,v1,vn-1的最優(yōu)三角剖分T包含三角形v0vkvn，1kn-1，則T的權(quán)為3個(gè)部分權(quán)的和：三角形v0vkvn的權(quán)，子多邊形v0,v1,vk和vk,vk+1,vn的權(quán)之和?？梢詳嘌?，由T所確定的這2個(gè)子多邊形的三角剖分也是最優(yōu)的。因?yàn)槿粲衯0,v1,vk或vk,vk+1,vn的更小權(quán)的三角剖分將導(dǎo)致

42、T不是最優(yōu)三角剖分的矛盾。,.,103,最優(yōu)三角剖分的遞歸結(jié)構(gòu),定義tij，1i1時(shí)，2.1j(i)。此時(shí)，。故在這種情況下，N(i,j)=N(i-1,j)，從而Size(i,j)=Size(i-1,j)。2.2j(i)，(i,(i)MNS(i,j)。則對(duì)任意(t,(t)MNS(i,j)有ti且(t)T(S,b(1)，設(shè)是作業(yè)集S在機(jī)器M2的等待時(shí)間為b(1)情況下的一個(gè)最優(yōu)調(diào)度。則(1)，(2)，(n)是N的一個(gè)調(diào)度，且該調(diào)度所需的時(shí)間為a(1)+T(S,b(1)a(1)+T。這與是N的最優(yōu)調(diào)度矛盾。故TT(S,b(1)。從而T=T(S,b(1)。這就證明了流水作業(yè)調(diào)度問(wèn)題具有最優(yōu)子結(jié)構(gòu)的性

43、質(zhì)。,由流水作業(yè)調(diào)度問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)可知，,.,112,Johnson不等式,對(duì)遞歸式的深入分析表明，算法可進(jìn)一步得到簡(jiǎn)化。設(shè)是作業(yè)集S在機(jī)器M2的等待時(shí)間為t時(shí)的任一最優(yōu)調(diào)度。若(1)=i,(2)=j。則由動(dòng)態(tài)規(guī)劃遞歸式可得:T(S,t)=ai+T(S-i,bi+maxt-ai,0)=ai+aj+T(S-i,j,tij)其中，,如果作業(yè)i和j滿足minbi,ajminbj,ai，則稱作業(yè)i和j滿足Johnson不等式。,.,113,流水作業(yè)調(diào)度的Johnson法則,交換作業(yè)i和作業(yè)j的加工順序，得到作業(yè)集S的另一調(diào)度，它所需的加工時(shí)間為T(S,t)=ai+aj+T(S-i,j,tji)其中，當(dāng)作業(yè)i和j滿足Johnson不等式時(shí)，有由此可見(jiàn)當(dāng)作業(yè)i和作業(yè)j不滿足Johnson不等式時(shí)，交換它們的加工順序后，不增加加工時(shí)間。對(duì)于流水作業(yè)調(diào)度問(wèn)題，必存在最優(yōu)調(diào)度，使得作業(yè)(i)和(i+1)滿足Johnson不等式。進(jìn)一步還可以證明，調(diào)度滿足Johnson法則當(dāng)且僅當(dāng)對(duì)任意i2n時(shí)，算法需要(n2n)計(jì)算時(shí)間。,.,117,算法改進(jìn),由m(i,j)的遞歸式容易證明，在一般情況下，對(duì)每一個(gè)確定的i(1in)，函數(shù)m(i,j)是關(guān)于變量j的階梯狀單調(diào)不減函數(shù)。跳躍點(diǎn)是這一類函數(shù)的描述特征。在一般情況下，函數(shù)m(