南開大學(xué)計(jì)算機(jī)算法設(shè)計(jì)與分析

計(jì)算機(jī)算法設(shè)計(jì)與分析引子DonaldKnuth,算法學(xué)歷史上最卓越的計(jì)算機(jī)科學(xué)家之一,如此論述:受過良好訓(xùn)練的計(jì)算機(jī)科學(xué)家知道怎樣處理算法:如何構(gòu)造算法,操作算法,理解算法以及分析算法。這些知識遠(yuǎn)不止為了編寫良好的計(jì)算機(jī)程序而準(zhǔn)備的。算法是一種一般性的智能工具,它必定有助于我們對其他學(xué)科的理解,不管是化學(xué),語言學(xué),音樂,還是另外的科學(xué)。為什么算法會有這種作用呢?我們可以這樣理解:人們常說,一個(gè)人只有把知識教給別人，才能真正掌握它。實(shí)際上,一個(gè)人只有把知識教給“計(jì)算機(jī)”，才能“真正”掌握它，也就是說，將知識表述為一種算法……比起簡單地按照常規(guī)去理解事物，用算法將其形式化會使我們的理解更加深刻。Knuth,D.E.SelectedPapersonComputerScience,CSLIPublicationsandCambridgeUniversityPress,NewYork,1996有趣的問題1.西雅圖附近一家著名軟件公司主考官面試題：

4個(gè)人過橋，時(shí)間為晚上，只有一只手電筒，最多只能兩個(gè)人同時(shí)過橋，且必須帶手電，只能步行將手電簡帶來帶去，而不能扔來扔去。每個(gè)人走路的速度不同，甲過橋要１分鐘，乙過橋需要２分鐘，丙需要５分鐘，丁需要１０分鐘，兩個(gè)一起走，則速度等于其中較慢的人的速度。2.關(guān)于驗(yàn)證一個(gè)數(shù)是否為素?cái)?shù)的問題3.旅行商問題：如何走最短的路，經(jīng)過所有的城市。4.漢諾塔問題漢諾塔問題voidhanoi(intn,charone,chartwo,charthree)/*將n個(gè)盤子從one座借助two座，移到three座*/{if(n==1)move(one,three);else {hanoi(n-1,one,three,two); move(one,three); hanoi(n-1,two,one,three); }}main(){intm;printf(inputthenumberofdiskes:);scanf(“%d”,&m);printf(“Thesteptomoving%3ddiskes:\n”,m);hanoi(m,’A’,’B’,’C’);}ABC每個(gè)盤子有三個(gè)位置,n個(gè)共有3n緒論

1.1 交通信號燈問題

1.2 什么是算法

1.3 算法的評價(jià)

1.4 基本概念

1.5 算法研究與Moore定律

1.6 MAXMIN的問題1.1交通信號燈問題1.1.1

問題

⑴每一車輛通過路口時(shí)都不會與其它車輛發(fā)生沖突； ⑵車輛在路口等待通過的時(shí)間盡可能少。1.1.2實(shí)例共有13條路線：ab,ac,adba,bc,bdda,db,dcea,eb,ec,ed1.1.3

圖著色問題

