“常見(jiàn)經(jīng)典算法”分析與研究

劉放美+蔡增玉+付長(zhǎng)寬

摘 要： 經(jīng)典算法是計(jì)算機(jī)專業(yè)核心課程之一。計(jì)算機(jī)算法的優(yōu)劣，對(duì)于計(jì)算機(jī)硬件的利用和系統(tǒng)的性能具有重要的影響。算法也是計(jì)算機(jī)科學(xué)中重要的理論之一。本文對(duì)遞歸算法、分治算法、動(dòng)態(tài)規(guī)劃算法、貪心算法等經(jīng)典的算法進(jìn)行研究，著重闡述算法的設(shè)計(jì)思想、優(yōu)缺點(diǎn)及其應(yīng)用，并對(duì)算法的發(fā)展進(jìn)行了探索。

關(guān)鍵詞： 經(jīng)典算法； 設(shè)計(jì)思想； 優(yōu)缺點(diǎn)； 應(yīng)用； 展望

中圖分類號(hào)：TP301 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1006-8228（2017）11-58-03

Analysis and study on common classical algorithms

Liu Fangmei1， Cai Zengyu2， Fu Changkuan1

（software engineering college， Zhengzhou University of Light Industry， Zhengzhou， Henan 450002， China；

2. School of Computer and Communication Engineering， Zhengzhou University of Light Industry）

Abstract： Classical algorithm is one of the core courses in computer science. Computer algorithm has great effect on the performance and use of computer hardware system. Algorithm is also one of the most important theories in computer science. In this paper， the classical algorithms such as the recursive algorithm， partition algorithm， dynamic programming algorithm and greedy algorithm etc. are studied， the design idea， advantages and disadvantages， and the applications of the algorithms are emphatically expounded， and the development of the algorithms is explored.

Key words： classical algorithm； design idea； advantages and disadvantages； prospect

0 引言

算法是通過(guò)基本運(yùn)算及運(yùn)算規(guī)定的運(yùn)算順序所構(gòu)成的完整的解題步驟。算法要求設(shè)計(jì)好有限的、確切的計(jì)算序列，通過(guò)設(shè)計(jì)好的步驟和計(jì)算序列可以解決同類問(wèn)題。要設(shè)計(jì)出好的算法，就必須對(duì)存在的問(wèn)題有深入細(xì)致的了解，還要有獨(dú)特的思考方式，只有如此，才能有奇妙的算法思想，這正是解決問(wèn)題的關(guān)鍵。當(dāng)解決問(wèn)題的方式有多種多樣時(shí)，就會(huì)存在不同的算法思想，而它們?cè)诮鉀Q問(wèn)題時(shí)有各自的優(yōu)勢(shì)和不足，我們根據(jù)需求，選擇出最佳方案，用最合適的算法來(lái)解決現(xiàn)實(shí)中的問(wèn)題，并逐步探索研究未來(lái)算法的方向，這便是我們探究與發(fā)現(xiàn)的初衷[1]。

1 常見(jiàn)經(jīng)典算法分析

1.1 遞歸算法

遞歸算法是在一個(gè)函數(shù)定義或者聲明的過(guò)程中直接或者間接地又調(diào)用自身的一種方法。遞歸算法基本思想是，把一個(gè)復(fù)雜的大問(wèn)題轉(zhuǎn)化為規(guī)模較小且相似的子問(wèn)題來(lái)解決，可以用很少的代碼來(lái)解決多次重復(fù)計(jì)算的問(wèn)題，節(jié)省了運(yùn)算時(shí)間。對(duì)于一些產(chǎn)生情況非常多的算法問(wèn)題，利用窮舉法將是非常麻煩且不明智的，如果利用遞歸可以解決的話，就可以實(shí)現(xiàn)交換元素，函數(shù)調(diào)用函數(shù)，最終得到結(jié)果。這避免了重復(fù)計(jì)算，節(jié)約了運(yùn)算時(shí)間。

遞歸的缺陷是解決問(wèn)題的運(yùn)行效率非常低[2]，原因在于在遞歸調(diào)用的過(guò)程中，系統(tǒng)會(huì)為每一層的返回點(diǎn)，局部變量等開(kāi)辟了堆棧來(lái)存儲(chǔ)，而且如果出現(xiàn)遞歸調(diào)用次數(shù)過(guò)多，會(huì)出現(xiàn)堆棧溢出的問(wèn)題，這也是很可怕的。

我們應(yīng)該知道遞歸都用來(lái)解決哪些問(wèn)題，首先，它可以解決一些數(shù)據(jù)的定義，其次，它可以實(shí)現(xiàn)一些問(wèn)題求解，而且，數(shù)據(jù)的結(jié)構(gòu)形式也可以按照遞歸定義。按照遞歸的這些適用條件，我們很容易的想到，它可以解決我們經(jīng)常見(jiàn)到的Fibonacci函數(shù)，回溯算法，以及樹(shù)的遍歷，圖的搜索等相關(guān)的問(wèn)題。

