算法分析與設(shè)計(jì)技巧

AlgorithmAnalysisandDesignTechniqs第1章算法的概念

1.1 算法的概念和描述 1.2 算法的時(shí)間復(fù)雜度

和空間復(fù)雜度第2章常用算法

2.1 遞歸法 2.2 分治法 2.3 貪心法 2.4 搜索法與回溯法目

錄第3章動(dòng)態(tài)規(guī)劃

3.1 動(dòng)態(tài)規(guī)劃的基本思想與概念 3.2 動(dòng)態(tài)規(guī)劃的簡(jiǎn)單應(yīng)用 3.3 動(dòng)態(tài)規(guī)劃的深入研究 3.4 動(dòng)態(tài)規(guī)劃的優(yōu)化方法第4章搜索算法中的優(yōu)化技巧

4.1 搜索中的剪枝技巧 4.2 選擇合適的搜索方向 4.3 A*算法 4.4 跳舞鏈 4.5 搜索還是動(dòng)態(tài)規(guī)劃目

錄第5章圖上的算法 5.1 并查集 5.2 生成樹 5.3 最短路 5.4 強(qiáng)連通分量 5.5 2—SAT 5.6 差分約束 5.7 二分圖 5.8 網(wǎng)絡(luò)流目

錄第一章

算法的概念1.1 算法的概念和描述1.2 算法的時(shí)間復(fù)雜度和空間復(fù)雜度1.1 算法的概念和描述【1.1.1 算法的概念】

算法是一系列解決問題的清晰指令，也就是對(duì)于符合一定規(guī)范的輸入在有限步驟內(nèi)求解某一問題所使用的一組定義明確的規(guī)則。通俗點(diǎn)說，就是計(jì)算機(jī)解題的過程。在這個(gè)過程中，無論是形成解題思路還是編寫程序，都是在實(shí)施某種算法。前者是推理實(shí)現(xiàn)的算法，后者是操作實(shí)現(xiàn)的算法。

這個(gè)定義可以用一幅簡(jiǎn)明的圖來說明，如圖1.1所示。

一個(gè)算法應(yīng)該具有以下五個(gè)重要的特征：①有窮性：一個(gè)算法必須保證執(zhí)行有限步之后結(jié)束，并且每一步都在有窮時(shí)間內(nèi)完成。②確定性：算法的每一步驟都必須有確切的定義。③輸入：一個(gè)算法有零個(gè)或多個(gè)輸入，以刻畫運(yùn)算對(duì)象的初始情況。④輸出：一個(gè)算法有一個(gè)或多個(gè)輸出，以反映對(duì)輸入數(shù)據(jù)加工后的結(jié)果。沒有輸出的算法是毫無意義的。⑤可行性：算法應(yīng)該是可行的，這意味著所有待實(shí)現(xiàn)的算法都是能夠理解和實(shí)現(xiàn)的，并可通過有限次運(yùn)算完成。

為了闡明算法的概念，本節(jié)將以三種方法為例來解決同一個(gè)問題：計(jì)算兩個(gè)整數(shù)的最大公約數(shù)。這些例子會(huì)幫助我們闡明以下幾項(xiàng)要點(diǎn)：圖1.1算法的概念1.1 算法的概念和描述①算法的每一個(gè)步驟都必須沒有歧義，不能有半點(diǎn)含糊。②必須認(rèn)真確定算法所處理的輸入的值域。③同一算法可以用幾種不同的形式來描述。④同一問題，可能存在幾種不同的算法。⑤針對(duì)同一問題的算法可能會(huì)基于完全不同的解題思路而且解題速度也會(huì)有顯著不同。

還記得最大公約數(shù)的定義嗎?將兩個(gè)不全為0的非負(fù)整數(shù)m和n的最大公約數(shù)記為gcd（m，n），代表能夠整除（即余數(shù)為0）m和n的最大正整數(shù)。亞歷山大的歐幾里得（公元前3世紀(jì)）所著的《幾何原本》，以系統(tǒng)論述幾何學(xué)而著稱，在其中的一卷里，他簡(jiǎn)要地描述了一個(gè)最大公約數(shù)算法。用現(xiàn)代數(shù)學(xué)的術(shù)語來表述，歐幾里得算法基于的方法重復(fù)應(yīng)用下列等式，直到mmodn等于0。 gcd（m，n）=gcd（n，mmodn）（mmodn表示m除以n之后的余數(shù)）

因?yàn)間cd（m，0）=m，m最后的取值也就是m和n的初值的最大公約數(shù)。

舉例來說，gcd（60，24）可以這樣計(jì)算： gcd(60,24)=gcd(24,60mod24)=gcd(24,12) =gcd(12,24mod12)=gcd(12,0)=12

下面是該算法的一個(gè)更加結(jié)構(gòu)化的描述。1.1 算法的概念和描述

用于計(jì)算gcd（m，n）的歐幾里得算法：

第一步：如果n=0，返回m的值作為結(jié)果，同時(shí)函數(shù)結(jié)束；否則，進(jìn)入第二步。

第二步：m除以n，將余數(shù)賦給r。

第三步：將n的值賦給m，將r的值賦給n，返回第一步。

我們也可以使用偽代碼來描述這個(gè)算法：

算法Euclid（m，n） //使用歐幾里得算法計(jì)算gcd（m，n） //輸入∶兩個(gè)不全為0的非負(fù)整數(shù)m，n //輸出∶m，n的最大公約數(shù)

whilen≠0do {r←mmodn m←n n←r } returnm

上面的偽代碼也可以用流程圖來加以描述，如圖1.2所示。圖1.2歐幾里得算法的流程圖1.1 算法的概念和描述

我們?cè)趺粗罋W幾里得算法最終一定會(huì)結(jié)束呢？通過觀察，我們發(fā)現(xiàn)，每經(jīng)過一次循環(huán)，參加運(yùn)算的兩個(gè)算子中的后一個(gè)都會(huì)變得更小，而且絕對(duì)不會(huì)變成負(fù)數(shù)。確實(shí)，下一次循環(huán)時(shí)，n的新值是mmodn，這個(gè)值總是比n小。所以，第二個(gè)算子的值最終會(huì)變成0，此時(shí)，這個(gè)算法也就停止了。

就像其他許多問題—樣，最大公約數(shù)問題也有多種算法。讓我們看看解這個(gè)問題的另外兩種方法。第—個(gè)方法只基于最大公約數(shù)的定義；m和n的最大公約數(shù)就是能夠同時(shí)整除它們的最大正整數(shù)。顯然，這樣一個(gè)公約數(shù)不會(huì)大干兩數(shù)中的較小者，因此，我們先有：t=min{m，n}。現(xiàn)在可以開始檢查t是否能夠整除m和n：如果能，t就是最大公約數(shù)；如果不能，我們就將t減1，然后繼續(xù)嘗試（我們?nèi)绾未_定該算法最終一定會(huì)結(jié)束呢?）。 例如，對(duì)于60和24這兩個(gè)數(shù)來說，該算法會(huì)先嘗試24，然后是23，這樣一值嘗試到12，算法就結(jié)束了。我們給這種算法命名為連續(xù)整數(shù)檢測(cè)算法，下面是該算法的具體描述。 用于計(jì)算gcd（m，n）的連續(xù)整數(shù)檢測(cè)算法∶ 第一步∶將min{m，n}的值賦給t。 第二步∶m除以t，如果余數(shù)為0，進(jìn)入第三步；否則，進(jìn)入第四步。 第三步∶n除以t，如果余數(shù)為0，返回t的值作為結(jié)果；否則，進(jìn)入第四步。 第四步∶把t的值減1。返回第二步。

1.1 算法的概念和描述

注意：和歐幾里得算法不同，按照這個(gè)算法的當(dāng)前形式，當(dāng)它的—個(gè)輸入為0時(shí)，計(jì)算出來的結(jié)果是錯(cuò)誤的。這個(gè)例子說明了為什么必須認(rèn)真、清晰地規(guī)定算法輸入的值域。

求最大公約數(shù)的第三種方法，我們應(yīng)該在中學(xué)時(shí)就很熟悉了。

中學(xué)里計(jì)算gcd（m，n）的方法：

第一步：找到m的所有質(zhì)因數(shù)。

第二步：找到n的所有質(zhì)因數(shù)。

第三步：從第一步和第二步求得的質(zhì)因數(shù)分解式中找出所有的公因數(shù)（如果P是一個(gè)公因數(shù)，而且在m和n的質(zhì)因數(shù)分解式分別出現(xiàn)過Pm和pn次，那么應(yīng)該將P重復(fù)min{pm，pn}次）。

第四步：將第三步中找到的公因數(shù)相乘，其結(jié)果作為給定數(shù)m和n的最大公約數(shù)。

這樣，對(duì)于60和24這兩個(gè)數(shù)，我們得到： 60=2×2×3×5 24=2×2×2×3 gcd(60,24)=2×2×3=12

我們能夠看到，第三種方法比歐幾里得算法要復(fù)雜得多，也慢得多。撇開低劣的性能不談，以這種形式表述的中學(xué)求解過程還不能稱為一個(gè)真正意義上的算法。為什么?因?yàn)槠渲星筚|(zhì)因數(shù)的步驟并沒有明確定義。1.1 算法的概念和描述【1.1.2 算法的描述】