已知：n點(diǎn)無向圖G=<V,E>,||V||=n。求：G的最小色數(shù)(colornumber)k，使得用k種顏色對G的頂點(diǎn)著色，可令任二相鄰頂點(diǎn)著色不同。地圖著色問題，交通信號燈問題都可以歸結(jié)為圖的頂點(diǎn)著色問題無向圖頂點(diǎn)著色問題：頂點(diǎn)，邊最小色數(shù)k地圖著色問題：國家，相鄰關(guān)系最小色數(shù)k交通信號燈問題：路線，交叉關(guān)系最小相位（組）數(shù)k2.圖著色(GraphColoring）問題

圖著色問題是一個(gè)經(jīng)典的組合算法問題，源于地圖著色問題。在繪制地圖時(shí)，總是要求相鄰的國家著上不同的顏色以示區(qū)別。1852年一位英國大學(xué)生古德里（F.Guthrie）提出了一個(gè)猜測：為了給任一個(gè)平面地圖著色，并使任何有公共邊界的區(qū)域顏色不同，至多需要四種顏色。這就是四色問題，又稱四色猜想。古德里僅僅是提出了這個(gè)猜想，他和他的老師未能證明。2.圖著色(GraphColoring）問題

二十幾年后的1878年，著名數(shù)學(xué)家凱萊（A.Kayley）發(fā)表了一篇“論地圖著色”的文章，雖然仍沒有解決這個(gè)問題，卻掀起了四色猜想的研究熱。經(jīng)過一百年的探索，美國伊利諾大學(xué)的哈肯（W.Haken）與阿佩爾（K.Appel）通過改進(jìn)算法，借助計(jì)算機(jī)（共用了1200個(gè)機(jī)時(shí)）終于在1976年完成了四色猜想的證明。當(dāng)?shù)氐泥]局在寄出的信上除了通常的郵戳(postmark)外，還要加蓋“四色是足夠的”一句話以表示自豪。2.圖著色(GraphColoring）問題

當(dāng)把地圖(Map)上的一個(gè)國家與圖(Graph)上的一個(gè)頂點(diǎn)對應(yīng)，兩個(gè)國家的相鄰關(guān)系對應(yīng)于無向圖上的邊，于是，上面關(guān)于地圖的“四色問題”實(shí)際上是無向圖的頂點(diǎn)著色問題的特例。無向圖的頂點(diǎn)著色問題是一個(gè)有名的NP完全問題，這類問題屬于“計(jì)算機(jī)難解”問題，關(guān)于著色問題算法的研究已有許多學(xué)者的大量成果。

Fig.1.2給出的無向圖對應(yīng)于五叉路口實(shí)例，該圖有13個(gè)結(jié)點(diǎn)和20條邊，其中ba,dc,ed三個(gè)頂點(diǎn)是孤立點(diǎn)，說明這三條路線與其它所有路線不相交，就是所謂的“拐小彎”。

c1.1.4算法設(shè)計(jì)討論1.窮舉法令色數(shù)k從2開始，用k種顏色分別對13個(gè)頂點(diǎn)著色，共有k13種情形，當(dāng)K＝5時(shí)，需要進(jìn)行

20×(213+313+413+513)次比較。413=2262.剪枝法對窮舉法的改進(jìn)。不必窮舉所有可能的著色法，例如：頂點(diǎn)ab著色為c1，則點(diǎn)ab的所有鄰點(diǎn)ea,da,bc,bd都不必著色為c1；…

第一個(gè)點(diǎn)，例如ab，可以只著一種顏色，因顏色的對稱性，ab取其它(k–1)種顏色的情形可不必再檢查。此剪枝法一項(xiàng)可以把計(jì)算量縮小到原來的1/k。3.啟發(fā)式(Heuristic)算法依賴于人的直覺知識：為了用最小色數(shù)為所有頂點(diǎn)著色，也就是要每一種顏色在不出現(xiàn)沖突的條件下為盡量多的頂點(diǎn)著色。算法1.1啟發(fā)式算法實(shí)現(xiàn)圖著色用k=1,2,3,…來表示顏色1#,2#,3#,…,Color[i]=3表示對i頂點(diǎn)著3#色，<i,j>∈E表示頂點(diǎn)i,j相鄰，Color[i]=0表示頂點(diǎn)i未著色此法又稱貪心法，比窮舉算法和剪枝算法快得多，當(dāng)n不太小時(shí)，其計(jì)算量比前者要少千萬倍甚至更多，不過它不一定總是得到最優(yōu)解。例如Fig.1.3中的5點(diǎn)無向圖，用貪心法著色需要用紅(R)、黃(Y)、藍(lán)(B)三種顏色，但實(shí)際上，這不是該圖的最小色數(shù)，顯然，兩種顏色已可滿足要求。即：頂點(diǎn)1、3、4著紅色，頂點(diǎn)2、5著黃色。(不同編號順序)1.1.4討論1.權(quán)衡(trade-off)的概念窮舉法：思想最簡單、最直觀，但計(jì)算量最大。改進(jìn)的窮舉法：比前者要快，容許的n值可以再大一些，不過對于大的n，計(jì)算量仍會很大，它比窮舉法有所改進(jìn)的代價(jià)是程序較為復(fù)雜。啟發(fā)式的貪心算法：簡單，快速，但不能保證總是得到最優(yōu)解。2.最優(yōu)性(Optimality)GreedyColor算法是一種“近似最優(yōu)”算法。執(zhí)行的結(jié)果是，

k=4，13條路線分為4組：（括號里的路線為補(bǔ)充的不沖突項(xiàng)）ab,ac,ad,ba,dc,ed;bc,bd,ea,(ba,dc,ed);da,db,(ba,dc,ed,ad);eb,ec,(ba,dc,ed,ea).一般的說可能還有更好的分組方法，例如分為三組。不過，在這個(gè)實(shí)例中，卻不難證明分為4組已不能改進(jìn)。這是因?yàn)閺腇ig.1.2中發(fā)現(xiàn)ac,bd,da,eb4個(gè)頂點(diǎn)組成一個(gè)完全子圖（又稱團(tuán)，Clique），4點(diǎn)的無向完全圖至少需4色，因此這個(gè)解已不可改進(jìn)。c3.算法設(shè)計(jì)討論·算法的研究與許多實(shí)際應(yīng)用問題直接相關(guān)，它不僅是個(gè)理論問題；·一些典型的算法問題的研究，如著色問題、旅行商問題、背包問題等等，常常在應(yīng)用算法的設(shè)計(jì)中發(fā)揮作用；·用來解一個(gè)問題，可以有多種不同的算法，它們的效果可能差別很大，如何設(shè)計(jì)有效的算法是算法理論的主要目標(biāo)。1.2什么是算法1.2.1算法1.Webster辭典定義：算法即在有限步驟內(nèi)解一個(gè)數(shù)學(xué)問題的過程，步驟中常常包括某一操作的重復(fù)。更廣義地說，一個(gè)算法就是為解一個(gè)問題或?qū)崿F(xiàn)某一目標(biāo)的逐步過程。2.D.E.Knuth定義：一個(gè)算法，就是一個(gè)有窮規(guī)則的集合，其中之規(guī)則規(guī)定了一個(gè)解決某一特定類型的問題的運(yùn)算序列；此外，它還應(yīng)有五個(gè)重要特性：·有窮性：一個(gè)算法必須總是在執(zhí)行有窮步之后結(jié)束；·確定性：算法的每一步驟，必須是確切地定義的；·輸入：有0或多個(gè)輸入值；·輸出：有1或多個(gè)輸出值；·能行性：算法中要做的運(yùn)算都是相當(dāng)基本的，能夠精確地進(jìn)行的。3.形式化定義：算法就是一個(gè)對任一有效輸入能夠停機(jī)的Turing機(jī)。1.2.2算法與問題

