現(xiàn)代大學(xué)計算機基礎(chǔ)算法思維與程序設(shè)計基礎(chǔ)

第5章算法思維與程序設(shè)計根底5.1開啟智慧的“蘋果〞—算法5.2亞當夏娃的誘惑—算法與程序5.3登上方舟的神器—經(jīng)典算法思想

5.1開啟智慧的“蘋果〞—算法

在20世紀50年代西方某些著名的詞典中，還未曾收錄過算法(Algorithm)一詞。根據(jù)西方數(shù)學(xué)史家的考證，古代阿拉伯的一位學(xué)者寫了一部名著?Kitābal-jabrWa’lmuqābJla?(?復(fù)原和化簡的規(guī)那么?)。這部著作流傳到了西方，結(jié)果從作者署名中的al-Khwārizmī派生出了Algorithm(算法)一詞，從作品名字中的al-jabr派生出了Algebra(代數(shù))一詞。隨著時間的推移，Algorithm(算法)這個詞已經(jīng)完全與它原來的含義不同了。計算機系統(tǒng)中的任何軟件，都是由大大小小的各種軟件組成局部構(gòu)成的，各自按照特定的算法來實現(xiàn)，算法的好壞直接決定所實現(xiàn)軟件性能的優(yōu)劣。用什么方法來設(shè)計算法，所設(shè)計的算法需要什么樣的資源，需要多少運行時間、多少存儲空間，如何判定一個算法的好壞，在開發(fā)一個軟件時，都是必須予以解決的。計算機系統(tǒng)中的操作系統(tǒng)、語言編譯系統(tǒng)、數(shù)據(jù)庫管理系統(tǒng)以及各種各樣的計算機應(yīng)用系統(tǒng)中的軟件，都必須用一個個具體的算法來實現(xiàn)。因此，算法設(shè)計與分析是計算機科學(xué)與技術(shù)的一個核心問題。5.1.1算法的根本概念

歐幾里德曾在他的著作中描述過求兩個數(shù)的最大公因子的過程。20世紀50年代，歐幾里德所描述的這個過程被稱為歐幾里德算法，算法這個術(shù)語在學(xué)術(shù)上便具有了現(xiàn)在的含義。下面是這個算法的例子及它的一種描述。

算法歐幾里德算法。

輸入：正整數(shù)m，n

輸出：m，n的最大公因子

1.inteuclid(intm，intn)

2.{

3.intr;

4.do{

5.r=m%n;

6.m=n;

7.n=r;

8.}while(r)

9.returnm;

10.}在此用一種類C語言來表達最大公因子的求解過程。在算法的第5行，把m除以n的余數(shù)賦予r，第6行把n的值賦予m，第7行把r值賦予n，第8行判斷r是否為0，假設(shè)非0，繼續(xù)轉(zhuǎn)到第5行進行處理；假設(shè)為0，就轉(zhuǎn)到第9行處理，第9行返回m，算法結(jié)束。按照上面這組規(guī)那么，給定任意兩個正整數(shù)，總能返回它們的最大公因子?？梢宰C明這個算法的正確性。算法的歷史可以追溯到9世紀的古波斯。最初它僅表示“阿拉伯數(shù)字的運算法那么〞。后來，它被賦予更一般的含義，即所謂的一組確定的、有效的、有限的解決問題的步驟。這是算法的最初定義。當代著名計算機科學(xué)家D．E．Knuth在他撰寫的?THEARTOFCOMPUTERPROGRAMMING?一書中寫到：“一個算法，就是一個有窮規(guī)那么的集合，其中之規(guī)那么規(guī)定了一個解決某一特定類型的問題的運算序列。〞

綜上所述，可以給出算法的定義：算法是解某一特定問題的一組有窮規(guī)那么的集合。5.1.2算法的根本特征

任何解決問題的過程都是由一定的步驟組成的，通常把解決問題確實定方法和有限步驟稱為算法。對于計算機科學(xué)來說，算法指的是對特定問題求解步驟的一種描述，是假設(shè)干條指令的有窮序列，并且它具有以下特性：

(1)有窮性：算法在執(zhí)行有限步驟之后結(jié)束。

(2)確切性：算法的每一個步驟都有確切的定義。

(3)輸入：一個算法有0個或多個輸入，它是由外部提供的，作為算法開始執(zhí)行前的初始值或初始狀態(tài)。算法的輸入是從特定的對象集合中抽取的。(4)輸出：一個算法有一個或多個輸出，這些輸出與輸入有特定的關(guān)系，實際上是輸入的某種函數(shù)。不同取值的輸入，產(chǎn)生不同結(jié)果的輸出。

(5)可行性：在原那么上算法能夠精確地運行，進行有限次運算后即可完成一種運算。

必須注意到，在實際應(yīng)用中，有窮性的限制是不夠的。一個實用的算法，不僅要求步驟有限，同時要求運行這些步驟所花費的時間是人們可以接受的。如果一個算法需要執(zhí)行數(shù)十百億計的運算步驟，那么從理論上說，它是有限的，最終可以結(jié)束，但卻是人們難以接受的。算法設(shè)計的整個過程，可以包含對問題需求的說明、數(shù)學(xué)模型的擬制、算法的詳細設(shè)計、算法的正確性驗證、算法的實現(xiàn)、算法分析、程序測試和文檔資料的編制。 5.2亞當夏娃的誘惑—算法與程序

5.2.1算法思想的本質(zhì)—數(shù)學(xué)模型

簡單地說，數(shù)學(xué)模型就是對實際問題的一種數(shù)學(xué)表達，是數(shù)學(xué)理論與實際問題相結(jié)合的一門科學(xué)。它將現(xiàn)實問題歸結(jié)為相應(yīng)的數(shù)學(xué)問題，并在此根底上利用數(shù)學(xué)概念、方法和理論進行深入分析與研究，從而可以從定性或定量的角度來刻畫實際問題，并為解決現(xiàn)實問題提供精確數(shù)據(jù)和可靠指導(dǎo)。算法設(shè)計時，首先要根據(jù)問題的描述，建立符合要求的數(shù)學(xué)模型，并設(shè)計相關(guān)的約束條件等。建立數(shù)學(xué)模型的步驟如下：

