計算機(jī)算法設(shè)計與分析 五種常用算法

淺論五個常用算法軟件工程姓名：余智昆專業(yè)班級：軟件102班日期：2012.2.18【摘要】隨著信息工業(yè)的發(fā)展，計算機(jī)已然成為人們?nèi)粘Ｉ钪胁豢苫蛉钡墓ぞ?。目前，各行業(yè)、各領(lǐng)域都廣泛采用了計算機(jī)信息技術(shù)，并由此產(chǎn)生出開發(fā)各種應(yīng)用軟件的需求。為了以最少的成本、最快的速度、最好的質(zhì)量開發(fā)出適應(yīng)各種應(yīng)用需求的軟件，必須遵循軟件工程的原則。設(shè)計一個高效的程序不僅需要編程小技巧，更需要合理的數(shù)據(jù)組織和清晰高效的算法，這正是計算機(jī)科學(xué)領(lǐng)域數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計所研究的主要內(nèi)容。通過對計算機(jī)算法系統(tǒng)的學(xué)習(xí)與研究，掌握算法設(shè)計的主要方法，培養(yǎng)對算法的計算復(fù)雜性正確分析的能力，為獨立設(shè)計算法和對算法進(jìn)行復(fù)雜性分析奠定了堅實的理論基礎(chǔ)。在計算機(jī)語言中，算法的概念是至關(guān)重要的，一個優(yōu)秀的軟件，設(shè)計出有效的算法將起決定性的作用。本篇論文將對五種常用算法概括總結(jié)，希望能夠?qū)λ惴ㄓ懈钊氲睦斫??！娟P(guān)鍵詞】遞歸與分治策略、動態(tài)規(guī)劃、貪心算法、回溯法、分之界限法