例：整數(shù)乘法問題全部可能輸入集合：{<a,b>|a,b∈Z}，其中Z表示整數(shù)集；一個(gè)實(shí)例：<2,4>,求：2×4=?旅行商問題(TravelingSalesmanProblem)實(shí)例集為：{n,Wn*n=[Wij]|n∈Z,Wij∈R,i,j∈[1,…,n]}；一個(gè)實(shí)例：n=4,該實(shí)例（n,W）就是求環(huán)游4個(gè)城市(1,2,3,4)且代價(jià)和最小的周游路線，其中權(quán)矩陣W給出了4個(gè)城市之間的距離（代價(jià)），Wij表示由城市i到城市j的距離（代價(jià)）。語言L<G,Σ>的識別問題其中G為文法，Σ為一字符集。L(G)為Σ上由G生成的語言，L(G)∈Σ*，Σ*表示由Σ中的字符組成的所有字符串集合。語言L的識別問題{G,Σ,ω|ω∈Σ*}的一個(gè)實(shí)例ω∈Σ*，識別算法判斷ω∈L(G)是否成立。算法研究對象：問題。問題由所有實(shí)例組成。一般對于問題P，總有其相應(yīng)的實(shí)例集I，那么，一個(gè)算法A是問題P的算法，意味著把P的任一實(shí)例input∈I作為A的輸入，都能得到問題P的正確的輸出。一個(gè)問題可以有許多個(gè)不同的算法。1.2.3算法與程序程序(Program)可以用來描述算法，同一個(gè)算法可以用不同的語言編寫的程序來描述。程序不一定是算法。程序設(shè)計(jì)可以分為四個(gè)層次：算法、方法學(xué)、語言和工具。