(1)模型準備。要了解問題的實際背景，明確建模目的，搜索必要的各種信息，盡量弄清對象的特征。

(2)模型假設(shè)。根據(jù)對象的特征和建模目的，對問題進行必要的、合理的簡化，用精確的語言做出假設(shè)，是建模至關(guān)重要的一步。高超的建模者能充分發(fā)揮想象力、洞察力和判斷力，善于區(qū)分問題所有因素的主次，而且為了使處理方法簡單，應(yīng)盡量使問題線性化、均勻化。

(3)模型構(gòu)成。根據(jù)所做的假設(shè)分析對象的因果關(guān)系，利用對象的內(nèi)在規(guī)律和適當?shù)臄?shù)學(xué)工具，建立各個量之間的等式或不等式關(guān)系，列出表格、畫出圖形或確定其他數(shù)學(xué)結(jié)構(gòu)，選擇恰當?shù)臄?shù)學(xué)工具和構(gòu)造模型的方法對其進行表征，構(gòu)造出刻畫實際問題的數(shù)學(xué)模型。(4)模型求解。構(gòu)造數(shù)學(xué)模型之后，再根據(jù)條件和數(shù)據(jù)分析模型的特征及結(jié)構(gòu)特點，設(shè)計或選擇求解模型的數(shù)學(xué)方法和算法，這其中包括解方程、畫圖形、證明定理、進行邏輯運算及穩(wěn)定性討論，特別是編寫計算機程序或運用與算法相適應(yīng)的軟件包，并借助計算機完成對模型的求解。

(5)模型分析。根據(jù)建模的目的要求，對模型求解的數(shù)字結(jié)果，或進行變量之間的依賴關(guān)系分析，或進行穩(wěn)定性分析，或進行系統(tǒng)參數(shù)的靈敏度分析，或進行誤差分析等。通過分析，如果不符合要求，就修改或增減建模假設(shè)條件，重新建模，直到符合要求；如果符合要求，還可以對模型進行評價、預(yù)測、優(yōu)化等。(6)模型檢驗?zāi)Ｐ头治龇弦笾?，還必須回到客觀實際中去對模型進行檢驗，用實際現(xiàn)象、數(shù)據(jù)等檢驗?zāi)Ｐ偷暮侠硇院瓦m用性，看它是否符合客觀實際，假設(shè)不符合，就修改或增減假設(shè)條件，重新建模，循環(huán)往復(fù)，不斷完善，直到獲得滿意的結(jié)果。目前計算機技術(shù)已為我們進行模型分析、模型檢驗提供了先進的手段，充分利用這一手段，可以節(jié)約大量的時間、人力和物力。

(7)模型應(yīng)用。模型應(yīng)用是數(shù)學(xué)建模的宗旨，也是對模型最客觀、最公正的檢驗。因此，一個成功的數(shù)學(xué)模型，必須根據(jù)建模的目的，將其用于分析、研究和解決實際問題，充分發(fā)揮數(shù)學(xué)模型在生產(chǎn)和科研中的特殊作用。5.2.2算法思想的表達—算法設(shè)計

人們希望計算機求解的問題是千差萬別的，所設(shè)計的求解方法也千差萬別。一般來說，算法設(shè)計沒有固定的方法可循，所以，算法的設(shè)計是一個靈活且充滿智慧的過程，要求設(shè)計者針對具體的問題設(shè)計出適合該問題的解決方案。

在進行算法設(shè)計時，一般遵循以下步驟：

(1)明確問題的性質(zhì)，分析題意。這一步很關(guān)鍵。在設(shè)計算法的時候，一定要先搞清楚要求算法處理什么問題、實現(xiàn)哪些功能、預(yù)期獲得的結(jié)果等。如果設(shè)計者沒有充分理解所要解決的問題，那么設(shè)計出的算法肯定是漏洞百出的。這一步是算法的切入點，也是設(shè)計者必備的技能。(2)建立問題的數(shù)學(xué)描述模型。數(shù)學(xué)模型是對實際問題的一種數(shù)學(xué)表達，進行算法設(shè)計時，首先要根據(jù)問題的描述，建立符合要求的數(shù)學(xué)模型，并設(shè)計相關(guān)的約束條件等。

(3)設(shè)計/驗證算法。算法設(shè)計是把算法具體化，即設(shè)計出算法的詳細規(guī)格說明。在這一階段，要選擇算法的設(shè)計策略，并確定合理的數(shù)據(jù)結(jié)構(gòu)。顯然，算法設(shè)計策略的選擇關(guān)乎全局，同樣，數(shù)據(jù)結(jié)構(gòu)的選擇對于算法的設(shè)計和分析也很重要，如果選擇不當，它將影響算法的性能。

做完上面的工作后，采用描述工具將算法的具體過程描述下來，通過對一系列與算法的工作對象有關(guān)的定理、引理和公式進行證明，來驗證算法所選擇的設(shè)計策略與思路是否正確。(4)算法分析。算法分析是對算法的效率進行分析，主要是時間效率和空間效率。其中，時間效率顯示算法運行速度有多快，空間效率顯示算法運行時需要的存儲空間有多大。相對而言，人們更關(guān)注時間效率。

(5)算法實現(xiàn)和測試。根據(jù)算法，采用一種編程語言編程實現(xiàn)，然后上機調(diào)試，得到程序的運行結(jié)果，分析運行結(jié)果是否符合預(yù)先的期望，如果不符合，那么找出原因，并對算法或程序進行修正，直到得到正確的結(jié)果。5.2.3算法思想的實現(xiàn)—程序設(shè)計

程序設(shè)計是給出解決特定問題程序的過程，是軟件構(gòu)造活動中的重要組成局部。程序設(shè)計往往以某種程序設(shè)計語言為工具，給出這種語言下的程序。程序設(shè)計過程應(yīng)當包括分析、設(shè)計、編碼、測試、排錯等不同階段。

任何設(shè)計活動都是在各種約束條件和相互矛盾的需求之間尋求一種平衡，程序設(shè)計也不例外。在計算機技術(shù)開展的早期，由于機器資源比較昂貴，程序的時間和空間代價往往是設(shè)計關(guān)心的主要因素；隨著硬件技術(shù)的飛速開展和軟件規(guī)模的日益龐大，程序的結(jié)構(gòu)、可維護性、復(fù)用性、可擴展性等因素日益重要。在程序設(shè)計時，一般遵循以下步驟：

