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

劉放美+蔡增玉+付長寬

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

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

中圖分類號：TP301 文獻(xiàn)標(biāo)志碼：A 文章編號：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 引言

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

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

1.1 遞歸算法

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

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

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

1.2 分治算法

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

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

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

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

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

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

1.4 貪心算法

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

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

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

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

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

2 未來展望

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

2.1 算法在未來的重要性

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

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

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

2.3 算法前景

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

3 總結(jié)

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

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

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

時代，2009.6：3-4

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

工程，2007.2：12-13

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

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

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

版），2013.7：3-6

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

等專科學(xué)校學(xué)報，2008.3：31-32

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

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