1.2 分治算法

分治算法是把一個(gè)復(fù)雜的問(wèn)題分成了多個(gè)子問(wèn)題，逐步細(xì)分，直到子問(wèn)題可以直接求解，而子問(wèn)題的解的合并就是原問(wèn)題的解。分治法的基本思想是把一個(gè)不容易解決的子問(wèn)題分為規(guī)模較小的相似問(wèn)題，以便于可以直接求解，遞歸地解決這些子問(wèn)題，再將得到的子問(wèn)題的解合并，就得到了原問(wèn)題的解。

當(dāng)需要解決一個(gè)輸入規(guī)模（n）很大的問(wèn)題時(shí)，直接處理往往比較困難或者根本無(wú)法求解，我們希望把輸入規(guī)?？s小，即分成很多份，分別去解決，并且這些小問(wèn)題容易合起來(lái)從而解決整個(gè)問(wèn)題。這便是分治的優(yōu)勢(shì)所在，簡(jiǎn)單高效。但是分治法的合并步驟并不是很容易的，有的問(wèn)題的合并方法比較明確，而有的問(wèn)題的合并方法比較復(fù)雜，可能還需要討論多種合并方案，這也是一個(gè)小缺陷。

分治算法在一些應(yīng)用中是簡(jiǎn)單有效的，只要遇到的問(wèn)題可以分解為很多小規(guī)模的相似的子問(wèn)題，且子問(wèn)題獨(dú)立無(wú)依賴，最后又可以合并子問(wèn)題的解，就可以使用分治算法[3]。在一些經(jīng)典的排序問(wèn)題中，分治法起到了至關(guān)重要的作用。

1.3 動(dòng)態(tài)規(guī)劃算法

動(dòng)態(tài)規(guī)劃是一個(gè)過(guò)程，每次決策都依賴于當(dāng)前的狀態(tài)，然后會(huì)引起狀態(tài)的轉(zhuǎn)移，如何決策就是在變化中產(chǎn)生出來(lái)的，這樣的多階段最優(yōu)化決策解決問(wèn)題的過(guò)程就是動(dòng)態(tài)規(guī)劃。動(dòng)態(tài)規(guī)劃把要求解的問(wèn)題分成了很多子問(wèn)題，從簡(jiǎn)單的子問(wèn)題入手，求出它們的解，然后再得出最終答案。與分治算法不同的是，動(dòng)態(tài)規(guī)劃算法不是遞歸地求解每一個(gè)子問(wèn)題，而是從簡(jiǎn)單問(wèn)題的解入手，逐步求解，最后再求出原問(wèn)題的解，動(dòng)態(tài)規(guī)劃的高明之處就在于，它不會(huì)重復(fù)求解某些重復(fù)出現(xiàn)的子問(wèn)題，即一些重疊子問(wèn)題，所以計(jì)算的效率是非常高的。利用動(dòng)態(tài)規(guī)劃，可以保存已解決的子問(wèn)題的答案，在需要的時(shí)候再加以利用，這樣減少了大量的重復(fù)計(jì)算，節(jié)省了時(shí)間。求解過(guò)程就是先找出最優(yōu)解的結(jié)構(gòu)，遞歸定義一個(gè)最優(yōu)解的值，然后以自底向上的方式計(jì)算出最優(yōu)解的值，根據(jù)計(jì)算最優(yōu)解的值的信息，構(gòu)造出一個(gè)最優(yōu)解。但是動(dòng)態(tài)規(guī)劃在存儲(chǔ)中間過(guò)程產(chǎn)生的結(jié)果需要大量的空間，這是動(dòng)態(tài)規(guī)劃的明顯缺點(diǎn)，以空間換時(shí)間。endprint

對(duì)于動(dòng)態(tài)規(guī)劃算法來(lái)說(shuō)，它要依賴于問(wèn)題本身所具有的兩個(gè)重要性質(zhì)，一個(gè)是最優(yōu)子結(jié)構(gòu)性質(zhì)，另一個(gè)是子問(wèn)題重疊性質(zhì)[4]。只有提前滿足了這兩個(gè)條件，動(dòng)態(tài)規(guī)劃算法才能發(fā)揮它的高效作用。動(dòng)態(tài)規(guī)劃算法的應(yīng)用十分廣泛，典型應(yīng)用有矩陣連乘，在解決矩陣連乘問(wèn)題中，先從最簡(jiǎn)單的兩個(gè)矩陣相乘開(kāi)始，再看三個(gè)，四個(gè)，從而得到如何進(jìn)行乘法運(yùn)算，可以讓相乘的次數(shù)最少，最后我們可以求出矩陣連乘的次數(shù)和它們?nèi)绾蜗喑?。正是以大化小，才使解決問(wèn)題更加方便。動(dòng)態(tài)規(guī)劃還經(jīng)常應(yīng)用在最長(zhǎng)公共子序列、最大字段和數(shù)字三角形問(wèn)題上。