(1)分析問題。對于接受的任務(wù)要進行認真的分析，研究所給定的條件，分析最后應(yīng)到達的目標，找出解決問題的規(guī)律，選擇解題的方法，完成實際問題。

(2)設(shè)計算法。即設(shè)計出解題的方法和具體步驟。

(3)編寫程序。將算法翻譯成計算機程序設(shè)計語言，對源程序進行編輯、編譯和連接。

(4)運行程序，分析結(jié)果。運行可執(zhí)行程序，得到運行結(jié)果。能得到運行結(jié)果并不意味著程序正確，要對結(jié)果進行分析，看它是否合理。不合理要對程序進行調(diào)試，即通過上機發(fā)現(xiàn)和排除程序中的故障的過程。(5)編寫程序文檔。許多程序是提供給別人使用的，如同正式的產(chǎn)品應(yīng)當提供產(chǎn)品說明書一樣，正式提供給用戶使用的程序，必須向用戶提供程序說明書。其內(nèi)容應(yīng)包括程序名稱、程序功能、運行環(huán)境、程序的裝入和啟動、需要輸入的數(shù)據(jù)，以及使用本卷須知等。5.2.4檢驗真理的標準—算法分析

解決一個問題，算法不必是唯一的。對表示問題的數(shù)據(jù)的不同組織方式(數(shù)據(jù)結(jié)構(gòu))，解決問題的不同策略將導(dǎo)致不同的算法。解決同一問題的不同算法，消耗的時間和空間資源量有所不同。算法運行所需要的計算機資源的量稱為算法的復(fù)雜性。一般來說，解決同一問題的算法，需要的資源量越少，我們認為越優(yōu)秀。計算算法運行所需資源量的過程稱為算法復(fù)雜性分析，簡稱算法分析。理論上，算法分析既要計算算法的時間復(fù)雜性，也要計算它的空間復(fù)雜性。然而，算法的運行時間都是消耗在數(shù)據(jù)處理上的，從這個意義上說，算法的空間復(fù)雜性不會超過時間復(fù)雜性。因此，人們多關(guān)注算法的時間復(fù)雜性。1．算法復(fù)雜性

1)時間復(fù)雜性

隨著計算機硬件和軟件的提升，一個算法的執(zhí)行時間不便精確計算，只能依據(jù)統(tǒng)計方法對算法進行估算。拋開硬件和軟件的因素，算法的好壞將直接影響程序的運行時間。一個算法花費的時間與算法中語句的執(zhí)行次數(shù)成正比，哪個算法中語句執(zhí)行次數(shù)多，它花費的時間就多。一般情況下，算法中根本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)，稱為語句頻度或時間頻度，用T(n)表示，假設(shè)有某個輔助函數(shù)f(n)，使得當n趨近于無窮大時，T(n)/f(n)的極限值為不等于零的常數(shù)，那么稱f(n)是T(n)的同數(shù)量級函數(shù)。記作T(n)=O(f(n))，稱O(f(n))為算法的漸進時間復(fù)雜度，簡稱時間復(fù)雜度。隨著模塊n的增大，算法執(zhí)行的時間增長率f(n)的增長率成正比，所以f(n)越小，算法的時間復(fù)雜度越低，算法的效率越高。

例5-1分析下面程序的時間復(fù)雜度：

intvalue=0;

//執(zhí)行了1次

for(inti=0;i<n;i++){

//執(zhí)行了n次

value+=i;

}這個算法執(zhí)行了1+n次，如果n無限大，那么可以把前邊的1忽略，也就是說這個算法執(zhí)行了n次，這個算法的時間復(fù)雜度就是O(n)。

計算時間復(fù)雜度的步驟如下：

(1)去掉運行時間中的所有加法常數(shù)。

(2)只保存最高階項。

(3)如果最高階項存在且不是1，那么去掉與這個最高階相乘的常數(shù)即可得到時間復(fù)雜度。

例5-2計算下面程序的時間復(fù)雜度：

分析：當i=0時，里面的for循環(huán)執(zhí)行了n次，當i等于1時里面的for循環(huán)執(zhí)行了n－1次，當i等于2時里面的for執(zhí)行了n－2次，……所以執(zhí)行的次數(shù)是根據(jù)上邊計算時間復(fù)雜度的步驟，可得以下計算過程：

(1)去掉運行時間中的所有加法常數(shù)：這里沒有加法常數(shù)不用考慮。

(2)只保存最高階項：這里只保存。

(3)去掉與這個最高階相乘的常數(shù)：這里去掉只剩下n2。

最終這個算法的時間復(fù)雜度為O(n2)。

例5-3計算下面程序的時間復(fù)雜度：

for(inti=0;i<n;i++){

//do...

}

因為循環(huán)要執(zhí)行n次，所以時間復(fù)雜度為O(n)。2)空間復(fù)雜性

一個程序的空間復(fù)雜度是指運行完一個程序所需內(nèi)存的大小。利用程序的空間復(fù)雜度，可以對程序的運行所需要的內(nèi)存多少有個預(yù)先估計。一個程序執(zhí)行時除了需要存儲空間來存儲本身所使用的指令、常數(shù)、變量和輸入數(shù)據(jù)外，還需要一些對數(shù)據(jù)進行操作的工作單元和存儲一些為實現(xiàn)計算所需信息的輔助空間。程序執(zhí)行時所需存儲空間包括以下兩局部：

(1)固定局部。這局部空間的大小與輸入/輸出的數(shù)據(jù)的個數(shù)多少、數(shù)值無關(guān)，主要包括指令空間(即代碼空間)、數(shù)據(jù)空間(常量、簡單變量)等所占的空間。這局部屬于靜態(tài)空間。(2)可變空間。這局部空間主要包括動態(tài)分配的空間以及遞歸棧所需的空間等。這局部的空間大小與算法有關(guān)。

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

2．算法分析意義

算法分析對算法的設(shè)計、選用和改進有著重要的指導(dǎo)意義及實用價值。

(1)對于任意給定的問題，設(shè)計出復(fù)雜性盡可能低的算法是在設(shè)計時考慮的一個重要目標。

