計(jì)算機(jī)多種算法分析

嚴(yán)　凡

[摘要]通常求解一個(gè)問題可能會(huì)有多種算法可供選擇,選擇的主要標(biāo)準(zhǔn)是算法的正確性可靠性、簡(jiǎn)單性和易理解性,其次是算法所需要的存儲(chǔ)空間少和執(zhí)行更快等。算法設(shè)計(jì)是一件非常困難的工作,經(jīng)常采用的算法設(shè)計(jì)技術(shù)主要有迭代法、窮舉搜索法、遞推法、回溯法、貪婪法、分治法等等。另外,為更簡(jiǎn)潔的形式設(shè)計(jì)和算法描述,在算法設(shè)計(jì)時(shí)又常常采用遞歸技術(shù),用遞歸描述算法。

[關(guān)鍵詞]計(jì)算機(jī) 算法 分析

中圖分類號(hào):TP3文獻(xiàn)標(biāo)識(shí)碼:A文章編號(hào):1671-7597(2009)0910049-02

要使計(jì)算機(jī)能完成人們預(yù)定的工作,首先必須為如何完成預(yù)定的工作設(shè)計(jì)一個(gè)算法,然后再根據(jù)算法編寫程序。計(jì)算機(jī)程序要對(duì)問題的每個(gè)對(duì)象和處理規(guī)則給出正確詳盡的描述,其中程序的數(shù)據(jù)結(jié)構(gòu)和變量用來描述問題的對(duì)象,程序結(jié)構(gòu)、函數(shù)和語句用來描述問題的算法。算法數(shù)據(jù)結(jié)構(gòu)是程序的兩個(gè)重要方面。

算法是問題求解過程的精確描述,一個(gè)算法由有限條可完全機(jī)械地執(zhí)行的、有確定結(jié)果的指令組成。指令正確地描述了要完成的任務(wù)和它們被執(zhí)行的順序。計(jì)算機(jī)按算法指令所描述的順序執(zhí)行算法的指令能在有限的步驟內(nèi)終止,或終止于給出問題的解,或終止于指出問題對(duì)此輸入數(shù)據(jù)無解[1]。

為了獲得有效的算法,必須了解一些解題的基本思想和方法,對(duì)于許多問題,只要仔細(xì)分析了數(shù)據(jù)對(duì)象后,相應(yīng)的處理方法就有了,然后對(duì)于有些問題則不然。作為探尋問題求解思路的基本思想和方法,對(duì)于任何算法設(shè)計(jì)都是有用的。下面簡(jiǎn)要介紹一些常用的算法設(shè)計(jì)方法和技術(shù)。

一、迭代法

迭代法是用于求方程或方程組近似根的一種常用的算法設(shè)計(jì)方法。設(shè)方程為f(x)=0,用某種數(shù)學(xué)方法導(dǎo)出等價(jià)的形式x=g(x),然后按以下步驟執(zhí)行:

1.選一個(gè)方程的近似根,賦給變量x0;

2.將x0的值保存于變量x1,然后計(jì)算g(x1),并將結(jié)果存于變量x0;

3.當(dāng)x0與x1的差的絕對(duì)值還小于指定的精度要求時(shí),重復(fù)步驟(2)的計(jì)算。

若方程有根,并且用上述方法計(jì)算出來的近似根序列收斂,則按上述方法求得的x0就認(rèn)為是方程的根。

具體使用迭代法求根時(shí)應(yīng)注意以下兩種可能發(fā)生的情況:

1.如果方程無解,算法求出的近似根序列就不會(huì)收斂,迭代過程會(huì)變成死循環(huán),因此在使用迭代算法前應(yīng)先考察方程是否有解,并在程序中對(duì)迭代的次數(shù)給予限制;

2.方程雖然有解,但迭代公式選擇不當(dāng),或迭代的初始近似根選擇不合理,也會(huì)導(dǎo)致迭代失敗。

二、窮舉搜索法

窮舉搜索法是對(duì)可能是解的眾多候選解按某種順序進(jìn)行逐一枚舉和檢驗(yàn),并從眾找出那些符合要求的候選解作為問題的解。