抽象級更新速度算法程序設(shè)計(jì)方法程序設(shè)計(jì)語言編程工具1.3算法的評估1.3.1正確性算法的正確性是評估的前提。有些算法，特別是一些十分精致巧妙的算法，其正確性需要證明，有的證明難度較大，例如無向圖單源最短路徑問題的Dijkstra算法，構(gòu)造最優(yōu)二分搜索樹的動態(tài)規(guī)劃算法的Knuth改進(jìn)。有些算法，其正確性是明顯的，例如：算法1.2選擇排序算法SelectSort

1.3.2時(shí)間代價(jià)

評估算法的時(shí)間代價(jià)是算法分析的核心。算法的時(shí)間代價(jià)的大小用算法的時(shí)間復(fù)雜度(TimeComplexity)來度量。但要考慮到以下因素：

·用來運(yùn)行算法的計(jì)算機(jī)的性能的差別；

·算法運(yùn)行的軟件平臺和描述語言的差別；

·算法所解的問題是多種多樣的；

·同一問題的算法對不同的實(shí)例，所花的時(shí)間開銷也可能有很大的差別。1.3.3空間代價(jià)

空間消耗是衡量算法優(yōu)劣的另一重要因素。不過算法的空間復(fù)雜性分析的重要性常常列于時(shí)間復(fù)雜性分析之后。在許多應(yīng)用問題中，人們往往以適當(dāng)增加算法的空間代價(jià)來減少時(shí)間代價(jià)?？臻g復(fù)雜度的分析類似于時(shí)間復(fù)雜度的分析，其有關(guān)的概念和方法幾乎是平行的。1.3.4最優(yōu)性

一個(gè)算法不一定是最優(yōu)的。所謂最優(yōu)算法是指在某一種度量標(biāo)準(zhǔn)之下，優(yōu)于該問題的所有（可能的）算法。一般，某一問題的最優(yōu)算法是指在時(shí)間復(fù)雜度的計(jì)算基礎(chǔ)上的最優(yōu)性。算法1.3求n個(gè)不同整數(shù)中的最大元MaxElement對于任何n個(gè)整數(shù)，要求其最大元，至少需進(jìn)行n-1次比較，因此，可以說上述算法Max(S)是最優(yōu)的。為了證明在n個(gè)不同元中求出最大元，至少需n-1次比較，可以把n個(gè)元?jiǎng)澐譃槿齻€(gè)動態(tài)的組A,B,C。

A：未知元的集合

B：已肯定不是最大元的元素集合

C：最大元的集合。

不難證明，任何一個(gè)通過二元比較求最大元的算法都是要從三個(gè)集合的元數(shù)為(n,0,0)（即|A|=n,|B|=0,|C|=0）狀態(tài)開始，經(jīng)過運(yùn)行，最終達(dá)到(0,n-1,1)狀態(tài)，即：

這實(shí)際上是元素從集合A向B和C中移動的過程。但每次兩個(gè)元的比較至多只可把一個(gè)較小的元素從集合A移至集合B。因此，任何最大元算法至少要進(jìn)行n-1次比較，從而證明了上述最大元算法Max(A)是最優(yōu)的。

ABCABC|A|=n|B|=0|C|=0|A|=n-1|B|=0|C|=1|A|=n-2|B|=1|C|=11.4算法理論的基本概念1.4.1基本操作算法的時(shí)間代價(jià)的度量不應(yīng)依賴于算法運(yùn)行的硬件和軟件平臺，因此不能從下面幾個(gè)方面來度量時(shí)間代價(jià)：

?算法運(yùn)行的實(shí)際執(zhí)行時(shí)間；