上一節(jié)中，我們已經(jīng)用文字、偽代碼及流程圖分別描述了歐幾里得算法。這是當(dāng)今描述算法的三種最常用的做法。

使用自然語言描述算法顯然很有吸引力，但是自然語言固有的不嚴(yán)密性使得要簡(jiǎn)單清晰地描述算法變得很困難。不過，這也是我們?cè)趯W(xué)習(xí)算法的過程中需要努力掌握的一個(gè)重要技巧。

偽代碼是自然語言和類編程語言組成的混合結(jié)構(gòu)。偽代碼往往比自然語言更精確，而且用偽代碼描述的算法通常會(huì)更簡(jiǎn)潔。令人驚訝的是，計(jì)算機(jī)科學(xué)家從來沒有就偽代碼的形式達(dá)成過共識(shí)，而是讓教材的作者去設(shè)計(jì)他們自己的"方言"。幸運(yùn)的是，這些方言彼此十分相似，任何熟悉一門現(xiàn)代編程語言的人都完全能夠理解。

在計(jì)算機(jī)應(yīng)用早期，描述算法的主要工具是流程圖。流程圖使用一系列相連的幾何圖形來描述算法，幾何圖形內(nèi)部包含對(duì)算法步驟的描述。實(shí)踐證明，除了一些非常簡(jiǎn)單的算法以外，這種表示方法使用起來非常不便。如今，我們只能在早期的算法教材里找到它的蹤影。

本書選擇的描述方式力求不給讀者帶來困難，出于對(duì)簡(jiǎn)單性的偏好，我們忽略了對(duì)變量的定義，并使用了縮進(jìn)來表示for、if和while語句的作用域。正像大家在前一節(jié)里看到的那樣，我們將使用箭頭“←”表示賦值操作，用雙斜線“∥"表示注釋。1.2 算法的時(shí)間復(fù)雜度和空間復(fù)雜度【1.2.1 算法的評(píng)價(jià)】

這正是我們本節(jié)要討論的問題——算法的復(fù)雜度，即估計(jì)、評(píng)價(jià)算法運(yùn)行時(shí)所需要花費(fèi)的時(shí)間及空間。

算法的時(shí)間復(fù)雜度和空間復(fù)雜度合稱為算法的復(fù)雜度。

那么，算法一旦確定，如何計(jì)算它的復(fù)雜度，衡量其優(yōu)劣呢?通常從下面幾個(gè)方面來考慮：

（1）正確性：也稱有效性，是指算法能滿足具體問題的要求。即對(duì)任何合法的輸入，算法都會(huì)得出正確的結(jié)果。確認(rèn)正確性的根本方法是進(jìn)行形式化的證明。但對(duì)一些較復(fù)雜的問題，這是一件相當(dāng)困難的事。許多計(jì)算機(jī)科學(xué)工作者正致力于這方面的研究，目前尚處于初級(jí)階段。因此，實(shí)際中常常用測(cè)試的方法驗(yàn)證算法的正確性。測(cè)試是指用精心選定的輸入（測(cè)試數(shù)據(jù)）去運(yùn)行算法，檢查其結(jié)果是否正確。但正如著名的計(jì)算機(jī)科學(xué)家E.Dijkstra所說的那樣，"測(cè)試只能指出有錯(cuò)誤，而不能指出不存在錯(cuò)誤"。

（2）可讀性：指算法被理解的難易程度。人們常把算法的可讀性放在比較重要的位置，主要是因?yàn)榛逎y懂的算法不易交流和推廣使用，也難以修改、擴(kuò)展與調(diào)試，而且可能隱藏較多的錯(cuò)誤?？勺x性實(shí)質(zhì)上強(qiáng)調(diào)的是越簡(jiǎn)單的東西越美。1.2 算法的時(shí)間復(fù)雜度和空間復(fù)雜度

（3）健壯性：對(duì)非法輸入的抵抗能力。它強(qiáng)調(diào)的是：如果輸入非法數(shù)據(jù)，算法應(yīng)能加以識(shí)別并做出處理，而不是產(chǎn)生誤操作或陷入癱瘓。

（4）時(shí)間復(fù)雜度與空間復(fù)雜度。時(shí)間復(fù)雜度是算法的計(jì)算復(fù)雜性的時(shí)間度量，粗略地講，就是該算法的運(yùn)行時(shí)間。同一個(gè)問題，不同的算法可能有不同的時(shí)間復(fù)雜度。問題規(guī)模較大時(shí)，時(shí)間復(fù)雜度就變得十分重要。盡管計(jì)算機(jī)的運(yùn)行速度提高很快，但這種提高無法滿足問題規(guī)模加大帶來的速度要求。所以追求高速算法仍然是件重要的事情。空間復(fù)雜度是指算法運(yùn)行所需的存儲(chǔ)空間的多少。相比起來，人們一般會(huì)更多地關(guān)注算法的時(shí)間復(fù)雜度，但這并不是因?yàn)橛?jì)算機(jī)的存儲(chǔ)空間是海量的，而是由人們面臨的問題的本質(zhì)決定的。時(shí)間復(fù)雜度與空間復(fù)雜度往往是一對(duì)矛盾。常?？梢杂每臻g換取速度，反之亦然。1.2 算法的時(shí)間復(fù)雜度和空間復(fù)雜度【1.2.2 算法的時(shí)間復(fù)雜度】

給定一個(gè)算法，如何確定該算法的時(shí)間復(fù)雜度呢?我們可以采用事后統(tǒng)計(jì)的辦法得出執(zhí)行算法所用的具體時(shí)間。因?yàn)楹芏嘤?jì)算機(jī)都有這種計(jì)時(shí)的功能，甚至可以獲取精確到毫秒級(jí)的統(tǒng)計(jì)數(shù)據(jù)。但這種辦法有兩個(gè)缺陷：第一，必須先運(yùn)行才能分辨出算法的好壞;第二，所得的時(shí)間的統(tǒng)計(jì)量過分依賴于計(jì)算機(jī)的硬件、軟件等環(huán)境因素，這些因素容易掩蓋算法本身的優(yōu)劣，因?yàn)橐粋€(gè)笨拙的算法在先進(jìn)的大型機(jī)上運(yùn)行可能比一個(gè)同功能的優(yōu)化算法在微型機(jī)上運(yùn)行更省時(shí)間。

因此，人們常常對(duì)算法進(jìn)行事前的時(shí)間估算?？衫谜Z句的"頻度"和算法的漸進(jìn)時(shí)間復(fù)雜度這兩個(gè)與軟、硬件無關(guān)的度量來討論算法執(zhí)行的時(shí)間消耗。

設(shè)n稱為問題的規(guī)模，當(dāng)n不斷變化時(shí)，算法中的基本語句執(zhí)行的頻度（我們且稱為時(shí)間頻度）T（n）也會(huì)不斷變化。一般情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個(gè)函數(shù)，用T（n）表示，若有某個(gè)輔助函數(shù)f（n），使得當(dāng)n趨近于無窮大時(shí)，T（n）/f（n）的極限值為不等于零的常數(shù)，則稱f（n）是T（n）的同數(shù)量級(jí)函數(shù)。記作T（n）=O（f(n)），稱O（f(n)）為算法的漸進(jìn)時(shí)間復(fù)雜度，簡(jiǎn)稱時(shí)間復(fù)雜度。

時(shí)間頻度不同，但時(shí)間復(fù)雜度可能相同。如： T（n）=n2＋3n+4與T（n）=4n2＋2n＋1它們的頻度不同，但時(shí)間復(fù)雜度相同，都為O（n2）。

1.2 算法的時(shí)間復(fù)雜度和空間復(fù)雜度

用兩個(gè)算法A1和A2來求解同一問題，時(shí)間復(fù)雜度分別是T1（n）=100n2，T2（n）=5n3。

（1）當(dāng)輸入量n<20時(shí)，有T1（n）>T2（n），后者花費(fèi)的時(shí)間較少。

（2）隨著問題規(guī)模n的增大，兩個(gè)算法的時(shí)間開銷之比5n3/100n2=n/20亦隨著增大。即當(dāng)問題規(guī)模較大時(shí)，算法Al比算法A要有效得多。它們的漸近時(shí)間復(fù)雜度O（n2）和O（n3）從宏觀上評(píng)價(jià)了這兩個(gè)算法在時(shí)間方面的質(zhì)量。在算法分析時(shí)，往往對(duì)算法的時(shí)間復(fù)雜度和漸近時(shí)間復(fù)雜度不予區(qū)分，而經(jīng)常是將漸近時(shí)間復(fù)雜度T（n）=O（f（n））簡(jiǎn)稱為時(shí)間復(fù)雜度，其中的f（n）一般是算法中頻度最大的語句的頻度。

研究算法的時(shí)間復(fù)雜度，通?？紤]的是算法在最壞情況下的時(shí)間復(fù)雜度。稱為最壞時(shí)間復(fù)雜度。一般不特別說明，討論的時(shí)間復(fù)雜度均是最壞情況下的時(shí)間復(fù)雜度。這樣做的原因是;最壞情況下的時(shí)間復(fù)雜度T（n）=O（n），是算法在任何輸入實(shí)例上運(yùn)行時(shí)間的上界，即它表示對(duì)于任何輸入實(shí)例，該算法的運(yùn)行時(shí)間不可能大于O（n）。