例如,將A、B、C、D、E、F這六個(gè)變量排成如圖1所示的三角形,這六個(gè)變量分別取[1,6]上的整數(shù),且均不相同。求使三角形三條邊上的變量之和相等的全部解。如圖就是一個(gè)解。程序引入變量a、b、c、d、e、f,并讓它們分別順序取1至6的整數(shù),在它們互不相同的條件下,測(cè)試由它們排成的如圖所示的三角形三條邊上的變量之和是否相等,如相等即為一種滿足要求的排列,把它們輸出。當(dāng)這些變量取盡所有的組合后,程序就可得到全部可能的解。

三、遞推法

遞推法是利用問題本身所具有的一種遞推關(guān)系求問題解的一種方法。設(shè)要求問題規(guī)模為N的解,當(dāng)N=1時(shí),解或?yàn)橐阎?或能非常方便地得到解。能采用遞推法構(gòu)造算法的問題有重要的遞推性質(zhì),即當(dāng)?shù)玫絾栴}規(guī)模為i-1的解后,由問題的遞推性質(zhì),能從已求得的規(guī)模為1,2,…,i-1的一系列解,構(gòu)造出問題規(guī)模為i的解。這樣,程序可從i=0或i=1出發(fā),重復(fù)地,由已知至i-1規(guī)模的解,通過遞推,獲得規(guī)模為i的解,直至得到規(guī)模為N的解。

四、遞歸法

遞歸是設(shè)計(jì)和描述算法的一種有力的工具,由于它在復(fù)雜算法的描述中被經(jīng)常采用,為此在進(jìn)一步介紹其他算法設(shè)計(jì)方法之前先討論它。

能采用遞歸描述的算法通常有這樣的特征:為求解規(guī)模為N的問題,設(shè)法將它分解成規(guī)模較小的問題,然后從這些小問題的解方便地構(gòu)造出大問題的解,并且這些規(guī)模較小的問題也能采用同樣的分解和綜合方法,分解成規(guī)模更小的問題,并從這些更小問題的解構(gòu)造出規(guī)模較大問題的解。特別地,當(dāng)規(guī)模N=1時(shí),能直接得解。

五、回溯法

回溯法也稱為試探法,該方法首先暫時(shí)放棄關(guān)于問題規(guī)模大小的限制,并將問題的候選解按某種順序逐一枚舉和檢驗(yàn)。當(dāng)發(fā)現(xiàn)當(dāng)前候選解不可能是解時(shí),就選擇下一個(gè)候選解;倘若當(dāng)前候選解除了還不滿足問題規(guī)模要求外,滿足所有其他要求時(shí),繼續(xù)擴(kuò)大當(dāng)前候選解的規(guī)模,并繼續(xù)試探。如果當(dāng)前候選解滿足包括問題規(guī)模在內(nèi)的所有要求時(shí),該候選解就是問題的一個(gè)解。在回溯法中,放棄當(dāng)前候選解,尋找下一個(gè)候選解的過程稱為回溯。擴(kuò)大當(dāng)前候選解的規(guī)模,以繼續(xù)試探的過程稱為向前試探。[2]

(一)回溯法的一般描述

可用回溯法求解的問題P,通常要能表達(dá)為:對(duì)于已知的由n元組(x1,

x2,…,xn)組成的一個(gè)狀態(tài)空間E={(x1,x2,…,xn)∣xi∈Si,i=1,2,…,n},給定關(guān)于n元組中的一個(gè)分量的一個(gè)約束集D,要求E中滿足D的全部約束條件的所有n元組。其中Si是分量xi的定義域,且|Si|有限,i=1,2,…,n。我們稱E中滿足D的全部約束條件的任一n元組為問題P的一個(gè)解。

在回溯法中,上述引入的樹被稱為問題P的狀態(tài)空間樹;樹T上任意一個(gè)結(jié)點(diǎn)被稱為問題P的狀態(tài)結(jié)點(diǎn);樹T上的任意一個(gè)葉子結(jié)點(diǎn)被稱為問題P的一個(gè)解狀態(tài)結(jié)點(diǎn);樹T上滿足約束集D的全部約束的任意一個(gè)葉子結(jié)點(diǎn)被稱為問題P的一個(gè)回答狀態(tài)結(jié)點(diǎn),它對(duì)應(yīng)于問題P的一個(gè)解。

