計算機多種算法分析

嚴　凡

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

[關鍵詞]計算機 算法 分析

中圖分類號:TP3文獻標識碼:A文章編號:1671-7597(2009)0910049-02

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

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

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

一、迭代法

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

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

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

3.當x0與x1的差的絕對值還小于指定的精度要求時,重復步驟(2)的計算。

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

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

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

2.方程雖然有解,但迭代公式選擇不當,或迭代的初始近似根選擇不合理,也會導致迭代失敗。

二、窮舉搜索法

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

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

三、遞推法

遞推法是利用問題本身所具有的一種遞推關系求問題解的一種方法。設要求問題規(guī)模為N的解,當N=1時,解或為已知,或能非常方便地得到解。能采用遞推法構造算法的問題有重要的遞推性質,即當得到問題規(guī)模為i-1的解后,由問題的遞推性質,能從已求得的規(guī)模為1,2,…,i-1的一系列解,構造出問題規(guī)模為i的解。這樣,程序可從i=0或i=1出發(fā),重復地,由已知至i-1規(guī)模的解,通過遞推,獲得規(guī)模為i的解,直至得到規(guī)模為N的解。

四、遞歸法

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

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

五、回溯法

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

(一)回溯法的一般描述

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

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

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

(二)回溯法的方法

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

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

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

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

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

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

六、貪婪法

貪婪法是一種不追求最優(yōu)解,只希望得到較為滿意解的方法[3]。從問題的某一個初始解出發(fā),采用逐步構造最優(yōu)解的方法向給定的目標前進。在每個局部階段,都做出一個看上去最優(yōu)的決策,并期望通過每次所做的局部最優(yōu)選擇,能夠產生出一個全局最優(yōu)解來。做出貪心決策的依據稱為貪心準則。貪婪法一般可以快速得到滿意的解,因為它省去了為找最優(yōu)解要窮盡所有可能而必須耗費的大量時間。貪婪法常以當前情況為基礎作最優(yōu)選擇,而不考慮各種可能的整體情況,所以貪婪法不要回溯。

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

七、分治法

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

參考文獻:

[1]Sara Baase,計算機算法設計與分析導論[M].北京:高教出版社,2001.

[2]Anany Levitin著,潘彥譯,算法設計與分析基礎[M].北京:清華大學出版社,2004:79-154.

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

[4]寧正元,算法與數據結構。清華大學出版社,2006.

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

作者簡介:

嚴凡(1979-),男,漢族,江西南昌人,軟件工程碩士,工程師,研究方向:計算機軟件、計算機網絡通信、計算機網絡安全。