(2)當給定的問題已經(jīng)有多種算法時，選擇復(fù)雜度最低者是在選用算法時應(yīng)遵循的一個重要準那么。

(3)算法分析有助于對算法進行改進。 5.3登上方舟的神器—經(jīng)典算法思想

5.3.1化整為零—分治法

1．分治法所能解決的問題特征

(1)該問題的規(guī)?？s小到一定的程度就可以容易地解決；

(2)該問題可以分解為假設(shè)干個規(guī)模較小的相同問題，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)；

(3)利用該問題分解出的子問題的解可以合并為該問題的解；

(4)該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子問題。上述第一條特征是絕大多數(shù)問題都可以滿足的，因為問題的計算復(fù)雜性一般是隨著問題規(guī)模的增加而增加的；第二條特征是應(yīng)用分治法的前提，它也是大多數(shù)問題可以滿足的，此特征反映了遞歸思想的應(yīng)用；第三條特征是關(guān)鍵，能否利用分治法完全取決于問題是否具有第三條特征，如果具備了第一條和第二條特征，而不具備第三條特征，那么可以考慮用貪心法或動態(tài)規(guī)劃法；第四條特征涉及分治法的效率，如果各子問題是不獨立的那么分治法要做許多不必要的工作，重復(fù)地解公共的子問題，此時雖然可用分治法，但一般用動態(tài)規(guī)劃法較好。2．分治法的求解步驟

1)分解

顧名思義，分治法就是要對待求解問題進行分解，即將問題分解為假設(shè)干個規(guī)模較小、相互獨立、與原問題形式相同的子問題。

那么，怎樣對問題分解才合理呢？應(yīng)把原問題分解為多少個子問題才適宜呢？每個子問題是否規(guī)模相同才更為適當？這些問題很難給出肯定的答復(fù)。人們通過大量的實踐發(fā)現(xiàn)，在用分治法設(shè)計算法時，最好使子問題的規(guī)模大致相同，即將一個問題分為大小相等的M個子問題，通常M=2，也有M=1的劃分，它仍然把問題劃分為兩局部，取其中的一局部，而丟棄另一局部。例如，二分查找問題在采用分治法求解時就是這樣劃分的。2)求解各個子問題

如何對各個子問題進行求解呢？由于采用分治法求解的問題被分解為假設(shè)干個規(guī)模較小的相同子問題，各個子問題的解法與原問題的解法是相同的，因此，可以采用遞歸技術(shù)對各個子問題進行求解。在這種情況下，反復(fù)應(yīng)用分治手段，可以使子問題與原問題類型一致而規(guī)模不斷縮小，最終使子問題縮小到很容易解決的程度，這導(dǎo)致遞歸過程的產(chǎn)生。分治與遞歸經(jīng)常同時用在算法設(shè)計中，有時，遞歸也可以采用循環(huán)來實現(xiàn)。

3)合并

合并對分治法的性能至關(guān)重要，算法的有效性很大程度上依賴于合并的實現(xiàn)。3．分治算法設(shè)計模式

其中p(n)表示一個規(guī)模為n的問題p，可以分解成K個規(guī)模較小的子問題，這些問題相互獨立，又與原來的問題結(jié)構(gòu)相同。在解決子問題時，又用相同的方式對每一個問題進行進一步的分解，直到某個閾值n0為止。遞歸地解這些子問題，再把這些子問題的解合并起來，就得到原來問題的解。n0為一閾值，表示當問題p的規(guī)模不超過n0時，問題已容易解出，不必繼續(xù)分解。Adhoc(p(n))是該分治法中的根本子算法，用于直接解小規(guī)模的問題p。因此，當p的規(guī)模不超過n0時，直接用Adhoc(p(n))求解。merge(y1，y2，…，yk)是該分治法中的合并子算法，用于將p的子問題p1，p2，…，pk的相應(yīng)解合并為p的解。

例5-4整數(shù)乘法。設(shè)X和Y都是n位二進制整數(shù)，現(xiàn)在要計算它們的乘積XY。我們可以用小學(xué)所學(xué)的方法來設(shè)計一個計算乘積XY的算法，但是這樣做計算步驟太多，顯得效率較低。如果將每2個1位數(shù)的乘法或加法看做一步運算，那么這種方法運行時間為O(n2)。下面用分治法來設(shè)計一個更有效的大整數(shù)乘積算法。

我們將n位二進制整數(shù)X和Y各分為2段，每段的長為n/2位(為簡單起見,假設(shè)n是2的冪),由此,X=A2n/2+B,Y=C2n/2+D。這樣，X和Y的乘積為

Y=(A2n/2+B)(C2n/2+D)=AC2n+(AD+CB)2n/2+BD(1)如果按式(1)計算XY，那么必須進行4次n/2位整數(shù)的乘法(AC，AD，BC和BD)，以及3次不超過n位的整數(shù)加法(分別對應(yīng)于式(1)中的加號)，此外還要做2次移位(分別對應(yīng)于式(1)中乘2n和乘2n/2)，運行時間為O(n2)，可見，用式(1)計算X和Y的乘積并不比小學(xué)生的方法更有效。要想改進算法的計算復(fù)雜性，必須減少乘法次數(shù)。為此把XY寫成另一種形式：

XY=AC2n+[(A－B)(D－C)+AC+?BD]2n/2+BD(2)

雖然式(2)來比式(1)復(fù)雜些，但它僅需做3次n/2位整數(shù)的乘法(AC，BD和(A－B)(D－C))以及6次加、減法和2次移位。由此需要運行的時間為O(nlog3)=O(n)。5.3.2欲壑難填—貪婪法

1．貪婪算法可解決的問題特征

(1)隨著算法的進行，將積累起其他兩個集合：一個包含已經(jīng)被考慮過并被選出的候選對象，另一個包含已經(jīng)被考慮過但被丟棄的候選對象。

(2)有一個函數(shù)來檢查一個候選對象的集合是否提供了問題的解答。該函數(shù)不考慮此時的解決方法是否最優(yōu)。

(3)還有一個函數(shù)檢查是否一個候選對象的集合是可行的，也即是否可能往該集合上添加更多的候選對象以獲得一個解。和上一個函數(shù)一樣，此時不考慮解決方法的最優(yōu)性。