(二)回溯法的方法

對(duì)于具有完備約束集D的一般問題P及其相應(yīng)的狀態(tài)空間樹T,利用T的層次結(jié)構(gòu)和D的完備性,在T中搜索問題P的所有解的回溯法可以形象地描述為:

從T的根出發(fā),按深度優(yōu)先的策略,系統(tǒng)地搜索以其為根的子樹中可能包含著回答結(jié)點(diǎn)的所有狀態(tài)結(jié)點(diǎn),而跳過對(duì)肯定不含回答結(jié)點(diǎn)的所有子樹的搜索,以提高搜索效率。具體地說,當(dāng)搜索按深度優(yōu)先策略到達(dá)一個(gè)滿足D中所有有關(guān)約束的狀態(tài)結(jié)點(diǎn)時(shí),即“激活”該狀態(tài)結(jié)點(diǎn),以便繼續(xù)往深層搜索;否則跳過對(duì)以該狀態(tài)結(jié)點(diǎn)為根的子樹的搜索,而一邊逐層地向該狀態(tài)結(jié)點(diǎn)的祖先結(jié)點(diǎn)回溯,一邊“殺死”其兒子結(jié)點(diǎn)已被搜索遍的祖先結(jié)點(diǎn),直到遇到其兒子結(jié)點(diǎn)未被搜索遍的祖先結(jié)點(diǎn),即轉(zhuǎn)向其未被搜索的一個(gè)兒子結(jié)點(diǎn)繼續(xù)搜索。

在搜索過程中,只要所激活的狀態(tài)結(jié)點(diǎn)滿足終結(jié)條件,那么它就是回答結(jié)點(diǎn),應(yīng)該把它輸出或保存。由于在回溯法求解問題時(shí),一般要求出問題的所有解,因此在得到回答結(jié)點(diǎn)后,同時(shí)也要進(jìn)行回溯,以便得到問題的其他解,直至回溯到T的根且根的所有兒子結(jié)點(diǎn)均已被搜索過為止。

例如在組合問題中,從T的根出發(fā)深度優(yōu)先遍歷該樹。當(dāng)遍歷到結(jié)點(diǎn)(1,2)時(shí),雖然它滿足約束條件,但還不是回答結(jié)點(diǎn),則應(yīng)繼續(xù)深度遍歷;當(dāng)遍歷到葉子結(jié)點(diǎn)(1,2,5)時(shí),由于它已是一個(gè)回答結(jié)點(diǎn),則保存(或輸出)該結(jié)點(diǎn),并回溯到其雙親結(jié)點(diǎn),繼續(xù)深度遍歷;當(dāng)遍歷到結(jié)點(diǎn)(1,5)時(shí),由于它已是葉子結(jié)點(diǎn),但不滿足約束條件,故也需回溯。

(三)回溯法的一般流程和技術(shù)

在用回溯法求解有關(guān)問題的過程中,一般是一邊建樹,一邊遍歷該樹。在回溯法中我們一般采用非遞歸方法。下面,我們給出回溯法的非遞歸算法的一般流程:在用回溯法求解問題,也即在遍歷狀態(tài)空間樹的過程中,如果采用非遞歸方法,則我們一般要用到棧的數(shù)據(jù)結(jié)構(gòu)。這時(shí),不僅可以用棧來表示正在遍歷的樹的結(jié)點(diǎn),而且可以很方便地表示建立孩子結(jié)點(diǎn)和回溯過程。例如在組合問題中,我們用一個(gè)一維數(shù)組Stack表示棧。開始?？?則表示了樹的根結(jié)點(diǎn)。如果元素1進(jìn)棧,則表示建立并遍歷(1)結(jié)點(diǎn);這時(shí)如果元素2進(jìn)棧,則表示建立并遍歷(1,2)結(jié)點(diǎn);元素3再進(jìn)棧,則表示建立并遍歷(1,2,3)結(jié)點(diǎn)。這時(shí)可以判斷它滿足所有約束條件,是問題的一個(gè)解,輸出(或保存)。這時(shí)只要棧頂元素(3)出棧,即表示從結(jié)點(diǎn)(1,2,3)回溯到結(jié)點(diǎn)(1,2)。