1.4 貪心算法

貪心算法是指在求解問(wèn)題時(shí)不從整體上考慮，只做出當(dāng)前最好的選擇，也就是局部最優(yōu)解。貪心算法的基本思想是找出整體中局部的最優(yōu)解，然后根據(jù)這些最優(yōu)解來(lái)得到整體的最優(yōu)解。在求解最優(yōu)化問(wèn)題算法中，一般會(huì)包括一系列的求解步驟，每一個(gè)求解步驟中都有一個(gè)選擇，然后得到問(wèn)題的一個(gè)解。貪心算法在具體求解問(wèn)題時(shí)是非常簡(jiǎn)單有效的，有時(shí)候雖然不能得到最優(yōu)解，但是可以得到近似解。貪心算法只選擇當(dāng)前看起來(lái)最好的選擇，而不去考慮它整體是不是最好的，正確的運(yùn)用貪心算法，應(yīng)該保證貪心策略無(wú)后效性，即：某個(gè)狀態(tài)以后過(guò)程不影響以前的狀態(tài)，只和當(dāng)前狀態(tài)有關(guān)。貪心算法對(duì)于解決很多問(wèn)題都是非常有效的，因?yàn)榫植孔顑?yōu)解很容易找到，所以簡(jiǎn)單易懂，效率較高，對(duì)于許多問(wèn)題都可以得到整體最優(yōu)解。貪心算法的缺點(diǎn)主要表現(xiàn)在它的“非理想性”。因?yàn)槲覀冋业降膯?wèn)題往往并不一定符合貪心算法的適用條件，即使達(dá)到了局部最優(yōu)，也很難得到我們想要的結(jié)果。貪心算法要想有效，就必須滿足問(wèn)題的約束，達(dá)到局部最優(yōu)的條件。如圖1所示的單源路徑問(wèn)題，雖然我們無(wú)法一眼看出最優(yōu)的結(jié)果，不知道該從哪一步走，但我們可以根據(jù)相鄰頂點(diǎn)的路徑來(lái)找出當(dāng)前最好的選擇，這便是先從局部最優(yōu)開(kāi)始[5]。

我們可以用dist[i]來(lái)記錄當(dāng)前的每個(gè)頂點(diǎn)的最短路徑，再?gòu)慕Y(jié)果中找出具有最短路徑的頂點(diǎn)，寫(xiě)入S集合中，等把所有的頂點(diǎn)都加入到了S集合中，dist就記錄了源頂點(diǎn)到其他頂點(diǎn)最短的路徑長(zhǎng)度。如表1所示：

此外，貪心算法還廣泛地應(yīng)用于活動(dòng)安排問(wèn)題，背包問(wèn)題，最優(yōu)裝載問(wèn)題等。

1.5 經(jīng)典算法的比較

經(jīng)典算法有很多，每個(gè)算法都有其獨(dú)到之處。本文對(duì)遞歸算法，分治算法，動(dòng)態(tài)規(guī)劃算法和貪心算法進(jìn)行歸納分析，總結(jié)了各自的優(yōu)缺點(diǎn)，如表2所示。要想真正地將算法用到恰到好處，就必須根據(jù)應(yīng)用場(chǎng)景，在相應(yīng)的條件下使用合適算法解決實(shí)際問(wèn)題[6]。

2 未來(lái)展望

很多人認(rèn)為，未來(lái)算法的重要性會(huì)變低，但是作為計(jì)算機(jī)科學(xué)領(lǐng)域最重要的基石之一的算法，它的重要性是會(huì)日益加強(qiáng)的。而且算法也將不局限于計(jì)算機(jī)和網(wǎng)絡(luò)，它所應(yīng)用的范圍也會(huì)越來(lái)越大。

2.1 算法在未來(lái)的重要性

在很多程序員看來(lái)，編程語(yǔ)言最值得關(guān)注，其實(shí)隨著時(shí)代的發(fā)展，算法會(huì)變得越來(lái)越有用，雖然編程語(yǔ)言的種類越來(lái)越多，有些編程語(yǔ)言由冷門(mén)到熱門(mén)，然而有些也會(huì)從熱門(mén)變?yōu)槔溟T(mén)，技術(shù)在不停地更新?lián)Q代，但是有些東西是不變的，例如算法，數(shù)據(jù)結(jié)構(gòu)，編程原理，關(guān)系型數(shù)據(jù)庫(kù)原理，計(jì)算機(jī)體系結(jié)構(gòu)等等。未來(lái)編程，算法將會(huì)是一種內(nèi)在的“修養(yǎng)”，沒(méi)有算法的思想和理論，就不可能成為真正的程序員。