另一個(gè)衡量算法復(fù)雜度的指標(biāo)是平均時(shí)間復(fù)雜度，它是指所有可能的輸入實(shí)例均以等概率出現(xiàn)的情況下，算法的期望運(yùn)行時(shí)間。1.2 算法的時(shí)間復(fù)雜度和空間復(fù)雜度1.2 算法的時(shí)間復(fù)雜度和空間復(fù)雜度1.2 算法的時(shí)間復(fù)雜度和空間復(fù)雜度1.2 算法的時(shí)間復(fù)雜度和空間復(fù)雜度

（4）算法的時(shí)間復(fù)雜度不僅僅依賴于問題的規(guī)模，還與輸入實(shí)例的初始狀態(tài)有關(guān)。例如： i=1； while(i＜n)and(x≠a[i]) #i=i+1； ifa[i]=xthenreturn(i)

此程序段中語句#的頻度不僅是n的函數(shù)，而且與x及數(shù)組a中各元素的具體值有關(guān)，在這種情況下，通常按最壞的情況考慮。由于while循環(huán)執(zhí)行的最大次數(shù)為n—1，則語句#的頻度的最大值為f（n）=n—1，則認(rèn)為此程序段的時(shí)間復(fù)雜度為T（n）=O（n）。

（5）遞歸算法的頻度不容易估算，須由遞推公式計(jì)算求得。其基本方法是：方程右邊較小的項(xiàng)根據(jù)定義被依次替代，如此反復(fù)擴(kuò)展，直到得到一個(gè)沒有遞歸式的完整數(shù)列，從而將復(fù)雜的遞歸問題轉(zhuǎn)化為了新的求和問題。以有名的Hanoi塔問題為例，其解是一個(gè)遞歸形式的算法： void hanoi（intn,charA,charB,charC)

｛ if(n==1)move(n,A,C)； else

｛hanoi(n—1,A,C,B)； move(n,A,C)； hanoi(n-1,B,A,C)；

｝

｝1.2 算法的時(shí)間復(fù)雜度和空間復(fù)雜度

顯見問題的規(guī)模是n，move（n，A，C）語句的頻度為1，若整個(gè)算法的頻度為f（n），則遞歸調(diào)用hanoi（n—1，A，C，B）和hanoi（n—1，B，A，C）語句的頻度應(yīng)為f（n一1），于是有

f(n)=f(n—1)＋1＋f(n—1)即

f(n)=2f(n—1)＋1,進(jìn)行遞推，有

f(n)=2(2f(n—2)＋1)＋1 =4f(n—2)＋3 =4(2f(n—3)＋1)＋3 =8f（n一3）十7 … =2kf(n—k)＋2k—1

當(dāng)n=k＋1時(shí)，f（n）=2n—1f（1）＋2n—1—1。

f（1）是n=1時(shí)算法的頻度，它只有move（n，A，C）語句，其值為1。最后得到f（n）=2n—1。時(shí)間復(fù)雜度T（n）=O（2n）。1.2 算法的時(shí)間復(fù)雜度和空間復(fù)雜度 總之，頻度和時(shí)間復(fù)雜度雖不能精確地確定一個(gè)算法或程序的執(zhí)行時(shí)間，但可以讓人們知道隨著問題的規(guī)模增大，算法耗用時(shí)間的增長(zhǎng)趨勢(shì)。由于討論算法的好壞不是針對(duì)某個(gè)特定大小的問題（這樣做本身沒有意義），因此，時(shí)間復(fù)雜度對(duì)算法來說是一個(gè)較恰當(dāng)?shù)牧慷取?較常見的時(shí)間復(fù)雜度有O（1）（常量型）、O（n）、O（n2）、…、O（nk）（多項(xiàng)式型）、O（lbn）、O（nlbn）（對(duì)數(shù)型）和O（n!）（階乘型）。顯然，時(shí)間復(fù)雜度為O（2n）或O（en）的指數(shù)型算法的效率極低，在n較大時(shí)無法實(shí)用。如圖1.3所示表明了各種時(shí)間復(fù)雜度的增長(zhǎng)率。圖1.3各種時(shí)間復(fù)雜度的增長(zhǎng)率1.2 算法的時(shí)間復(fù)雜度和空間復(fù)雜度

表1.1是我們所熟悉的各種排序算法的復(fù)雜度，讀者可以分析思考。表1.1常用排序算法的時(shí)間復(fù)雜度和空間復(fù)雜度 實(shí)踐中我們可以把事前估算和事后統(tǒng)計(jì)兩種辦法結(jié)合起來使用，例如，若上機(jī)運(yùn)行一個(gè)10×10矩陣模型，執(zhí)行時(shí)間為12ms，則由算法的時(shí)間復(fù)雜度T（n）=O（n3）可估算一個(gè)31×31矩陣自乘的時(shí)間大約為（31/10）3×12ms≈358ms。這種辦法很有實(shí)用價(jià)值，它用小模型可推得大尺寸問題的耗用機(jī)時(shí)。1.2 算法的時(shí)間復(fù)雜度和空間復(fù)雜度1.2 算法的時(shí)間復(fù)雜度和空間復(fù)雜度

可見，這個(gè)簡(jiǎn)單的遞歸算法雖然正確，但卻毫無效率。那么，fibl算法能改進(jìn)嗎?

首先，我們分析fib1算法為什么如此之慢呢?如圖1.4所示提示了由一個(gè)單獨(dú)的fib1（n）調(diào)用過程觸發(fā)的一系列遞歸操作。請(qǐng)注意很多計(jì)算步驟都是重復(fù)的！圖1.4fib1（n）遞歸調(diào)用的擴(kuò)張過程1.2 算法的時(shí)間復(fù)雜度和空間復(fù)雜度

正是由于重復(fù)計(jì)算才導(dǎo)致了fibl算法如此之慢。一種更合理的算法是隨時(shí)存儲(chǔ)中間計(jì)算結(jié)果——F0，F(xiàn)1，…，F(xiàn)n-1的值。

voidfib2(intn)

｛

if(n==0)return0；

f[0]=0；f[1]=1；

fori=2tondo f[i]=f[i—1]+f[i—2]；

returnf[n]； ｝ 與fibl算法一樣，由于該算法直接應(yīng)用了Fn的定義，其正確性是顯而易見的。那么它的時(shí)間復(fù)雜度如何呢?由于其內(nèi)層循環(huán)內(nèi)包含了一個(gè)單獨(dú)的操作，并且執(zhí)行了n—1次，因此，fib2的操作次數(shù)n是線性的。這就是說，現(xiàn)在我們從fibl的指數(shù)時(shí)間降至fib2的多項(xiàng)式時(shí)間，我們?cè)跁r(shí)間復(fù)雜度上取得了巨大的突破?，F(xiàn)在我們完全可以在可接受的時(shí)間內(nèi)計(jì)算F200，甚至更大的n了。

由此可見，一個(gè)好的算法將使問題的解決變得完全不同。1.2 算法的時(shí)間復(fù)雜度和空間復(fù)雜度【1.2.3 算法的空間復(fù)雜度】

空間復(fù)雜度（SpaceComplexity）是對(duì)一個(gè)算法在運(yùn)行過程中臨時(shí)占用存儲(chǔ)空間大小的量度，它也是問題規(guī)模n的函數(shù)。一個(gè)算法在計(jì)算機(jī)存儲(chǔ)器上所占用的存儲(chǔ)空間，包括存儲(chǔ)算法本身所占用的存儲(chǔ)空間，算法的輸入/輸出數(shù)據(jù)所占用的存儲(chǔ)空間和算法在運(yùn)行過程中臨時(shí)占用的存儲(chǔ)空間這三個(gè)方面。

（1）固定部分。這部分空間的大小與輸入/輸出的數(shù)據(jù)的個(gè)數(shù)多少、數(shù)值無關(guān)。其主要包括指令空間（即代碼空間）、數(shù)據(jù)空間（常量、簡(jiǎn)單變量）等所占的空間。這部分屬于靜態(tài)空間。

（2）可變空間。這部分空間主要包括動(dòng)態(tài)分配的空間以及遞歸棧所需的空間等。這部分的空間大小與算法有關(guān)。

一個(gè)算法所需的存儲(chǔ)空間用f（n）表示。S（n）=O（f（n）），其中n為問題的規(guī)模，S（n）表示空間復(fù)雜度。

算法的輸入/輸出數(shù)據(jù)所占用的存儲(chǔ)空間是由要解決的問題決定的，它不隨著算法的不同而改變。存儲(chǔ)算法本身所占用的存儲(chǔ)空間與算法書寫的長(zhǎng)短成正比，要壓縮這方面的存儲(chǔ)空間，就必須編寫出較短的算法。算法在運(yùn)行過程中臨時(shí)占用的存儲(chǔ)空間隨算法的不同而異，有的算法只需要占用少量的臨時(shí)工作單元，而且不隨問題規(guī)模的大小而改變，是節(jié)省存儲(chǔ)空間的算法，可表示為O（1）。O（1）是說算法規(guī)模和臨時(shí)變量數(shù)目無關(guān)，并不是說僅僅定義一個(gè)臨時(shí)變量。第二章