?運(yùn)行過程中所執(zhí)行的指令條數(shù)；(不同語言,不同編程風(fēng)格)?運(yùn)行過程中程序循環(huán)的次數(shù)。(循環(huán)體差別大)

因此需要引入基本操作的概念來度量時(shí)間代價(jià)?；静僮骶褪侵杆惴ㄟ\(yùn)行中起主要作用且花費(fèi)最多時(shí)間的操作。例如：兩個(gè)實(shí)數(shù)矩陣的乘法問題中，矩陣的實(shí)數(shù)元素之間的數(shù)乘是基本操作；對N個(gè)整數(shù)進(jìn)行排序的算法中，整數(shù)間的比較是基本操作；移動操作；移動與比較。1.4.2問題實(shí)例長度

算法運(yùn)行的時(shí)間（或空間）代價(jià)還與問題實(shí)例長度，即輸入規(guī)模有關(guān)，這稱為問題實(shí)例長度。

問題實(shí)例長度是指作為該問題的一個(gè)實(shí)例的輸入規(guī)模大小。例如：

排序問題：問題實(shí)例長度是待排序元素序列的長度n；

矩陣乘積：問題實(shí)例長度是矩陣（指n階方陣）的階數(shù)n；

圖的最短路徑問題：圖G=<V,E>的頂點(diǎn)數(shù)n=||V||和邊數(shù)m=||E||是問題實(shí)例長度；

字符串匹配問題：文本T的長度n，亦可再加上樣本P的長度m為問題實(shí)例長度。算法的時(shí)間（或空間）代價(jià)由該算法用于問題長度為n的實(shí)例所需要的基本操作次數(shù)來刻畫。一般一個(gè)算法的時(shí)間復(fù)雜度用函數(shù)T(n)(或T(n,m))表示，空間復(fù)雜度用S(n)表示。1.4.3復(fù)雜度的漸進(jìn)性質(zhì)算法的比較是根據(jù)復(fù)雜度函數(shù)的漸進(jìn)性質(zhì)的比較進(jìn)行的。例如：算法A和算法B，其時(shí)間復(fù)雜度函數(shù)為TA(n)和TB(n)，在Fig.1.4中，雖然當(dāng)n<n0時(shí)TB(n)<TA(n)，但在n>n0時(shí)，或說n充分大時(shí)(n->∞)，有TA(n)<TB(n)，因此認(rèn)為算法A優(yōu)于算法B。㊣算法B有條件優(yōu)于算法A：在實(shí)際應(yīng)用中問題規(guī)模是給定的1.4.4最壞情形和最好情形例：算法1.4插入排序算法Insertsortn=10時(shí)，有三種輸入：正序：123456789109次比較逆序：1098765432145次比較（9+1）9/2隨機(jī)：3745102961828次比較同一算法，相同的問題長度，不同的輸入，其時(shí)間代價(jià)一般不同。因此在實(shí)際的算法分析中，復(fù)雜度函數(shù)值T(n)不是唯一的，在大多數(shù)情況下取其最大值，即最壞情形的時(shí)間（空間）復(fù)雜度。設(shè)Dn為問題P的所有長度為n的實(shí)例集合，輸入實(shí)例I∈Dn

，||I||=n，而t(I)為用來解問題P的算法A在以I為輸入時(shí)的執(zhí)行代價(jià)（基本操作次數(shù)），則W(n)=MAX{t(I)}

I∈DnW(n)稱為算法A的最壞情形(WorstCase)時(shí)間復(fù)雜度。類似的，還可以定義最好情形（BestCase）時(shí)間復(fù)雜度，B(n)=MIN{t(I)}---最好與最壞復(fù)雜度有何用,何時(shí)用?

I∈Dn

平均復(fù)雜度何時(shí)用

1.4.5平均情形和算法的期望復(fù)雜度設(shè)算法A的輸入為I∈Dn的概率為P(I)，則

其中P(I)滿足為實(shí)例輸入I出現(xiàn)的概率，t(I)為算法A完成實(shí)例I的耗費(fèi)值（即基本操作次數(shù)）。