【正文】一、遞歸與分治策略A.1.遞歸：一個直接或間接調(diào)用自身的算法稱為遞歸算法。在計算機(jī)算法設(shè)計與分析中，使用遞歸技術(shù)往往使函數(shù)的定義和算法的描述簡潔且易于理解。有些數(shù)據(jù)結(jié)構(gòu)如二叉樹等，由于其本身固有的遞歸特性，特別適合用遞歸形式來描述。還有一些問題，雖然本身并沒有明顯的遞歸結(jié)構(gòu)，但是用遞歸技術(shù)來求解設(shè)計出的算法簡潔易懂且易于分析。遞歸算法要求：遞歸算法所體現(xiàn)的“重復(fù)”一般有三個要求一是每次調(diào)用在規(guī)模上都有所縮?。ㄍǔＪ菧p半）；二是相鄰兩次重復(fù)之間有緊密的聯(lián)系，前一次要為后一次做準(zhǔn)備（通常前一次的輸出就作為后一次的輸入）；結(jié)束三是在問題的規(guī)模極小時必須用直接給出解答而不再進(jìn)行遞歸調(diào)用，因而每次遞歸調(diào)用都是有條件的（以規(guī)模未達(dá)到直接解答的大小為條件），無條件遞歸調(diào)用將會成為死循環(huán)而不能正常結(jié)束。結(jié)束開始3.遞歸過程實質(zhì)：~rr一遞歸算法的實現(xiàn)類似于多個算法的嵌套調(diào)用，只是n調(diào)用算法和被調(diào)用算法是同一個算法。和每次調(diào)用相關(guān)的一個重要概念是遞歸算法的調(diào)用層次。若調(diào)用一個遞歸算法的主算法為第0層算法，則主算法調(diào)用遞歸算法為進(jìn)入第一層調(diào)用；從第i層遞歸調(diào)用本算法為進(jìn)入第i+1層調(diào)用。反之，退出第i否層調(diào)用，則返回第i-1」層遞歸調(diào)用。為了保證遞歸調(diào)用正確執(zhí)行，系統(tǒng)要建立一個遞歸調(diào)用工作棧，為各層次的調(diào)用數(shù)據(jù)存儲區(qū)。4.遞歸算法的優(yōu)缺點：結(jié)構(gòu)清晰、可讀性強(qiáng)，且容易用數(shù)學(xué)歸納法證明算法的正確性，因此它為設(shè)計算法、調(diào)試程序帶來很大的方便。然而，遞歸算法的運(yùn)行效率較低，無論是耗費(fèi)的計算時間還是占用的空間都要比非遞歸算法要多。因此，我們使用遞歸算法，必須權(quán)衡運(yùn)行時間與內(nèi)存這兩者的消耗。B.1.分治策略：對于一個規(guī)模為n的問題，若該問題可以容易地解決（比如說規(guī)模n較小）則直接解決，否則將其分解為k個規(guī)模較小的子問題，這些子問題互相獨立且與原問題形式相同，遞歸地解這些子問題，然后將各子問題的解合并得到原問題的解。這種算法設(shè)計策略叫做分治法。它的一般算法設(shè)計模式：Divid-and-Conquer（p）If（|p|<=n0）Adhoc（p）;DividPintosmallersubinstancesP1,P2,…，Pk;for（i=1;i<=k;i++）yi=Divide-and-Conquer（pi）;returnMerge（y1,y2,?yk）;}分治法的基本步驟：分治法在每一層遞歸上都有三個步驟：分解：將原問題分解為若干個規(guī)模較小，相互獨立，與原問題形式相同的子問題；解決：若子問題規(guī)模較小而容易被解決則直接解，否則遞歸地解各個子問題；合并：將各個子問題的解合并為原問題的解。分治的應(yīng)用：分治法所能解決的問題一般具有以下幾個特征：（1）該問題的規(guī)?？s小到一定的程度就可以容易地解決；（2）該問題可以分解為若干個規(guī)模較小的相同問題，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)；（3）利用該問題分解出的子問題的解可以合并為該問題的解；（4）該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子子問題。分治策略在計算機(jī)算法中應(yīng)用還是比較多的，如：二分搜索技術(shù)、大整數(shù)乘法、Strassen矩陣乘法、期盼覆蓋、合并排序、快速排序、線性時間選擇。最接近點問題、循環(huán)賽日程表。二、動態(tài)規(guī)劃基本思想與分治法類似，也是將待求解的問題分解為若干個子問題（階段），按順序求解子階段，前一子問題的解，為后一子問題的求解提供了有用的信息。在求解任一子問題時，列出各種可能的局部解，通過決策保留那些有可能達(dá)到最優(yōu)的局部解，丟棄其他局部解。依次解決各子問題，最后一個子問題就是初始問題的解。由于動態(tài)規(guī)劃解決的問題多數(shù)有重疊子問題這個特點，為減少重復(fù)計算，對每一個子問題只解一次，將其不同階段的不同狀態(tài)保存在一個二維數(shù)組中。與分治法最大的差別是：適合于用動態(tài)規(guī)劃法求解的問題，經(jīng)分解后得到的子問題往往不是互相獨立的（即下一個子階段的求解是建立在上一個子階段的解的基礎(chǔ)上，進(jìn)行進(jìn)一步的求解）。適合解哪類問題：能采用動態(tài)規(guī)劃求解的問題的一般要具有3個性質(zhì)：（1）最優(yōu)化原理：如果問題的最優(yōu)解所包含的子問題的解也是最優(yōu)的，就稱該問題具有最優(yōu)子結(jié)構(gòu)，即滿足最優(yōu)化原理。（2）無后效性：即某階段狀態(tài)一旦確定，就不受這個狀態(tài)以后決策的影響。也就是說，某狀態(tài)以后的過程不會影響以前的狀態(tài)，只與當(dāng)前狀態(tài)有關(guān)。（3）有重疊子問題：即子問題之間是不獨立的，一個子問題在下一階段決策中可能被多次使用到。（該性質(zhì)并不是動態(tài)規(guī)劃適用的必要條件，但是如果沒有這條性質(zhì)，動態(tài)規(guī)劃算法同其他算法相比就不具備優(yōu)勢）3、求解的基本步驟動態(tài)規(guī)劃所處理的問題是一個多階段決策問題，一般由初始狀態(tài)開始，通過對中間階段決策的選擇，達(dá)到結(jié)束狀態(tài)。這些決策形成了一個決策序列，同時確定了完成整個過程的一條活動路線（通常是求最優(yōu)的活動路線）。如圖所示。動態(tài)規(guī)劃的設(shè)計都有著一定的模式，一般要經(jīng)歷以下幾個步驟。初始狀態(tài)f|決策l|f|決策2|f???f|決策n|f結(jié)束狀態(tài)圖1動態(tài)規(guī)劃決策過程示意圖劃分階段：按照問題的時間或空間特征，把問題分為若干個階段。在劃分階段時，注意劃分后的階段一定要是有序的或者是可排序的，否則問題就無法求解。確定狀態(tài)和狀態(tài)變量：將問題發(fā)展到各個階段時所處于的各種客觀情況用不同的狀態(tài)表示出來。當(dāng)然，狀態(tài)的選擇要滿足無后效性。確定決策并寫出狀態(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)移方程。尋找邊界條件：給出的狀態(tài)轉(zhuǎn)移方程是一個遞推式，需要一個遞推的終止條件或邊界條件。一般，只要解決問題的階段、狀態(tài)和狀態(tài)轉(zhuǎn)移決策確定了，就可以寫出狀態(tài)轉(zhuǎn)移方程(包括邊界條件)。實際應(yīng)用中可以按以下幾個簡化的步驟進(jìn)行設(shè)計：分析最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征。遞歸的定義最優(yōu)解。以自底向上或自頂向下的記憶化方式(備忘錄法)計算出最優(yōu)值根據(jù)計算最優(yōu)值時得到的信息，構(gòu)造問題的最優(yōu)解三、貪心算法概念：用貪婪法設(shè)計算法的特點是一步一步地進(jìn)行，常以當(dāng)前情況為基礎(chǔ)根據(jù)某個優(yōu)化測度作最優(yōu)選擇，而不考慮各種可能的整體情況，它省去了為找最優(yōu)解要窮盡所有可能而必須耗費(fèi)的大量時間，它采用自頂向下，以迭代的方法做出相繼的貪心選擇，每做一次貪心選擇就將所求問題簡化為一個規(guī)模更小的子問題，通過每一步貪心選擇，可得到問題的一個最優(yōu)解，雖然每一步上都要保證能獲得局部最優(yōu)解，但由此產(chǎn)生的全局解有時不一定是最優(yōu)的，所以貪婪法不要回溯。貪婪算法可解決的問題通常大部分都有如下的特性：有一個以最優(yōu)方式來解決的問題。為了構(gòu)造問題的解決方案，有一個候選的對象的集合：比如不同面值的硬幣。隨著算法的進(jìn)行，將積累起其它兩個集合：一個包含已經(jīng)被考慮過并被選出的候選對象，另一個包含已經(jīng)被考慮過但被丟棄的候選對象有一個函數(shù)來檢查一個候選對象的集合是否提供了問題的解答。該函數(shù)不考慮此時的解決方法是否最優(yōu)還有一個函數(shù)檢查是否一個候選對象的集合是可行的，也即是否可能往該集合上添加更多的候選對象以獲得一個解。和上一個函數(shù)一樣，此時不考慮解決方法的最優(yōu)性。選擇函數(shù)可以指出哪一個剩余的候選對象最有希望構(gòu)成問題的解。最后,目標(biāo)函數(shù)給出解的值基本思路建立數(shù)學(xué)模型來描述問題把求解的問題分成若干個子問題對每一子問題求解，得到子問題的局部最優(yōu)解4.把子問題的解局部最優(yōu)解合成原來解問題的一個解相同點不同點動態(tài)規(guī)劃都是一種遞推算法均有局部最優(yōu)解來推導(dǎo)全局最優(yōu)解需要記錄之前的所有最優(yōu)解動態(tài)規(guī)劃的關(guān)鍵是狀態(tài)轉(zhuǎn)移方程，即如何由以求出的局部最優(yōu)解來推導(dǎo)全局最優(yōu)解邊界條件：即最簡單的，可以直接得出的局部最優(yōu)解貪心算法作出的每步貪心決策都無法改變，因為貪心策略是由上一步的最優(yōu)解推導(dǎo)下一步的最優(yōu)解，而上一部之前的最優(yōu)解則不作保留貪心法正確的條件是:每一步的最優(yōu)解一定包含上一步的最優(yōu)解圖2動態(tài)規(guī)劃與貪心算法的異同點四、回溯法概念：回溯法（探索與回溯法）是一種選優(yōu)搜索法，按選優(yōu)條件向前搜索，以達(dá)到目標(biāo)。但當(dāng)探索到某一步時，發(fā)現(xiàn)原先選擇并不優(yōu)或達(dá)不到目標(biāo)，就退回一步重新選擇，這種走不通就退回再走的技術(shù)為回溯法，而滿足回溯條件的某個狀狀態(tài)的點稱為'回溯點”。用回溯法解題的一般步驟（1）針對所給問題，定義問題的解空間（2）確定易于搜索的解空間結(jié)構(gòu)（3）以深度優(yōu)先方式搜索解空間，并在搜索過程中用剪枝函數(shù)避免無效搜索回溯法的一般流程和技術(shù)在用回溯法求解有關(guān)問題的過程中，一般是一邊建樹，一邊遍歷該樹。在回溯法中我們一般采用非遞歸方法。下面，我們給出回溯法的非遞歸算法的一般流程：在用回溯法求解問題，也即在遍歷狀態(tài)空間樹的過程中，如果采用非遞歸方法，則我們一般要用到棧的數(shù)據(jù)結(jié)構(gòu)。這時，不僅可以用棧來表示正在遍歷的樹的結(jié)點，而且可以很方便地表示建立孩子結(jié)點和回溯過程。例如在組合問題中，我們用一個一維數(shù)組Stack［表示棧。開始?？?，則表示了樹的根結(jié)點。如果元素1進(jìn)棧，則表示建立并遍歷（1）結(jié)點；這時如果元素2進(jìn)棧，則表示建立并遍歷（1,2）結(jié)點；元素3再進(jìn)棧，則表示建立并遍歷（1,2,3）結(jié)點。這時可以判斷它滿足所有約束條件，是問題的一個解，輸出（或保存）。這時只要棧頂元素（3）出棧，即表示從結(jié)點（1,2,3）回溯到結(jié)點（1,2）。五、分支限界法概念：分支限界法常以廣度優(yōu)先或以最小耗費(fèi)（最大效益）優(yōu)先的方式搜索問題的解空間樹。在分支限界法中，每一個活結(jié)點只有一次機(jī)會成為擴(kuò)展結(jié)點?；罱Y(jié)點一旦成為擴(kuò)展結(jié)點，就一次性產(chǎn)生其所有兒子結(jié)點。在這些兒子結(jié)點中，導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的兒子結(jié)點被舍棄，其余兒子結(jié)點被加入活結(jié)點表中此后，從活結(jié)點表中取下一結(jié)點成為當(dāng)前擴(kuò)展結(jié)點，并重復(fù)上述結(jié)點擴(kuò)展過程。這個過程一直持續(xù)到找到所需的解或活結(jié)點表為空時為止。分支限界法的設(shè)計思路：設(shè)求解最大化問題，解向量為X=（x1,...,xn），xi的取值范圍為Si，ISil=ri。在使用分支限界搜索問題的解空間樹時，先根據(jù)限界函數(shù)估算目標(biāo)函數(shù)的界［down,up］，然后從根結(jié)點出發(fā)，擴(kuò)展根結(jié)點的r1個孩子結(jié)點，從而構(gòu)成分量x1的r1種可能的取值方式。對這r1個孩子結(jié)點分別估算可能的目標(biāo)函數(shù)bound(xl)，其含義：以該結(jié)點為根的子樹所有可能的取值不大于bound(xl)，即：bound(x1)>bound(x1,x2)>_>bound(x1,...,xn)若某孩子結(jié)點的目標(biāo)函數(shù)值超出目標(biāo)函數(shù)的下界，則將該孩子結(jié)點丟棄；否則，將該孩子結(jié)點保存在待處理結(jié)點表PT中。再取PT表中目標(biāo)函數(shù)極大值結(jié)點作為擴(kuò)展的根結(jié)點，重復(fù)上述。直到一個葉子結(jié)點時的可行解X=(x1,...,xn)，及目標(biāo)函數(shù)值bound(x1,...,xn)。求解目標(biāo)搜索方式的不同存儲方式分支限界法找出解空間樹中滿足約束條件的所有解深度優(yōu)先的方式搜索解空間樹隊列和優(yōu)先隊列回溯法找出滿足約束條件的一個解，或是在滿足約束條件的解中找出在某種意義下的最優(yōu)解深度優(yōu)先的方式搜