常用算法2.1 遞歸法2.2 分治法2.3 貪心法2.4 搜索法與回溯法【2.1.1 遞歸的概念與基本思想】

遞歸（Recursion）即是一個(gè)函數(shù)直接或間接調(diào)用自己本身的過程。使用遞歸時(shí)必須符合以下三個(gè)條件：

①可將一個(gè)問題轉(zhuǎn)化為新問題，而新問題的解決方法仍然與原問題的方法相同，只不過所處理的對(duì)象不同而已，即它們只是規(guī)律的遞增和遞減。

②可以通過轉(zhuǎn)化過程使問題回到對(duì)原問題的求解。

③必須要有一個(gè)明確的遞歸結(jié)束條件，否則遞歸會(huì)無休止地進(jìn)行下去。遞歸的思想就是把復(fù)雜的問題層層分解成簡(jiǎn)單的問題去解決。 我們用幾個(gè)經(jīng)典例子說明遞歸的思想。 階乘函數(shù)f（n）=n！按照遞歸的思想可以定義為

f(0)=1, n=0 f(n)=f(n—1)×n, n＞0

對(duì)應(yīng)的遞歸函數(shù)：

intf(intn)

｛

if(n==0) return1；

2.1 遞歸法 else returnf(n—1)*n；

｝ 斐波那契數(shù)列按照遞歸的思想可以定義為：

f(1)=1， n=1 f(2)=1， n=2 f(n)=f(n—1)＋f(n—2), n＞2

對(duì)應(yīng)的遞歸函數(shù)：

intf(intn)

｛

if(n==1) return1；

if(n==2) return1；

else returnf(n—1)+f(n—2)； ｝2.1 遞歸法【2.1.2 遞歸法的應(yīng)用】【例2.1】計(jì)算兩個(gè)數(shù)的最大公約數(shù)?！舅惴ǚ治觥课覀冇胓cd（n，m）來表示兩個(gè)數(shù)的最大公約數(shù)，那么我們有公式∶gcd（n，m）=gcd（m，n—m）進(jìn)而我們可以按照遞歸的思想寫出新的公式∶gcd(n,m)=gcd(m,n%m)有了這個(gè)公式我們就可以寫出程序了?！驹O(shè)計(jì)技巧】可以利用?∶表達(dá)式來簡(jiǎn)化程序?！境绦?qū)崿F(xiàn)】下面是用if語句完成的程序。 /* prog:gcd lang∶c＋＋

*/ #include＜iostream＞ usingnamespacestd； intgcd（inta,intb）2.1 遞歸法

｛

if（b==0）

returna；

else returngcd（b，a%b）；

｝ intmain（）

｛ inta，b；

cin＞＞a＞＞b；

cout＜＜gcd（a，b）＜＜endl；

return0；

｝2.1 遞歸法下面是用？：表達(dá)式完成的程序。 /* prog：gcd lang：c＋＋

*/ #include＜iostream＞ usingnamespacestd； intgcd（inta，intb）

｛

returnb==0？a：gcd（b，a%b）；

｝ intmain（）｛ inta，b；

cin＞＞a＞＞b；

cout＜＜gcd（a，b）＜＜endl； return0；

｝2.1 遞歸法

【例2.2】將十進(jìn)制正整數(shù)n轉(zhuǎn)化為m進(jìn)制數(shù)。2≤m≤20。

【算法分析】連續(xù)除以m直到商為0，從底向上記錄余數(shù)即可得到結(jié)果。 如圖2.1所示，將12轉(zhuǎn)化為2進(jìn)制數(shù)，（12）10=（1100）2

觀察這個(gè)過程，它就是一個(gè)遞歸的過程，遞歸的邊界條件是當(dāng)前數(shù)為0，只需按照上圖的思路設(shè)計(jì)程序即可。

【設(shè)計(jì)技巧】需要注意n=0時(shí)是特殊情況，需要特殊處理保證程序的正確性。

可以提前存儲(chǔ)代碼，減少程序代碼量。 在遞歸更深層結(jié)束后再將這一層對(duì)應(yīng)的余數(shù)加入答案，即回溯時(shí)再將這一層的余數(shù)加人答案。

【程序?qū)崿F(xiàn)】 /* prog：進(jìn)制轉(zhuǎn)換

lang：c＋＋ */ #include＜iostreanm＞

usingnamespacestd；

stringNum[20]；

stringS； voidPreWork（void）

2.1 遞歸法圖2.112轉(zhuǎn)換為2進(jìn)制數(shù) ｛ for（inti=0；i＜20；i＋＋）Num[i]="." for（inti=0；i＜10；i＋＋Num[i][0]=（char）（′0′＋i）；

for（inti=10；i＜20；i＋＋）Num[i][0]=（char）（′A′＋i—10）； ｝

voidNemberConver（intn，intm） ｛ if（n==0）return；

NumberConver（n/m，m）；

S＋=Num[n%m]； ｝

intmain（） ｛ intn，m；

cin＞＞n＞＞m；

id（n==0）cout＜＜0＜＜endl；

else

｛ PreWork（）；

NumberConver（n，m）；

cout＜＜S＜＜endl； ｝

return0； ｝2.1 遞歸法【2.2.1 分治的概念與基本思想】 分治法是一種很重要的算法。字面上的解釋是“分而治之”，其基本思想就是把一個(gè)復(fù)雜的問題分成兩個(gè)或更多的相同或相似的子問題，再把子問題分成更小的子問題，直到最后子問題可以簡(jiǎn)單的直接求解，原問題的解即子問題的解的合并。這個(gè)技巧是很多高效算法的基礎(chǔ)，如排序算法（快速排序，歸并排序），傅立葉變換（快速傅立葉變換）。 任何一個(gè)可以用計(jì)算機(jī)求解的問題所需的計(jì)算時(shí)間都與其規(guī)模有關(guān)。問題的規(guī)模越小，越容易直接求解，解題所需的計(jì)算時(shí)間也越少。例如，對(duì)于n個(gè)元素的排序問題，當(dāng)n=1時(shí)，不需任何計(jì)算；n=2時(shí)，只要作一次比較即可排好順序；n=3時(shí)只要作三次比較即可。而當(dāng)n較大時(shí)，問題就不那么容易處理了，要想直接解決一個(gè)規(guī)模較大的問題，有時(shí)是相當(dāng)困難的。

分治法的設(shè)計(jì)思想：將一個(gè)難以直接解決的大問題，分割成一些規(guī)模較小的相同問題，以便各個(gè)擊破，分而治之。

分治策略：對(duì)于一個(gè)規(guī)模為n的問題，若該問題可以容易地解決（比如說規(guī)模n較小）則直接解決，否則將其分解為k個(gè)規(guī)模較小的子問題，這些子問題互相獨(dú)立且與原問題形式相同，遞歸地解這些子問題，然后將各子問題的解合并得到原問題的解。這種算法設(shè)計(jì)策略叫做分治法。2.2 分治法 分治法所能解決的問題一般具有以下幾個(gè)特征： （1）該問題的規(guī)?？s小到一定的程度就可以容易地解決。 （2）該問題可以分解為若干個(gè)規(guī)模較小的相同問題，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。 （3）利用該問題分解出的子問題的解可以合并為該問題的解。 （4）該問題所分解出的各個(gè)子問題是相互獨(dú)立的，即子問題之間不包含公共的子問題。 上述的第一條特征是絕大多數(shù)問題都可以滿足的，因?yàn)閱栴}的計(jì)算復(fù)雜性一般是隨著問題規(guī)模的增加而增加;第二條特征是應(yīng)用分治法的前提它也是大多數(shù)問題可以滿足的，此特征反映了遞歸思想的應(yīng)用;第三條特征是關(guān)鍵，能否利用分治法完全取決于問題是否具有第三條特征，如果具備了第一條和第二條特征，而不具備第三條特征，則可以考慮用貪心法或動(dòng)態(tài)規(guī)劃法。第四條特征涉及到分治法的效率，如果各子問題是不獨(dú)立的則分治法要做許多不必要的工作，重復(fù)地解公共的子問題，此時(shí)雖然可用分治法，但一般用動(dòng)態(tài)規(guī)劃法較好。 分治法的基本步驟。 分治法在每一層遞歸上都有三個(gè)步驟： （1）分解：將原問題分解為若干個(gè)規(guī)模較小、相互獨(dú)立并且與原問題形式相同的子問題； （2）解決：若子問題規(guī)模較小而容易被解決則直接解，否則遞歸地解各個(gè)子問題； （3）合并：將各個(gè)子問題的解合并為原問題的解。 它的一般的算法設(shè)計(jì)模式如下：

Divide—and—Conquer（P） ①if|P|≤n0；2.2 分治法 ②thenreturn（ADHOC（P））； ③將P分解為較小的子問題P1，P2，…，Pk； ④fori←1tok； ⑤doyi←Divide—and—Conquer（Pi）；

∥遞歸解決Pi ⑥T←MERGE（y1，y2，…，yk）； ∥合并子問題 ⑦return（T）。