期望復(fù)雜度比最壞情形復(fù)雜度更好的刻畫了算法的性能，但是，由于Dn一般很大，P(I)和t(I)較難計(jì)算，因此，平均情形的復(fù)雜度分析比較難。例如：在數(shù)組L[1,…,n]中搜索，求使L[j]=X的位置j。算法1.5順序搜索算法SeqSearch因?yàn)長[1,…,n]長度為n，不同的輸入實(shí)例由X的值決定，實(shí)例集Dn由下列實(shí)例組成：（1）X在L中，共有n種情況：I1,…,In

，Ii表示X=L[i] (i=1,…,n)；（2）X不在L中，這時(shí)X有許多可能值，把它們統(tǒng)記為In+1

。因?yàn)楫?dāng)X=L[k]時(shí)，t(Ik)=k，(k=1,…,n)，X不在L中時(shí)，t(In+1)=n。這時(shí)W(n)容易計(jì)算：W(n)=MAX{t(Ik)|k=1,2,…,n,n+1}=n。但計(jì)算A(n)則應(yīng)首先設(shè)定I在Dn中的分布：設(shè)X在L中的概率為q，故X不在L中的概率為1-q，假定X在L中，它等于L的n個(gè)元素是等可能的，即P(Ik)=Pk=q/n,(k=1,…,n),P(In+1)=Pn+1=1-q，當(dāng)q=1，即已知X在L中，A(n)=(n+1)/2，q=1/2，即X有一半可能在L中，A(n)=3n/4+1/4。也就是說，在上面的假設(shè)條件下，我們的順序搜索的平均代價(jià)大約是n/2次比較和3n/4次比較。1.4.6復(fù)雜度函數(shù)的表示

各種復(fù)雜度函數(shù)的表示方法大致可按表達(dá)的精確程度分為下面的三個(gè)等級:(何種情況下用相應(yīng)的復(fù)雜度函數(shù))

1.解析表達(dá)式。用解析表達(dá)式刻畫復(fù)雜度函數(shù)是最精確的表達(dá)方式。例如·求n元中之最大元算法MaxElement的復(fù)雜度為T(n)=W(n)=A(n)=n–1?！ろ樞蛩阉魉惴ǖ淖顗那樾螘r(shí)間復(fù)雜度為W(n)=n；在指定分布條件及q=1情形下的期望時(shí)間復(fù)雜度為

A(n)=(n+1)/2。2.階（Order）表達(dá)式。為了簡化算法復(fù)雜度分析的方法，往往只需計(jì)算當(dāng)問題規(guī)模較大時(shí)算法的漸進(jìn)復(fù)雜度的階。定義1.1

稱（復(fù)雜度）函數(shù)T(n)是O(f(n))的，即

T(n)=O(f(n))，如果存在常數(shù)c>0與n0

，當(dāng)n>n0時(shí)有T(n)≤cf(n)。例如：T1(n)=(n+1)/2=O(n),T2(n)=3n2+4n+5=O(n2)定義1.2

稱（復(fù)雜度）函數(shù)T(n)是Ω(f(n))的，即T(n)=Ω(f(n))，如果存在常數(shù)c>0與n0

，當(dāng)n>n0

時(shí)有T(n)≥cf(n)。例如：T1(n)=(n+1)/2=Ω(n),T2(n)=3n2+4n+5=Ω(n2)定義1.3

稱（復(fù)雜度）函數(shù)T(n)是θ(f(n))的，即T(n)=θ(f(n))，如果存在常數(shù)c1,c2>0與n0，當(dāng)n>n0時(shí)有c1f(n)≥T(n)≥c2f(n)。例如：T1(n)=(n+1)/2=θ(n),T2(n)=3n2+4n+5=θ(n2)顯然，如果T(n)=O(f(n))且T(n)=Ω(f(n))，則T(n)=θ(f(n))。3.多項(xiàng)式函數(shù)和指數(shù)函數(shù)。多項(xiàng)式函數(shù)指T(n)為自變量n的多項(xiàng)式函數(shù)，例如T1(n)=n/2+1/2，T2(n)=3n2+4n+5等。而指數(shù)函數(shù)如T3(n)=2n+5，T4(n)=3n/2–8等等，自變量n出現(xiàn)在