(4)選擇函數(shù)可以指出哪一個剩余的候選對象最有希望構(gòu)成問題的解。(5)最后，目標函數(shù)給出解的值。

(6)為了解決問題，需要尋找一個構(gòu)成解的候選對象集合，它可以優(yōu)化目標函數(shù)，貪婪算法一步一步地進行。起初，算法選出的候選對象的集合為空。接下來的每一步中，根據(jù)選擇函數(shù)，算法從剩余候選對象中選出最有希望構(gòu)成解的對象。如果集合中加上該對象后不可行，那么該對象就被丟棄并不再考慮；否那么就加到集合里。每一次都擴充集合，并檢查該集合是否構(gòu)成解。如果貪婪算法正確工作，那么找到的第一個解通常是最優(yōu)的。2．貪婪算法的根本思路

(1)建立數(shù)學(xué)模型來描述問題。

(2)把求解的問題分成假設(shè)干個子問題。

(3)對每一子問題求解，得到子問題的局部最優(yōu)解。

(4)把子問題的解局部最優(yōu)解合成原問題的一個解。

3．貪婪算法的求解步驟

(1)從問題的某一初始解出發(fā)。

(2)朝給定總目標前進一步，求出可行解的一個解元素。

(3)由所有解元素組合成問題的一個可行解。

4．貪婪算法設(shè)計模式

貪婪法是在少量運算的根底上做出目前最好的選擇，不考慮該選擇對將來是否有不良影響，一步一步地進行解的擴充，最后由局部最優(yōu)解來推導(dǎo)全局最優(yōu)解

。

例5-5設(shè)有n個正整數(shù)，將它們連接成一排，組成一個最大的多位整數(shù)。例如，n=3時，3個整數(shù)25、324、456連成的最大整數(shù)為45?632?425；又如，n=4時，4個整數(shù)2、9、17、386連成的最大整數(shù)為9?386?217。此題很容易想到使用貪婪法，我們考慮把整數(shù)按從大到小的順序連接起來，按這種貪婪標準，很容易找到反例：12、121應(yīng)該組成12121而非12112，這樣情況就有很多種了。是不是此題不能用貪婪法呢？其實此題是可以用貪婪法來求解的，只是剛剛的貪婪標準不對，正確的貪婪標準是：先把整數(shù)化成字符串，然后再比較a+b和b+a，如果a+b>b+a，就把a排在b的前面，反之那么把a排在b的后面。

貪婪算法所作的選擇可以依賴于以往所作過的選擇，但決不依賴于將來的選擇，也不依賴于子問題的解，因此貪婪算法與其他算法相比具有一定的速度優(yōu)勢。如果一個問題可以同時用幾種方法解決，那么貪婪算法應(yīng)該是最好的選擇之一。

5.3.3成竹在胸—動態(tài)規(guī)劃法

動態(tài)規(guī)劃(DynamicProgramming)法是20世紀50年代初美國數(shù)學(xué)家等人在研究多階段決策過程(MultistepDecisionProcess)的優(yōu)化問題時，把多階段過程轉(zhuǎn)化為一系列單階段問題，利用各階段之間的關(guān)系，逐個求解，所創(chuàng)立的解決這類過程優(yōu)化問題的新方法。

動態(tài)規(guī)劃問世以來，在經(jīng)濟管理、生產(chǎn)調(diào)度、工程技術(shù)和最優(yōu)控制等方面得到了廣泛的應(yīng)用。例如，最短路線、庫存管理、資源分配、設(shè)備更新、排序、裝載等問題，用動態(tài)規(guī)劃法比用其他方法求解更為方便。動態(tài)規(guī)劃程序設(shè)計是解決最優(yōu)化問題的一種途徑和方法，而不是一種特殊算法。不像搜索或數(shù)值計算那樣，具有一個標準的數(shù)學(xué)表達式和明確清晰的解題方法。由于各種問題的性質(zhì)不同，確定最優(yōu)解的條件也互不相同，因而動態(tài)規(guī)劃的設(shè)計方法對不同的問題，有各具特色的解題方法，而不存在一種萬能的動態(tài)規(guī)劃算法，可以解決各類最優(yōu)化問題。因此讀者在學(xué)習(xí)時，在正確理解根本概念和方法的根底上，必須具體問題具體分析處理，以豐富的想象力去建立模型，用創(chuàng)造性的技巧去求解。1．動態(tài)規(guī)劃法所能解決的問題特征

(1)最優(yōu)子結(jié)構(gòu)性質(zhì)：一個最優(yōu)化策略具有這樣的性質(zhì)，不管過去狀態(tài)和決策如何，對前面的決策所形成的狀態(tài)而言，余下的諸決策必須構(gòu)成最優(yōu)策略。簡而言之，一個最優(yōu)化策略的子策略總是最優(yōu)的。

(2)無后效性：將各階段按照一定的次序排列好之后，對于某個給定的階段狀態(tài)，它以前各階段的狀態(tài)無法直接影響它未來的決策，而只能通過當前的這個狀態(tài)。換句話說，每個狀態(tài)都是過去歷史的一個完整總結(jié)。這就是無后效性，又稱為無后向性。(3)子問題的重疊性：即子問題之間是不獨立的，一個子問題在下一階段決策中可能被屢次使用到。該性質(zhì)并不是動態(tài)規(guī)劃適用的必要條件，但是如果沒有這條性質(zhì)，動態(tài)規(guī)劃算法同其他算法相比就不具備優(yōu)勢。2．動態(tài)規(guī)劃算法的根本思路

動態(tài)規(guī)劃算法的根本思想與分治法類似，也是將待求解的問題分解為假設(shè)干個子問題(階段)，按順序求解子階段，前一子問題的解為后一子問題的求解提供了有用的信息。在求解任一子問題時，列出各種可能的局部解，通過決策保存那些有可能到達最優(yōu)的局部解，丟棄其他局部解。依次解決各子問題，最后一個子問題就是初始問題的解。由于動態(tài)規(guī)劃解決的問題多數(shù)有重疊子問題這個特點，為減少重復(fù)計算，對每一個子問題只解一次，將其不同階段的不同狀態(tài)保存在一個二維數(shù)組中。動態(tài)規(guī)劃法與分治法最大的差異是：適合于用動態(tài)規(guī)劃法求解的問題，經(jīng)分解后得到的子問題往往不是互相獨立的(即下一個子階段的求解是建立在上一個子階段的解的根底上，進行進一步的求解)。3.動態(tài)規(guī)劃算法的求解步驟