其中|P|表示問題P的規(guī)模；n0為一閾值，表示當(dāng)問題P的規(guī)模不超過n0時(shí)，問題已容易直接解出，不必再繼續(xù)分解。ADHOC（P）是該分治法中的基本子算法，用于直接解小規(guī)模的問題P。因此，當(dāng)P的規(guī)模不超過n0時(shí)直接用算法ADHOC（P）求解。算法MERGE（y1，y2，…，yk）是該分治法中的合并子算法，用于將P的子問題P1，P2，…，Pk的相應(yīng)的解yl，y2，…，yk合并為P的解。

分治法的過程如圖2.2所示。2.2 分治法圖2.2分治法的過程 實(shí)際中分治法的應(yīng)用很廣泛，信息學(xué)競(jìng)賽中有很多經(jīng)典的應(yīng)用。例如，歸并排序算法、快速排序算法和二分查找算法。下面我們介紹歸并排序算法和二分查找算法來更詳細(xì)的解釋分治法。

1.歸并排序算法 歸并排序是一種利用了分治法的排序算法。其可以分為三個(gè)步驟： ①將序列分為規(guī)模相等的兩部分。 ②對(duì)兩部分分別進(jìn)行排序。 ③將已經(jīng)排過序的兩部分整合起來得到有序的原序列。 其中②可以繼續(xù)遞歸下去處理，整個(gè)遞歸樹只有O（lnn）層，故如果我們能在O（n）時(shí)間復(fù)雜度內(nèi)完成③，則整個(gè)算法時(shí)間復(fù)雜度為O（nlnn）。 歸并排序非常巧妙的應(yīng)用了分治法，將原序列排序這個(gè)大問題，層層分治最后變成容易解決的小規(guī)模問題。歸并排序是分治法的經(jīng)典應(yīng)用之一。

下面給出歸并排序算法的程序： /* prog：mergesort lang：c＋＋

*/ #include＜iostream＞

#include＜cstdio＞

usingnamespacestd；2.2 分治法 constintmaxn=100005；

intn，A[maxn]，tmp_A[maxn]；

voidMergeSort（int1，intr） ｛

if（1==r）return；

intmid=（1+r）＞＞1；

MergeSort（1，mid）；

MergeSort（mid+1，r）；

intp1=1，p2=mid+1；

for（inti=1；i＜=r；i++） ｛

if（p1＞mid）tmp_A[i]=A[p2]，p2++；

else

｛if（p2＞r）tmp_A[i]=A[P1]，p1++；

else

｛if（A[p1]＜A[p2]）tmp_A[i]=A[p1]，p1++；

elsetmp_A[i]=A[p2]，p2++；

｝ ｝

2.2 分治法 ｝

for（inti=1；i＜=r；i++）A[i]=tmp_A[i]；｝intmain（）｛ cin＞＞n；

for（inti=0；i＜n；i++）scanf（"%d"，&A[i]）；

MergeSort（0，n—1）；

for（inti=0；i＜n；i++）printf（"%d%c"，A[i]，i==n—1？′\n′：′′）；

return0；

｝2.2 分治法 2.二分查找算法

現(xiàn)在有一個(gè)嚴(yán)格單調(diào)遞增數(shù)列，要求在其中查找元素X（保證X一定存在）。數(shù)列中有n個(gè)數(shù)。 我們把數(shù)列從頭到尾查找一遍，時(shí)間復(fù)雜度O（n）。但是沒有用到嚴(yán)格單調(diào)遞增這個(gè)條件，利用二分查找算法可以在時(shí)間復(fù)雜度O（lnn）內(nèi)解決問題。 二分查找算法可以分為三個(gè)部分： ①如果當(dāng)前區(qū)間只有一個(gè)數(shù)，那么必然是要查找的數(shù)。 ②將要查找的數(shù)與區(qū)間最中間的數(shù)進(jìn)行比較，根據(jù)區(qū)間單調(diào)性可以確定要查找的數(shù)在左半部分區(qū)間還是在右半部分區(qū)間。 ③在新的區(qū)間內(nèi)繼續(xù)查找。 下面給出二分查找算法的程序：2.2 分治法2.2 分治法【2.2.2 分治法的應(yīng)用】

【例2.4】比賽安排（NOIP1996提高組）。 設(shè)有2n（n≤6）個(gè)球隊(duì)進(jìn)行單循環(huán)比賽，計(jì)劃在2n一1天內(nèi)完成，每個(gè)隊(duì)每天進(jìn)行一場(chǎng)比賽，且在2n一1天內(nèi)每個(gè)隊(duì)都與不同的對(duì)手比賽。請(qǐng)編寫程序設(shè)計(jì)比賽安排表并按下表的格式輸出。 例如下面是n=2時(shí)的比賽安排表，見表2.1。表2.1n=2時(shí)的比賽安排表【算法分析】題目貌似很難下手，我們不妨嘗試一下找規(guī)律。

下面是n=1時(shí)的比賽安排表，見表2.2。2.2 分治法

表2.2n=1時(shí)的比賽安排表 對(duì)比兩個(gè)表，我們?nèi)菀装l(fā)現(xiàn)規(guī)律： ①表2.1的左上角與右下角和表2.2一樣。 ②表2.1的左下角和右上角一樣，且是表2.2每個(gè)值均加上2得到。 按照這兩個(gè)規(guī)律我們可以構(gòu)造出n=3時(shí)的比賽安排表，注意這里要加上22，見表2.3。表2.3n=3時(shí)的比賽安排表2.2 分治法2.2 分治法2.2 分治法【2.3.1 貪心的概念與基本思想】 貪心法是解決一類最優(yōu)問題的策略。這種算法只選擇當(dāng)前局部看起來的最佳策略，而不去考慮整體來講是否是最佳策略。正確的貪心算法應(yīng)保證貪心策略的無后效性（即某個(gè)狀態(tài)以后的過程不影響以前的狀態(tài)，只和當(dāng)前狀態(tài)有關(guān)）。

貪心法不能保證對(duì)所有問題均適用，但對(duì)很多最優(yōu)解的問題適用。

可以應(yīng)用貪心法的題目必須具備貪心選擇和最優(yōu)子結(jié)構(gòu)兩種性質(zhì)。所謂貪心選擇性質(zhì)，是指所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來達(dá)到。貪心選擇是貪心法的核心，我們求整體最優(yōu)解的時(shí)候可以通過一系列局部最優(yōu)的選擇來達(dá)到，即我們可以迭代的選擇局部最優(yōu)選擇來得到全局最優(yōu)解。怎么去設(shè)計(jì)貪心選擇是貪心法的關(guān)鍵。最優(yōu)子結(jié)構(gòu)性質(zhì)，是指一個(gè)問題的最優(yōu)解包含其子問題的最優(yōu)解。問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題可用貪心算法求解的關(guān)鍵特征。

程序設(shè)計(jì)中，貪心算法的問題枚不勝數(shù)，且問題類型變化也很多，是信息學(xué)競(jìng)賽的一個(gè)難點(diǎn)。貪心算法的經(jīng)典應(yīng)用有單源最短路徑的Dijkstra算法（我們將在第5章介紹這種算法）、求解最小生成樹的Prim算法及Kruskal算法（我們將在第5章介紹這種算法）。很多時(shí)候貪心算法并不能保證正確性，但往往通過與隨機(jī)算法的結(jié)合可以得到靠近最優(yōu)解的近似算法，例如遺傳算法、模擬退火算法。對(duì)于這一類問題，通過一定的數(shù)學(xué)推導(dǎo)之后可以用貪心算法解決，這是貪心算法和數(shù)學(xué)的結(jié)合。

貪心算法類型繁多，我們主要通過例題來說明貪心算法的應(yīng)用。2.3 貪心法【2.3.2 貪心法的應(yīng)用】

【例2.7】背包問題。 給定背包的容量為W，給定n（n≤105）件物品，第i件物品的體積是w[i]，問背包至多能裝多少件物品?

【算法分析】顯然，背包的剩余的容量越大能裝的物品數(shù)越多。根據(jù)題意，每個(gè)物品除了體積以外沒有區(qū)別。那么我們可以得到以下貪心策略。 （1）將物品按體積從小到大排序。 （2）從體積最小的開始依次放入背包，直到背包不再能裝物品為止。

【設(shè)計(jì)技巧】排序可以應(yīng)用algorithm庫中的sort函數(shù)。

【程序?qū)崿F(xiàn)】

/* prog：背包問題

lang：c++ */ #include＜iostream＞

#include＜cstdio＞

#include＜algorithm＞2.3 貪心法 usingnamespacestd； constintmaxn=100005； intw[maxn]； intmain（）

｝

intn，W；

cin＞＞n＞＞W(wǎng)；

for(inti=0；i＜n；i++)scanf("%d"，&w[i])；

sort（w，w+n）；

intres=0；

for(inti=0；i＜n&&W＞=w[i]；i++)res++，W—=w[i]；

cout＜＜res＜＜endl；

return0；

｝2.3 貪心法