2.2 算法在未來(lái)的應(yīng)用

如今計(jì)算機(jī)已經(jīng)全面普及，價(jià)格也很低廉。當(dāng)在激烈的競(jìng)爭(zhēng)中，用戶體驗(yàn)成為了關(guān)鍵，用算法去設(shè)計(jì)各種應(yīng)用，是一個(gè)必然的選擇。在存儲(chǔ)方面，大數(shù)據(jù)存儲(chǔ)是關(guān)鍵問(wèn)題，算法能有效的提高大數(shù)據(jù)存儲(chǔ)的效率。在科學(xué)研究方面，無(wú)論是三維模型還是數(shù)據(jù)處理，都會(huì)需要很大的計(jì)算量，都要靠算法來(lái)解決。例如Google每天都會(huì)處理數(shù)以億計(jì)的搜索，存儲(chǔ)幾千萬(wàn)用戶的數(shù)據(jù)，通過(guò)互聯(lián)網(wǎng)將巨量的信息提交給每個(gè)用戶，很顯然，如果沒(méi)有找到好的算法，這些是不可能完成的。所以Google數(shù)據(jù)中心使用的是超大型并行計(jì)算機(jī)，讓并行算法在并行計(jì)算的環(huán)境下執(zhí)行，使處理請(qǐng)求速度得到飛躍式的提升。

2.3 算法前景

算法的作用在未來(lái)計(jì)算機(jī)的發(fā)展中不可估量，不僅在大數(shù)據(jù)和云計(jì)算方面，也用于解決實(shí)驗(yàn)數(shù)據(jù)的處理和存儲(chǔ)，還用來(lái)研究人類基因，發(fā)明新的醫(yī)療方式，可以保障國(guó)家網(wǎng)絡(luò)安全，預(yù)測(cè)天災(zāi)的發(fā)生等。算法在未來(lái)的機(jī)遇和挑戰(zhàn)并存的環(huán)境中是不可或缺的，是不可以替代的。我們要用發(fā)展的眼光來(lái)看待算法，與時(shí)俱進(jìn)，不可輕視它，冷落它，須始終保持一顆對(duì)算法探索研究的心，爭(zhēng)取利用算法來(lái)造福美好的未來(lái)。

3 總結(jié)

本文對(duì)常用經(jīng)典算法進(jìn)行了概括與分析，探究了算法的設(shè)計(jì)思想與優(yōu)缺點(diǎn)，并根據(jù)算法的具體應(yīng)深入探討算法。從分析和研究我們可以看出，在不同的情況下，應(yīng)該選擇不同的算法。同時(shí)，我們也能發(fā)現(xiàn)在復(fù)雜的問(wèn)題面前，一個(gè)正確高效的算法是非常重要的，每一個(gè)算法都有自己的優(yōu)缺點(diǎn)，在算法選擇時(shí)，要考慮算法本身的特性。面對(duì)復(fù)雜的問(wèn)題，要具體問(wèn)題具體分析，將復(fù)雜的問(wèn)題簡(jiǎn)單化，將算法的思想與解題步驟巧妙地聯(lián)系在一起，用科學(xué)有效的方法來(lái)解決問(wèn)題，這是學(xué)習(xí)的意義所在。算法有著美好而又遠(yuǎn)大的前景，還需要我們獨(dú)具慧心，發(fā)掘算法的潛力，造福我們的生活。

參考文獻(xiàn)（References）：

[1] 陳德裕，杭月芹.數(shù)據(jù)結(jié)構(gòu)中經(jīng)典算法的教學(xué)研究[J].計(jì)算機(jī)

時(shí)代，2009.6：3-4

[2] 袁勁松，楊偉明.遞歸算法設(shè)計(jì)及效率分析[J].計(jì)算機(jī)與數(shù)字

工程，2007.2：12-13

[3] 李健勇，李曄，劉艷紅，張杰，李建春，黃道穎.任意數(shù)量選手的

循環(huán)賽賽程分治算法[J].鄭州輕工業(yè)學(xué)院學(xué)報(bào)（自然科學(xué)版），2007.4：26-27

[4] 宛楠，張義.動(dòng)態(tài)規(guī)劃算法分析[J].長(zhǎng)江大學(xué)學(xué)報(bào)（自然科學(xué)

版），2013.7：3-6

[5] 常友渠，肖貴元，曾敏.貪心算法的探討與研究[J].重慶電力高

等?？茖W(xué)校學(xué)報(bào)，2008.3：31-32

[6] 歐陽(yáng)圣，胡望宇.幾種經(jīng)典搜索算法研究與應(yīng)用[J]. 計(jì)算機(jī)系

統(tǒng)應(yīng)用，2011.5：16-17endprint