動態(tài)規(guī)劃所處理的問題是一個多階段決策問題，一般由初始狀態(tài)開始，通過對中間階段決策的選擇，到達結(jié)束狀態(tài)。動態(tài)規(guī)劃的設(shè)計都有著一定的模式，一般要經(jīng)歷以下幾個步驟。

(1)劃分階段：按照問題的時間或空間特征，把問題分為假設(shè)干個階段。在劃分階段時，注意劃分后的階段一定要是有序的或者是可排序的，否那么問題就無法求解。

(2)確定狀態(tài)和狀態(tài)變量：將問題開展到各個階段時所處于的各種客觀情況用不同的狀態(tài)表示出來。當然，狀態(tài)的選擇要滿足無后效性。(3)確定決策并寫出狀態(tài)轉(zhuǎn)移方程：因為決策和狀態(tài)轉(zhuǎn)移有著天然的聯(lián)系，狀態(tài)轉(zhuǎn)移就是根據(jù)上一階段的狀態(tài)和決策來導(dǎo)出本階段的狀態(tài)。所以如果確定了決策，狀態(tài)轉(zhuǎn)移方程也就可寫出。但事實上常常是反過來做，根據(jù)相鄰兩個階段的狀態(tài)之間的關(guān)系來確定決策方法和狀態(tài)轉(zhuǎn)移方程。

(4)尋找邊界條件：給出的狀態(tài)轉(zhuǎn)移方程是一個遞推式，需要一個遞推的終止條件或邊界條件。

實際應(yīng)用中可以按以下簡化的步驟進行設(shè)計：

(1)分析最優(yōu)解的性質(zhì)，并刻畫最優(yōu)解的結(jié)構(gòu)特征。

(2)遞歸定義最優(yōu)值。

(3)自底向上計算出最優(yōu)值，并記錄相關(guān)信息。

(4)根據(jù)計算最優(yōu)值時得到的信息，構(gòu)造出最優(yōu)解。

4．動態(tài)規(guī)劃算法設(shè)計模式

根據(jù)上述動態(tài)規(guī)劃設(shè)計的步驟，可得到大體解題框架如下:

(1)初始化(邊界條件)。

(2)fori:=2ton(順推法)或fori:=n－1to1(逆推法)，對i階段的每一個決策點求局部最優(yōu)。

(3)確定和輸出結(jié)束狀態(tài)的值。

例5-6一個有N個整數(shù)元素的一位數(shù)組(A[0]，A[1]，…,A[n－1]，A[n])，這個數(shù)組當然有很多子數(shù)組，那么數(shù)組之和的最大值是什么呢？明確一下題意：

(1)子數(shù)組必須是連續(xù)的。

(2)不需要返回子數(shù)組的具體位置。

(3)數(shù)組中包含正整數(shù)、零和負整數(shù)。

例如：

數(shù)組{1，－2，3，5，－3，2}的返回值為8；

數(shù)組{0，－2，3，5，－1，2}的返回值為9；

數(shù)組{－9，－2，－3，－5，－6}的返回值為－2，注意子數(shù)組不能為空。根據(jù)題意，可以考慮數(shù)組的第一個元素，以及最大的一段數(shù)組(A[i]，…，A[j])和A[0]的關(guān)系，有以下幾種情況：

(1)當0=i=j時，元素A[0]本身構(gòu)成和最大的一段；

(2)當0=i<j時，和最大的一段以A[0]開始；

(3)當0<i時，元素A[0]和最大的一段沒有關(guān)系。

從上面三種情況看出：可以將一個大問題(N個元素數(shù)組)轉(zhuǎn)化為一個較小的問題(N－1個元素的數(shù)組)。假設(shè)已經(jīng)知道(A[1]，…，A[n－1])中和最大的一段數(shù)組之和為All[1]，并且已經(jīng)知道(A[1]，…，A[n－1])中包含A[1]的和最大的一段數(shù)組為Start[1]，那么不難看出(A[0]，…，A[n])中問題的解All[0]=max{A[0]，A[0]+start[1]，All[1]}。通過這樣的分析，可以看出這個問題無后效性，可以用動態(tài)規(guī)劃來解決，算法如下：5.3.4志在四方—周游法

1．遍歷方案

從二叉樹的遞歸定義可知，一棵非空的二叉樹由根節(jié)點及左、右子樹這三個根本局部組成，如下圖，因此，在任一給定節(jié)點上，可以按某種次序執(zhí)行三個操作：

(1)訪問節(jié)點本身(N)。

(2)遍歷該節(jié)點的左子樹(L)。

(3)遍歷該節(jié)點的右子樹(R)。

以上三種操作有六種執(zhí)行次序：NLR、LNR、LRN、NRL、RNL、RLN。

注意：

前三種次序與后三種次序?qū)ΨQ，故只討論先左后右的前三種次序。圖5.1遍歷二叉樹的搜索路線

2．三種遍歷的命名

根據(jù)訪問節(jié)點操作發(fā)生位置命名：

(1)NLR：前序遍歷(PreorderTraversal，亦稱先序遍歷)—訪問節(jié)點的操作發(fā)生在遍歷其左右子樹之前。

(2)?LNR：中序遍歷(InorderTraversal)—訪問節(jié)點的操作發(fā)生在遍歷其左右子樹之中(間)。

(3)LRN：后序遍歷(PostorderTraversal)—訪問節(jié)點的操作發(fā)生在遍歷其左右子樹之后。

注意：由于被訪問的節(jié)點必是某子樹的根，所以N(Node)、L(Leftsubtlee)和R(Rightsubtree)又可解釋為根、根的左子樹和根的右子樹。NLR、LNR和LRN分別又稱為先根遍歷、中根遍歷和后根遍歷。3．遍歷算法

1)中序遍歷的遞歸算法

假設(shè)二叉樹非空，那么依次執(zhí)行如下操作：

(1)遍歷左子樹；

(2)訪問根節(jié)點；

(3)遍歷右子樹。

中序遍歷圖所示的二叉樹時，得到的中序序列為DBAECF。2)先序遍歷的遞歸算法