【例2.8】線段。 在數(shù)軸上有n（n≤105）個(gè)線段，編號(hào)從0到n—1，第i條線段的左端點(diǎn)坐標(biāo)為L(zhǎng)[i]、右端點(diǎn)坐標(biāo)為R[i]，且滿足對(duì)于任意的i，j∈[0，n—1]，i≠j都不滿足L[i]≤L[j]且R[i]≥R[j]（即不存在兩個(gè)線段滿足包含關(guān)系）。要求在數(shù)軸上選擇盡量少的點(diǎn)使得這個(gè)線段每個(gè)線段內(nèi)均有被選擇的點(diǎn)。 即求最小的K滿足K≤n且存在｛b1，b2，…，bk｝使得對(duì)于任意i∈[0，n—1]均存在j∈[1，K]使得L[i]≤b[j]≤R[i]，輸出最少要用多少個(gè)點(diǎn)即可。

【算法分析】將n個(gè)線段按照左端點(diǎn)坐標(biāo)升序排序，下面證明這時(shí)右端點(diǎn)坐標(biāo)為升序。 證明 我們利用反證法來證明這個(gè)結(jié)論。 若排序后存在i，j∈[0，n—1]且i＜j，R[i]≥R[j]。 即存在i，j∈[0，n—1]且L[i]≤L[j]，R[i]≥R[j]。 矛盾。故排序后右端點(diǎn)坐標(biāo)也為升序。 證畢。 這時(shí)我們得到了n個(gè)左右端點(diǎn)都升序的線段，如圖2.8所示：圖2.8 線段2.3 貪心法 設(shè)f[i]為最少需要多少個(gè)點(diǎn)才能"覆蓋"第i條線段到第n一1條線段（這里的編號(hào)是排序之后的編號(hào)）。那么f[0]就是我們要求的答案。 如果我們要求f[i]，那么先選擇R[i]這個(gè)點(diǎn)，如果此時(shí)編號(hào)從i到n一1的線段均被"覆蓋"則f[i]=1。否則找到編號(hào)最小的不被"覆蓋"的線段j，那么f[i]=f[j]＋1。 這樣我們?cè)谪澬牟呗缘幕A(chǔ)上得到了遞推式。下面我們來證明這樣的貪心策略是正確的。

證明 如果選擇R[i]這個(gè)點(diǎn)編號(hào)從i到n—1的線段均被"覆蓋"，那么這一定是最優(yōu)方案。我們只需討論不能全部被"覆蓋"的情況。 顯然，f[i]是不下降的序列，那么我們只需要證明選擇R[i]這個(gè)點(diǎn)能使得遞推式中的j最小即可。 因?yàn)檫@n條線段左右端點(diǎn)均單調(diào)遞增。顯然選擇R[i]這個(gè)點(diǎn)能使得遞推式中的j最小。 證畢。 因?yàn)閿?shù)據(jù)規(guī)模較大，這里的值要用二分法求出。 總時(shí)間復(fù)雜度O（nlnn）。

【設(shè)計(jì)技巧】我們需要倒著去求f數(shù)組。排序可以用algorithm庫中sort函數(shù)。 【程序?qū)崿F(xiàn)】 /* prog：segmemt lang：c++ */2.3 貪心法2.3 貪心法2.3 貪心法【2.4.1 搜索與回溯的概念與基本思想】

搜索算法如同其字面意思，即窮舉所有的可能情況去解決問題，搜索算法的復(fù)雜度往往是指數(shù)級(jí)，數(shù)據(jù)規(guī)模稍大運(yùn)算時(shí)間可能就會(huì)是天文數(shù)字，但搜索算法往往是解決問題最直接的方式。有些問題沒有更優(yōu)秀的方法只能應(yīng)用搜索算法解決問題。搜索算法往往也用作和其他算法相互配合解決問題。

搜索算法的實(shí)質(zhì)就是構(gòu)造一個(gè)“搜索樹”，這個(gè)“搜索樹”表達(dá)了整個(gè)搜索算法的過程。搜索算法從一個(gè)初始狀態(tài)出發(fā)根據(jù)一定的擴(kuò)展規(guī)則來進(jìn)行搜索過程，最后形成的整個(gè)過程就是一個(gè)“搜索樹”。也就相當(dāng)于我們將一個(gè)問題的解決過程已經(jīng)抽象成了圖論中的模型——樹，即我們的搜索算法相當(dāng)于在這個(gè)樹上進(jìn)行某種形式的遍歷，如圖2.9所示。圖2.9 搜索樹2.4 搜索法與回溯法 一種搜索算法相當(dāng)于樹的遍歷，通常我們有兩種實(shí)現(xiàn)方式，深度優(yōu)先搜索（簡(jiǎn)稱DFS）和廣度優(yōu)先搜索（簡(jiǎn)稱BFS）。 回溯算法的基本思想是：為了求得待解問題的解，我們先選擇一種可能的情況向前搜索，一旦發(fā)現(xiàn)原來的選擇是錯(cuò)誤（也就是這種選擇會(huì)導(dǎo)致問題無解）就退回來重新選擇，如此反復(fù)進(jìn)行。直到得到問題的解，或者在窮舉完所有情況后，判斷原問題無解。 下面我們來介紹深度優(yōu)先搜索和廣度優(yōu)先搜索： （1）深度優(yōu)先搜索。顧名思義，深度優(yōu)先搜索即是深度優(yōu)先的搜索算法，即在搜索樹上優(yōu)先深度遍歷。深度優(yōu)先搜索通常用遞歸法的方法實(shí)現(xiàn)。 （2）廣度優(yōu)先搜索。對(duì)比深度優(yōu)先搜索，廣度優(yōu)先搜索是以廣度優(yōu)先的搜索算法，即在搜索樹上一層層遍歷，第0層和第1層全部遍歷完才會(huì)遍歷第2層，廣度優(yōu)先搜索通常用循環(huán)結(jié)構(gòu)就可以實(shí)現(xiàn)。 對(duì)比這兩種搜索算法，我們發(fā)現(xiàn)深度優(yōu)先搜索是以棧結(jié)構(gòu)為基礎(chǔ)的搜索算法，而廣度優(yōu)先搜索是以隊(duì)列結(jié)構(gòu)為基礎(chǔ)的搜索算法。2.4 搜索法與回溯法【2.4.2 搜索法與回溯法的應(yīng)用】

【例2.11】跳馬。 如圖2.10所示的5×5的棋盤上，從左下角的方格出發(fā)，按照日字跳馬，要求不重復(fù)地跳過所有方格。輸出方案數(shù)。

【算法分析】用窗口坐標(biāo)系表示棋盤上的每個(gè)格子，那么我們從（x，y）只能跳往（x—2，y—1）、（x—2，y＋1）、（x—1，y—2）、（x—1，y＋2）、（x＋1，y—2）、（x＋1，y＋2）、（x＋2，y—1）和（x＋2，y＋1）這八個(gè)格子。 我們采用深度優(yōu)先搜索，狀態(tài)表示為當(dāng)前所在格子的坐標(biāo)。那么初始狀態(tài)為（1，1），那么每個(gè)狀態(tài)可以擴(kuò)展的狀態(tài)最多只有八個(gè)。 題目還要求不能重復(fù)經(jīng)過。我們需要加一個(gè)標(biāo)志數(shù)組，標(biāo)志哪些格子已經(jīng)經(jīng)過了，繼續(xù)往下搜的時(shí)候加標(biāo)志搜完了退回來去掉標(biāo)志即可。 一直重復(fù)這個(gè)過程直至所有狀態(tài)均已搜索出來。

【設(shè)計(jì)技巧】標(biāo)志數(shù)組必須是全局變量。

【程序?qū)崿F(xiàn)】 /* Prog：跳馬 lang：c＋＋

*/2.4 搜索法與回溯法圖2.10 棋盤 #include＜iostream＞ #include＜cstring＞ usingnamespacestd； constintdir_x[8]={—2,—2,—1,—1,2,2,1,1}； constintdir_y[8]={—1,1,—2,2,—1,1,—2,2}； boolvis[5][5]； intans=0； voidDFS(intx,inty,intdeep)

｛

if(deep＞=24)

｛

ans＋＋；

return；

｝

2.4 搜索法與回溯法 for(inti=0；i＜8；i＋＋) if(x＋dir_x[i]＞=0&&x＋dir_xi＜5) if(y＋dir_y[i]＞=O&&y＋dir_y[i]＜5) if(！vis[x＋dir_x[i]][y＋dir_y[i]])

｛

vis[x＋dir_x[i]][y＋dir_y[i]]=true；

DFS(x＋dir_x[i],y＋dir_y[i],deep＋1)；

vis[x＋dir_x[i]][y＋dir_yti]=false；

｝

｝ intmain（）

｛ memset(vis,false,sizeof(vis))； vis[0][0]=true； DFS(0,0,0)； cout＜＜ans＜＜endl；

｝2.4 搜索法與回溯法

【例2.12】哈密頓回路。 給一個(gè)無向圖，從1號(hào)點(diǎn)開始不重復(fù)的經(jīng)過所有點(diǎn)后再回到1號(hào)點(diǎn)，這樣的回路稱之為哈密頓回路。 對(duì)于一個(gè)無向圖，求有多少個(gè)哈密頓回路。

【算法分析】哈密頓回路是典型的NP完全問題，沒有多項(xiàng)式復(fù)雜度的解法?？紤]使用深度優(yōu)先搜索的方法解決問題。和上例很類似，但是本題要求的是回路，其實(shí)方法一樣，判斷下走到的最后一個(gè)點(diǎn)和1號(hào)點(diǎn)是否聯(lián)通即可。