六、貪婪法

貪婪法是一種不追求最優(yōu)解,只希望得到較為滿意解的方法[3]。從問題的某一個(gè)初始解出發(fā),采用逐步構(gòu)造最優(yōu)解的方法向給定的目標(biāo)前進(jìn)。在每個(gè)局部階段,都做出一個(gè)看上去最優(yōu)的決策,并期望通過每次所做的局部最優(yōu)選擇,能夠產(chǎn)生出一個(gè)全局最優(yōu)解來。做出貪心決策的依據(jù)稱為貪心準(zhǔn)則。貪婪法一般可以快速得到滿意的解,因?yàn)樗∪チ藶檎易顑?yōu)解要窮盡所有可能而必須耗費(fèi)的大量時(shí)間。貪婪法常以當(dāng)前情況為基礎(chǔ)作最優(yōu)選擇,而不考慮各種可能的整體情況,所以貪婪法不要回溯。

例如平時(shí)購物找錢時(shí),為使找回的零錢的硬幣數(shù)最少,不考慮找零錢的所有各種發(fā)表方案,而是從最大面值的幣種開始,按遞減的順序考慮各幣種,先盡量用大面值的幣種,當(dāng)不足大面值幣種的金額時(shí)才去考慮下一種較小面值的幣種。這就是在使用貪婪法。這種方法在這里總是最優(yōu),是因?yàn)殂y行對(duì)其發(fā)行的硬幣種類和硬幣面值的巧妙安排。如只有面值分別為1、5和11單位的硬幣,而希望找回總額為15單位的硬幣。按貪婪算法,應(yīng)找1個(gè)11單位面值的硬幣和4個(gè)1單位面值的硬幣,共找回5個(gè)硬幣。但最優(yōu)的解應(yīng)是3個(gè)5單位面值的硬幣。

七、分治法

求解一個(gè)復(fù)雜問題時(shí),盡可能地把這個(gè)問題分解為若干較小的子問題,在找出各個(gè)較小問題的解之后再組合成為整個(gè)問題的解,這就是分治法。[4]但是,根據(jù)分治法的分割原則,原問題應(yīng)該分為多少個(gè)子問題才較適宜?各個(gè)子問題的規(guī)模應(yīng)該怎樣才適當(dāng)?這些問題很難予以肯定的回答。但人們從大量實(shí)踐中發(fā)現(xiàn),在用分治法設(shè)計(jì)算法時(shí),最好使子問題的規(guī)模大致相同。換句話說,將一個(gè)問題分成若干個(gè)大小相等的子問題的處理方法是行之有效的。這種使子問題規(guī)模大致相等的做法是出自一種平衡(balancing)子問題的思想,它幾乎總是比子問題規(guī)模不等的做法要好[5]。

參考文獻(xiàn):

[1]Sara Baase,計(jì)算機(jī)算法設(shè)計(jì)與分析導(dǎo)論[M].北京:高教出版社,2001.

[2]Anany Levitin著,潘彥譯,算法設(shè)計(jì)與分析基礎(chǔ)[M].北京:清華大學(xué)出版社,2004:79-154.

[3]王曉東,計(jì)算機(jī)算法設(shè)計(jì)與分析(第2版)[M].北京:電子工業(yè)出版社,2005:86-113.

[4]寧正元,算法與數(shù)據(jù)結(jié)構(gòu)。清華大學(xué)出版社,2006.

[5]傅清祥、王曉東,算法與數(shù)據(jù)結(jié)構(gòu),北京:電子工業(yè)出版社,1998.

作者簡(jiǎn)介:

嚴(yán)凡(1979-),男,漢族,江西南昌人,軟件工程碩士,工程師,研究方向:計(jì)算機(jī)軟件、計(jì)算機(jī)網(wǎng)絡(luò)通信、計(jì)算機(jī)網(wǎng)絡(luò)安全。