假設(shè)二叉樹非空，那么依次執(zhí)行如下操作：

(1)訪問根節(jié)點；

(2)遍歷左子樹；

(3)遍歷右子樹。

先序遍歷圖所示的二叉樹時，得到的中序序列為ABDCEF。3)后序遍歷得遞歸算法定義

假設(shè)二叉樹非空，那么依次執(zhí)行如下操作：

(1)遍歷左子樹；

(2)遍歷右子樹；

(3)訪問根節(jié)點。

后序遍歷圖所示的二叉樹時，得到的中序序列為DBEFCA。本卷須知：

(1)在搜索路線中，假設(shè)訪問節(jié)點均是第一次經(jīng)過節(jié)點時進行的，那么是前序遍歷；假設(shè)訪問節(jié)點均是在第二次(或第三次)經(jīng)過節(jié)點時進行的，那么是中序遍歷(或后序遍歷)。只要將搜索路線上所有在第一次、第二次和第三次經(jīng)過的節(jié)點分別列表，即可分別得到該二叉樹的前序序列、中序序列和后序序列。

(2)上述三種序列都是線性序列，有且僅有一個開始節(jié)點和一個終端節(jié)點，其余節(jié)點都有且僅有一個前趨節(jié)點和一個后繼節(jié)點。為了區(qū)別于樹形結(jié)構(gòu)中前趨(即雙親)節(jié)點和后繼(即孩子)節(jié)點的概念，對上述三種線性序列，要在某節(jié)點的前趨和后繼之前冠以其遍歷次序名稱。

例5-7圖所示的二叉樹中節(jié)點C，其前序前趨節(jié)點是D，前序后繼節(jié)點是E；中序前趨節(jié)點是E，中序后繼節(jié)點是F；后序前趨節(jié)點是F，后序后繼節(jié)點是A。但是就該樹的邏輯結(jié)構(gòu)而言，C的前趨節(jié)點是A，后繼節(jié)點是E和F。

4．算法遞歸實現(xiàn)

在這里，假設(shè)所有的二叉樹都以數(shù)組的形式儲存。

(1)中序遍歷。

procedure

mid(i:longint);

begin

if

a[i*2]<>0

then

mid(i*2)；

write(a[i]);

if

a[i*2+1]<>0

then

mid(i*2+1)；

end;(2)先序遍歷。

procedure

first(i:longint);

begin

write(a[i]);

ifa[i*2]<>0then

first(i*2)；

ifa[i*2+1]<>0then

first(i*2+1)；

end;(3)后序遍歷。

procedure

last(i:longint);

begin

if

a[i*2]<>0

then

last(i*2)；

if

a[i*2+1]<>0

then

last(i*2+1)；

write(a[i]);

end;5.3.5迷途知返—回溯法

1．回溯法所能解決的問題特征

可用回溯法求解的問題P，通常要能表達為：對于的由n元組(x1，x2，…，xn)組成的一個狀態(tài)空間E={(x1，x2，…，xn)∣xi∈Si，i=1，2，…，n}，給定關(guān)于n元組中的一個分量的一個約束集D，要求E中滿足D的全部約束條件的所有n元組。其中Si是分量xi的定義域，且|Si|有限，i=1，2，…，n。我們稱E中滿足D的全部約束條件的任一n元組為問題P的一個解。我們發(fā)現(xiàn)，對于許多問題，所給定的約束集D具有完備性，即i元組(x1，x2，…，xi)滿足D中僅涉及x1，x2，…，xi的所有約束意味著j(j<=i)元組(x1，x2，…，xj)一定也滿足d中僅涉及x1，x2，…，xj的所有約束，其中i=1，2，…，n。換句話說，只要存在0≤j≤n-1，使得(x1，x2，…，xj)違反d中僅涉及x1，x2，…，xj的約束之一，那么以(x1，x2，…，xj)為前綴的任何n元組(x1，x2，…，xj，xj+1，…，xn)一定也違反d中僅涉及x1，x2，…，xi的一個約束(j≤i≤n)。因此，對于約束集d具有完備性的問題P，一旦檢測斷定某個j元組(x1，x2，…，xj)違反d中僅涉及x1，x2，…，xj的一個約束，就可以肯定，以(x1，x2，…，xj)為前綴的任何n元組(x1，x2，…，xj，xj+1，…，xn)都不會是問題P的解，因而就不必去搜索、檢測它們?；厮莘ㄕ轻槍@類問題，利用這類問題的上述性質(zhì)而提出的比枚舉法效率更高的算法。

2．回溯法的根本要素

(1)約束條件：包括隱性的和顯性的，顯約束指對問題的解的取值范圍限定，隱約束指為滿足問題的解而對不同分量之間施加的約束。

(2)解空間：對于問題的一個實例，解向量滿足顯約束的所有n元組構(gòu)成該實例的一個解空間。為了搜索方便，一般用樹或圖的形式將問題的解空間有效地組織起來，稱為狀態(tài)樹，它是構(gòu)造深度搜索過程的依據(jù)，整個搜索以此樹展開。

注意：同一個問題的顯約束可能有多種，相應(yīng)解空間的大小就會不同，通常情況下，解空間越小，算法的搜索效率越高。3．回溯法算法的求解步驟

(1)針對所給問題，確定問題的解空間。

首先應(yīng)明確問題的解空間，問題的解空間應(yīng)至少包含問題的一個(最優(yōu))解。

(2)確定節(jié)點的擴展搜索規(guī)那么。

搜索思想：從根節(jié)點開始，以深度優(yōu)先搜索的方式進行搜索。在搜索過程中，當前的擴展節(jié)點延縱深方向移向一個新節(jié)點，判斷新節(jié)點是否滿足隱約束。如果滿足，那么新節(jié)點成為當前的擴展節(jié)點，繼續(xù)深一層的搜索；如果不滿足，那么換到擴展節(jié)點的兄弟節(jié)點(其他分支)繼續(xù)搜索。如果新節(jié)點沒有兄弟節(jié)點，或兄弟節(jié)點已全部搜索完畢，那么擴展節(jié)點成為死節(jié)點，搜索回溯到其父節(jié)點處繼續(xù)進行。搜索過程直到找到問題的解或根節(jié)點變成死節(jié)點為止。(3)以深度優(yōu)先方式搜索解空間，并在搜索過程中用剪枝函數(shù)防止無效搜索。