【設(shè)計(jì)技巧】采用鄰接矩陣存儲(chǔ)圖，標(biāo)志數(shù)組必須是全局變量。

【程序?qū)崿F(xiàn)】

/* prog：哈密頓回路

lang：c＋＋ */ #include＜iostream＞

#include＜cstring＞

usingnamespacestd； boolvis[10]； intG[10][10]，n，m，ans=0；2.4 搜索法與回溯法 voidDFS(intp,intdeep)

｛

if(deep>=n-1)

｛

if(G[p][1])ans＋＋; return;

｝

for(inti=1;i＜=n;i＋＋)

｛

if(G[p][i]&&！vis[i])

｛

vis[i]=true; DFS(i,deep＋1); vis[i]=false;

｝

｝

｝ intmain（）2.4 搜索法與回溯法

｛

memset(G,0,sizeof(G))；

cin＞＞n＞＞m；

for(inti=0；i＜m；i＋＋)

｛ intpl,p2； cin＞＞pl＞＞p2； G[p1][p2]=G[p2][p1]=1；

｝

memset(vis,false,sizeof(vis))；

vis[1]=true；

DFS(1,0)；

cout＜＜ans＜＜endl；

returnO；

｝2.4 搜索法與回溯法第三章

動(dòng)態(tài)規(guī)劃3.1 動(dòng)態(tài)規(guī)劃的基本思想與概念3.2 動(dòng)態(tài)規(guī)劃的簡(jiǎn)單應(yīng)用3.3 動(dòng)態(tài)規(guī)劃的深入研究3.4 動(dòng)態(tài)規(guī)劃的優(yōu)化方法【3.1.1 動(dòng)態(tài)規(guī)劃的基本思想】

1951年美國數(shù)學(xué)家R.Bellman等人，根據(jù)一類多階段問題的特點(diǎn)，把多階段決策問題變換為一系列互相聯(lián)系的單階段問題，然后逐個(gè)加以解決。一些靜態(tài)模型，只要人為地引進(jìn)“時(shí)間”因素，分成時(shí)段，就可以轉(zhuǎn)化成多階段的動(dòng)態(tài)模型，用動(dòng)態(tài)規(guī)劃方法去處理。與此同時(shí)，他提出了解決這類問題的“最優(yōu)化原理”（Principleofoptimality）：“—個(gè)過程的最優(yōu)決策具有這樣的性質(zhì)，即無論其初始狀態(tài)和初始決策如何，其今后諸策略對(duì)以第一個(gè)決策所形成的狀態(tài)作為初始狀態(tài)的過程而言，必須構(gòu)成最優(yōu)策略?！焙?jiǎn)言之，一個(gè)最優(yōu)策略的子策略，對(duì)于它的初態(tài)和終態(tài)而言也必是最優(yōu)的。

這個(gè)“最優(yōu)化原理”如果用數(shù)學(xué)化一點(diǎn)的語言來描述的話，就是假設(shè)為了解決某一優(yōu)化問題，需要依次作出n個(gè)決策D1、D2、…、Dn，若這個(gè)決策序列是最優(yōu)的，對(duì)于任何一個(gè)整數(shù)k，1＜k＜n，不論前面k個(gè)決策是怎樣的，以后的最優(yōu)決策只取決于由前面決策所確定的當(dāng)前狀態(tài)，即以后的決策Dk+1、Dk+2、…、Dn也是最優(yōu)的。 最優(yōu)化原理是動(dòng)態(tài)規(guī)劃的基礎(chǔ)。任何一個(gè)問題，如果失去了這個(gè)最優(yōu)化原理的支持，就不可能用動(dòng)態(tài)規(guī)劃方法計(jì)算。所以說，它只適于解決一定條件的最優(yōu)策略問題。或許，大家聽到這個(gè)結(jié)論會(huì)很失望。其實(shí)，這個(gè)結(jié)論并沒有削減動(dòng)態(tài)規(guī)劃的光輝，因?yàn)閷儆谏厦娣秶鷥?nèi)的問題極多，還有許多看似不是這個(gè)范圍中的問題都可以轉(zhuǎn)化成這類問題。為了更好地理解動(dòng)態(tài)規(guī)劃的思想，請(qǐng)看下面的例子。3.1 遞歸法 【例3.1】斐波那契數(shù)列是數(shù)學(xué)中常見的數(shù)列，也叫兔子數(shù)列，它滿足：a[1]=1，a[2]=1，a[n]=a[n—1]＋a[n—2]（n＞2）。輸入n，輸出a[n]mod10000007的值。（n≤100000）。

輸入樣例： 3 4 5

輸出樣例： 2 3 5

【算法分析】看到題目以后，我們可以很輕松地寫出兩個(gè)版本的代碼，一個(gè)是遞推的代碼，一個(gè)是遞歸的代碼。其中，遞歸的代碼如下： /* prob：fib—遞歸 lang：c＋＋

*/ #include＜iostream＞ #definemod100000073.1 遞歸法

usingnamespacestd； intf（intx）

｛if（x＜=2） returnl； else return(f(x—1)+f(x—2))%mod；

｝ intmain（） {intn； while(cin＞＞n)

｛ cout＜＜f(n)＜＜endl；

｝

｝3.1 遞歸法 這一段代碼看起來沒有問題，但是運(yùn)行起來卻非常慢，當(dāng)n=100的時(shí)候已經(jīng)無法在有限的時(shí)間內(nèi)得到結(jié)果。我們來看當(dāng)n=5的例子，如圖3.1所示。 當(dāng)n=5的時(shí)候，使用遞歸的思路計(jì)算，f（3）被重復(fù)地調(diào)用了2次，f（2）被重復(fù)地調(diào)用了3次，而f（i）無論被調(diào)用多少次，它的返回值都是相同的。因此，進(jìn)行了很多次無用的計(jì)算。如果能夠在第一次計(jì)算f（i）的時(shí)候，把f（i）的結(jié)果記錄下來，下一次調(diào)用的時(shí)候，直接返回f（i）的值，就可以避免很多次冗余的計(jì)算，如圖3.2所示。這樣一來，把冗余的計(jì)算都省去，程序的效率將得到質(zhì)的提升。圖3.1斐波那契數(shù)列的計(jì)算過程

圖3.2記憶化的優(yōu)化效果，灰色部分不再被調(diào)用3.1 遞歸法3.1 遞歸法 斐波那契數(shù)列的求法，從嚴(yán)格意義上來說，并不算是動(dòng)態(tài)規(guī)劃，但是卻和動(dòng)態(tài)規(guī)劃有著千絲萬縷的聯(lián)系： （1）利用多余的空間記錄了重復(fù)狀態(tài)的計(jì)算結(jié)果，避免了冗余的計(jì)算。 （2）有狀態(tài)轉(zhuǎn)移方程（在這里是f[i]=f[i—1]＋f[i—2]，i≥3）。 （3）任何一個(gè)狀態(tài)只與確定的前幾項(xiàng)直接相關(guān)。 在這類問題中，保存已經(jīng)求得的結(jié)果，在下次求解時(shí)直接調(diào)用結(jié)果，而不是重復(fù)地計(jì)算，這就是動(dòng)態(tài)規(guī)劃的基本思想。3.1 遞歸法【3.1.2 動(dòng)態(tài)規(guī)劃的概念】 動(dòng)態(tài)規(guī)劃是運(yùn)籌學(xué)的一個(gè)分支。與其說動(dòng)態(tài)規(guī)劃是一種算法，不如說是一種思維方法來得更貼切。因?yàn)閯?dòng)態(tài)規(guī)劃沒有固定的框架，即便是應(yīng)用到同一問題上，也可以建立多種形式的求解算法。許多隱式圖上的算法，例如求單源最短路徑的Dijkstra算法、廣度優(yōu)先搜索算法，都滲透著動(dòng)態(tài)規(guī)劃的思想。還有許多數(shù)學(xué)問題，表面上看起來與動(dòng)態(tài)規(guī)劃風(fēng)馬牛不相及，但是其求解思想與動(dòng)態(tài)規(guī)劃是完全一致的。 因此，動(dòng)態(tài)規(guī)劃不像深度或廣度優(yōu)先那樣可以提供一套模式，需要的時(shí)候，取來就可以使用，它必須對(duì)具體問題進(jìn)行具體分析處理，需要豐富的想象力去建立模型，需要?jiǎng)?chuàng)造性的思想去求解。 前面我們?cè)f，動(dòng)態(tài)規(guī)劃不是萬能的，它只適于解決滿足一定條件的最優(yōu)策略問題。 “滿足一定條件”主要指下面兩點(diǎn)： （1）狀態(tài)必須滿足最優(yōu)化原理； （2）狀態(tài)必須滿足無后效性。所謂的無后效性，是指"過去的決策只能通過當(dāng)前狀態(tài)影響未來的發(fā)展，當(dāng)前的狀態(tài)是對(duì)以往決策的總結(jié)"。 這條特征說明什么呢?它說明動(dòng)態(tài)規(guī)劃適于解決當(dāng)前決策和過去狀態(tài)無關(guān)的問題。狀態(tài)出現(xiàn)在策略的任何一個(gè)位置，它的地位都是相同的，都可以實(shí)施同樣的決策。這就是無后效性的內(nèi)涵。3.1 遞歸法【3.1.3 動(dòng)態(tài)規(guī)劃的常用名詞】 在學(xué)習(xí)動(dòng)態(tài)規(guī)劃之前，先得對(duì)下面的名詞有所了解。本書將標(biāo)準(zhǔn)名詞作了一些簡(jiǎn)化，便于大家更好地理解。 （1）狀態(tài)（state）。對(duì)于一個(gè)問題，所有可能到達(dá)的情況（包括初始情況和目標(biāo)情況）都稱為這個(gè)問題的一個(gè)狀態(tài)。 （2）狀態(tài)變量（sk）。對(duì)每個(gè)狀態(tài)k關(guān)聯(lián)一個(gè)狀態(tài)變量sk，它的值表示狀態(tài)k所對(duì)應(yīng)的問題的當(dāng)前解值。 （3）決策（decision）。決策是一種選擇，于每一個(gè)狀態(tài)而言，都可以選擇某一種路線或方法，從而到達(dá)下一個(gè)狀態(tài)。 （4）決策變量（dk）。在狀態(tài)k下的決策變量dk的值表示對(duì)狀態(tài)k當(dāng)前所做出的決策。 （5）策略。策略是一個(gè)決策的集合，在解決問題的時(shí)候，我們將一系列決策記錄下來，就是一個(gè)策略，其中滿足某些最優(yōu)條件的策略稱為最優(yōu)策略。 （6）狀態(tài)轉(zhuǎn)移函數(shù)（t）。從一個(gè)狀態(tài)到另一個(gè)狀態(tài)，可以依據(jù)一定的規(guī)則來前進(jìn)。我們用一個(gè)函數(shù)t來描述這樣的規(guī)則，它將狀態(tài)i和決策變量di映射到另一個(gè)狀態(tài)j，記為t（i,di）=j。 （7）狀態(tài)轉(zhuǎn)移方程（f）。狀態(tài)轉(zhuǎn)移方程f描述了狀態(tài)變量之間的數(shù)學(xué)關(guān)系。一般來說，與最優(yōu)化問題相對(duì)應(yīng)，狀態(tài)轉(zhuǎn)移方程表示si的值最優(yōu)化的條件，或者說是狀態(tài)i所對(duì)應(yīng)問題的最優(yōu)解值的計(jì)算公式，用代數(shù)式表示就是：