在深度優(yōu)先搜索的過程中，不滿足隱約束的分支被剪掉，只沿著滿足隱約束的分支搜索問題的解，從而防止了無效搜索，加快了速度。因此，隱約束又稱為剪枝函數(shù)。剪枝函數(shù)一般有兩種：一是判斷是否能夠得到可行解的隱約束，稱為約束函數(shù)；二是判斷是否有可能得到最優(yōu)解的隱約束，稱為限界函數(shù)?；厮莘ㄊ且环N具有約束函數(shù)或限界函數(shù)的深度優(yōu)先搜索法。4．回溯算法設(shè)計模式

回溯算法通常采用遞歸技術(shù)，也可以選用非遞歸技術(shù)。在設(shè)計過程中，參數(shù)t代表當前擴展節(jié)點在解空間樹中所處的層次；變量n代表問題的規(guī)模，也是解空間的深度；s(n，t)代表當前擴展節(jié)點處未搜索的子樹的起始編號，e(n，t)代表當前擴展節(jié)點處未搜索的子樹的終止編號；d(i)代表當前擴展節(jié)點可選分支上的數(shù)據(jù)；X是用來記錄問題當前解的數(shù)組；constraint(t)代表當前擴展節(jié)點處的約束函數(shù)；bound(t)代表當前擴展節(jié)點處的限界函數(shù)。滿足約束和限界函數(shù)那么繼續(xù)深一層次的搜索，否那么就剪掉相應(yīng)的子樹。Backtrack(t)代表從第t層開始搜索問題的解。(1)遞歸回溯模式。

例5-8數(shù)的劃分(noip2001tg)。

問題描述：將整數(shù)n分成k份，且每份不能為空，任意兩份不能相同(不考慮順序)。例如，n=7，k=3，下面三種分法被認為是相同的：1，1，5；1，5，1；5，1，1。有多少種不同的分法？

輸入：n，k(6<n<=200，2<=k<=6)；

輸出：一個整數(shù)，即不同的分法。

例如：

輸入：7

3；

輸出：4

{四種分法為：1，1，5；1，2，4；1，3，3；2，2，3}。算法分析：此題可以用回溯法求解，設(shè)自然數(shù)n拆分為a1，a2，…，ak，必須滿足以下兩個條件：

(1)?n=a1+a2+…+ak；

(2)?a1<=a2<=…<=ak(防止重復(fù)計算)。

現(xiàn)假設(shè)己求得的拆分數(shù)為a1，a2，…，ai，且都滿足以上兩個條件，設(shè)sum=n-a1-a2-…-ai，可根據(jù)不同的情形進行處理：

(1)如果i=k，那么得到一個解，那么計數(shù)器t加1，并回溯到上一步，改變ai-1的值；

(2)如果i<k且sum>=ai，那么添加下一個元素ai+1；

(3)如果i<k且sum<ai，那么說明達不到目標，回溯到上一步，改變ai-1的值。算法實現(xiàn)步驟如下：

(1)輸入自然數(shù)n，k并初始化：t:=0;

i:=1;a[i]:=1;

sum:=n-1;

nk:=n

div

k。

(2)如果a[1]<=nk重復(fù)：假設(shè)i=k，搜索到一個解，計數(shù)器t=t+1;并回溯；否那么，假設(shè)sum>=a[i]那么繼續(xù)搜索，假設(shè)sum<a[i]那么回溯。搜索時，inc(i);a[i]:=a[i-1];sum:=sum-a[i];；回溯時，dec(i);

inc(a[i]);

sum:=sum+a[i+1]-1。

(3)輸出。5.3.6畫地為牢—分枝限界法

1．分枝限界算法的根本思路

分枝限界算法常以廣度優(yōu)先或以最小消耗(最大收益)優(yōu)先的方式搜索問題的解空間樹。問題的解空間樹是表示解空間的一棵有序樹。在搜索問題的解空間樹時，分枝限界算法與回溯法對當前節(jié)點所采用的擴展方式不同：在分枝限界算法中，每一個活節(jié)點(一個自身已生成但其子節(jié)點還沒有全部生成的節(jié)點)只有一次時機成為擴展節(jié)點，某節(jié)點成為擴展節(jié)點后，就一次性產(chǎn)生所有子節(jié)點。在這些子節(jié)點中，那些導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的子節(jié)點被舍棄，其余子節(jié)點被參加活節(jié)點表中。此后，從活節(jié)點表中取下一節(jié)點成為當前擴展節(jié)點，并重復(fù)上述節(jié)點擴展過程，直到找到所需的解或活節(jié)點表為空時為止。2．分枝節(jié)點的選擇

對搜索樹上的某些點必須作出分枝決策，即但凡界限小于迄今為止所有可行解最小下界的任何子集(節(jié)點)，都有可能作為分枝的選擇對象(對求最小值問題而言)。怎樣選擇搜索樹上的節(jié)點作為下次分枝的節(jié)點呢？有兩個原那么：

(1)從最小下界分枝(優(yōu)先隊列式分枝限界法)：每次算完界限后，把搜索樹上當前所有葉節(jié)點的界限進行比較。找出限界最小的節(jié)點，此節(jié)點即為下次分枝的節(jié)點。

優(yōu)點：檢查子問題較少，能較快地求得最正確解。

缺點：要存儲很多葉節(jié)點的界限及對應(yīng)的消耗矩陣，會花費很多內(nèi)存空間。(2)從最新產(chǎn)生的最小下界分枝(隊列式(FIFO)分枝限界法)：從最新產(chǎn)生的各子集中按順序選擇各節(jié)點進行分枝，對于下界比上界還大的節(jié)點不進行分枝。

優(yōu)點：節(jié)省了空間。

缺點：需要較多的分枝運算，消耗的時間較多。

這兩個原那么更進一步說明了在算法設(shè)計中的時空轉(zhuǎn)換概念。

分枝定界法已經(jīng)成功地應(yīng)用于求解整數(shù)規(guī)劃問題、生產(chǎn)進度表問題、貨郎擔問題、選址問題、背包問題以及可行解的數(shù)目為有限的許多其他問題