si=f（｛(sj，dj）|i=t（j，dj），對(duì)決策變量dj所有可行的取值｝）3.1 遞歸法【3.1.4 動(dòng)態(tài)規(guī)劃算法的基本步驟】

動(dòng)態(tài)規(guī)劃求解的基本步驟一般是：（1）定義狀態(tài)；（2）劃分階段；（3）確定狀態(tài)轉(zhuǎn)移方程；（4）確定邊界條件。 【例3.2】給定一個(gè)三角形，三角形的第一行有1個(gè)元素，第二行有2個(gè)元素……第N行有N個(gè)元素，每個(gè)元素的值都是正數(shù)。現(xiàn)在從三角形的第1行1列出發(fā)，每次只能往下一行的同一列或者下一行的下一列走，走到最后一行停止，路徑上能夠取得的元素最大值之和是多少?

例如：12 34 5 6若路徑為1→3→6，則能夠去的的最大值和是1＋3＋6＝10?！舅惴ǚ治觥课覀儼凑談?dòng)態(tài)規(guī)劃的基本求解步驟來解這道題目。

3.1 遞歸法

1.定義狀態(tài)

動(dòng)態(tài)規(guī)劃的狀態(tài)定義方式和搜索算法的狀態(tài)定義方式很相似。如果本題采用搜索算法來求解，則可以寫出這樣一個(gè)函數(shù)模型： dfs（inti，intj，intsum）表示現(xiàn)在走道（i，j）這個(gè)點(diǎn)，已經(jīng)拿到的元素之和為sum。 根據(jù)動(dòng)態(tài)規(guī)劃的思想，對(duì)于任何一個(gè)點(diǎn)（i，j），我們只關(guān)心能夠走到這個(gè)點(diǎn)的最大的和sum。因此，動(dòng)態(tài)規(guī)劃的狀態(tài)定義如下： dp[i][j]=sum，1≤i，j≤N，j≤i表示走到第i行j列的時(shí)候所能取得的最大元素之和。 2.劃分階段 在本題中，無論每一步該怎么走，行數(shù)i必然＋1。因此，經(jīng)過恰好N一1步后，將到達(dá)三角形的底部，尋找路徑的過程結(jié)束。所以，本題的階段就是行走過程中的步數(shù)，與狀態(tài)中的i一一對(duì)應(yīng)。

3.確定狀態(tài)轉(zhuǎn)移方程 使用搜索算法求解此題，搜索的函數(shù)中會(huì)有如下代碼∶

dfs(i＋1，j，sum＋a[i＋1][j])； ∥向下走

dfs（i＋1，j＋1，sum＋a[i＋1][j＋1]）； ∥向右下走3.1 遞歸法說明：每一個(gè)坐標(biāo)（i，j）有兩種決策，往下或者往右下走，換個(gè)角度思考，每一個(gè)坐標(biāo)（i，j）也有兩種到達(dá)方式：從上方來或者從左上方來。使用數(shù)學(xué)語言來描述這句話，就是狀態(tài)轉(zhuǎn)移方程： dp[i][j]=max(dp[i-1][j]，dp[i-1][j-1])＋a[i][j]

4.確定邊界條件 上述狀態(tài)轉(zhuǎn)移方程，由于是一步一步遞推得到的，因此必須確定邊界條件。邊界條件包含兩部分：初始狀態(tài)和邊界狀態(tài)。 初始狀態(tài)：dp[1][1]=a[1]1] ∥所有的起點(diǎn)都是（1，1） 邊界狀態(tài)∶dp[i][j]=0 ∥如果（i，j）不在三角形內(nèi) 此時(shí)，就可以編寫代碼了。

【程序?qū)崿F(xiàn)】 /* prob：數(shù)字三角形

lang：c＋＋

*/ #include＜iostream＞ #include＜string.h＞ #definemod100000073.1 遞歸法3.1 遞歸法【3.2.1 線性動(dòng)態(tài)規(guī)劃】

【例3.3】魔族密碼。 題目描述：魔族現(xiàn)在使用一種新型的密碼系統(tǒng)。每一個(gè)密碼都是一個(gè)給定的僅包含小寫字母的英文單詞表，每個(gè)單詞至少包含1個(gè)字母，至多75個(gè)字母。如果在一個(gè)由一個(gè)詞或多個(gè)詞組成的表中，除了最后一個(gè)以外，每個(gè)單詞都被其后的一個(gè)單詞所包含，即前一個(gè)單詞是后一個(gè)單詞的前綴，則稱詞表為一個(gè)詞鏈。例如下面的單詞組成了一個(gè)詞鏈： i int integer

但下面的單詞不組成詞鏈： integer intern 現(xiàn)在你要做的就是在一個(gè)給定的單詞表中取出一些詞，組成最長(zhǎng)的詞鏈，就是包含單詞數(shù)最多的詞鏈。將它的單詞數(shù)統(tǒng)計(jì)出來，就得到密碼了。 輸入格式：第一行為單詞表中的單詞數(shù)N（1≤N≤2000），下面每一行有一個(gè)單詞，按字典順序排列，中間也沒有重復(fù)的單詞。

3.2 動(dòng)態(tài)規(guī)劃的簡(jiǎn)單應(yīng)用

輸入樣例： 5 i int integer intern internet

輸出樣例： 4

樣例解釋： i-＞int一＞intern-＞internet

【算法分析】這道題目就是一道典型的線性動(dòng)態(tài)規(guī)劃，為了更好地理解它，我們首先來看它的搜索實(shí)現(xiàn)。如果用搜索算法來寫這道題目，寫起來是非常容易的，代碼如下： /* prob：vijos—p1028—dfs lang：c＋＋

*/3.2 動(dòng)態(tài)規(guī)劃的簡(jiǎn)單應(yīng)用 #include＜iostream＞ #include＜string.h＞ usingnamespacestd； intn； strings[2005]； intdp[2005]； intans=0； boolcan（inti，intj）

｛ if（i==0）returntrue； if（s[j].find（s[i]））==0）returntrue； returnfalse；

｝

∥i指的是當(dāng)前搜索到了哪一個(gè)字符串

∥step指的是當(dāng)前一共接了幾個(gè)字符串 intdfs（inti，intstep）

｛ ans=max（ans，step）；3.2 動(dòng)態(tài)規(guī)劃的簡(jiǎn)單應(yīng)用 for（intj=i＋1；j＜=n；j＋＋） if（can（i，j））

｛ dfs（j，step＋1）；

｝ return0；

｝ intmain（）

｛ while（cin＞＞n）

｛ ans=0 memset（dp，0，sizeof（dp））； for（inti=1；i＜=n；i＋＋）

｛ cin＞＞s[i]；

｝ dfs（0，0）； count＜＜ans＜＜endl；

｝