求組合問題的不同算法比較分析

1、求組合問題的不同算法比擬分析摘要:本文主要介紹的遞歸法與回溯法的一般思想，并通過比擬與分析用遞歸法與回溯法求解組合問題，以及比擬它們對求解問題的復雜度以及它們優(yōu)缺點。論文關(guān)鍵詞：遞歸法,回溯法,組合問題,算法比擬分析下面就以回溯法與遞歸法解決組合問題進行比擬分析：問題描述：找出從自然數(shù)1，2，m中任取k個數(shù)的所有組合。1、用純遞歸法求解能采用遞歸描述的算法通常有這樣的特征：為求解規(guī)模為N的問題，設(shè)法將它分解成規(guī)模較小的問題，然后從這些小問題的解方便地構(gòu)造出大問題的解，并且這些規(guī)模較小的問題也能采用同樣的分解和綜合方法，分解成規(guī)模更小的問題，并從這些更小問題的解構(gòu)造出規(guī)模較大問題的解。特別地，當

2、規(guī)模N=1時，能直接得解。我們可以采用這樣的遞歸思想來考慮求組合函數(shù)的算法。設(shè)函數(shù)為void comb(int m,int k)為找出從自然數(shù)1、2、m中任取k個數(shù)的所有組合。當組合的第一個數(shù)字選定時，其后的數(shù)字是從余下的m-1個數(shù)中取k-1數(shù)的組合。這就將求m個數(shù)中取k個數(shù)的組合問題轉(zhuǎn)化成求m-1個數(shù)中取k-1個數(shù)的組合問題。設(shè)函數(shù)引入工作數(shù)組a存放求出的組合的數(shù)字，約定函數(shù)將確定的k個數(shù)字組合的第一個數(shù)字放在a中，當一個組合求出后，才將a中的一個組合輸出。第一個數(shù)可以是m、m-1、k，函數(shù)將確定組合的第一個數(shù)字放入數(shù)組后，有兩種可能的選擇，因還未去掉組合的其余元素，繼續(xù)遞歸去確定；或因已確

3、定了組合的全部元素，輸出這個組合。細節(jié)見以下程序中的函數(shù)comb。public static void comb(int m, int k)int i = 0, j = 0;for (i = m; i = k; i-)a = i;if (k 1)comb(i - 1, k - 1);elsefor (j = a; j 0; j-)Console.Write(a.ToString() + );Console.WriteLine( );2、用回溯法求解：回溯法也稱為試探法，該方法首先暫時放棄關(guān)于問題規(guī)模大小的限制，并將問題的候選解按某種順序逐一枚舉和檢驗。當發(fā)現(xiàn)當前候選解不可能是解時，就選擇下一個

4、候選解；倘假設(shè)當前候選解除了還不滿足問題規(guī)模要求外，滿足所有其他要求時，繼續(xù)擴大當前候選解的規(guī)模，并繼續(xù)試探。如果當前候選解滿足包括問題規(guī)模在內(nèi)的所有要求時，該候選解就是問題的一個解。在回溯法中，放棄當前候選解，尋找下一個候選解的過程稱為回溯。擴大當前候選解的規(guī)模，以繼續(xù)試探的過程稱為向前試探。(1)回溯法的方法對于具有完備約束集D的一般問題P及其相應(yīng)的狀態(tài)空間樹T，利用T的層次結(jié)構(gòu)和D的完備性，在T中搜索問題P的所有解的回溯法可以形象地描述為：從T的根出發(fā)，按深度優(yōu)先的策略，系統(tǒng)地搜索以其為根的子樹中可能包含著答復結(jié)點的所有狀態(tài)結(jié)點，而跳過對肯定不含答復結(jié)點的所有子樹的搜索，以提高搜索效率。

5、具體地說，當搜索按深度優(yōu)先策略到達一個滿足D中所有有關(guān)約束的狀態(tài)結(jié)點時，即激活;該狀態(tài)結(jié)點，以便繼續(xù)往深層搜索；否那么跳過對以該狀態(tài)結(jié)點為根的子樹的搜索，而一邊逐層地向該狀態(tài)結(jié)點的祖先結(jié)點回溯，一邊殺死;其兒子結(jié)點已被搜索遍的祖先結(jié)點，直到遇到其兒子結(jié)點未被搜索遍的祖先結(jié)點，即轉(zhuǎn)向其未被搜索的一個兒子結(jié)點繼續(xù)搜索。在搜索過程中，只要所激活的狀態(tài)結(jié)點又滿足終結(jié)條件，那么它就是答復結(jié)點，應(yīng)該把它輸出或保存。由于在回溯法求解問題時，一般要求出問題的所有解，因此在得到答復結(jié)點后，同時也要進行回溯，以便得到問題的其他解，直至回溯到T的根且根的所有兒子結(jié)點均已被搜索過為止。(2)回溯法的一般流程和技術(shù)在用

6、回溯法求解有關(guān)問題的過程中，一般是一邊建樹，一邊遍歷該樹。在回溯法中我們一般采用非遞歸方法。下面，我們給出回溯法的非遞歸算法的一般流程：在用回溯法求解問題，也即在遍歷狀態(tài)空間樹的過程中，如果采用非遞歸方法，那么我們一般要用到棧的數(shù)據(jù)結(jié)構(gòu)。這時，不僅可以用棧來表示正在遍歷的樹的結(jié)點，而且可以很方便地表示建立孩子結(jié)點和回溯過程。假設(shè)采用回溯法找問題的解，將找到的組合以從小到大順序存于a，a【1】，a中，組合的元素滿足以下性質(zhì)：(1) aa，后一個數(shù)字比前一個大；(2) a-i按回溯法的思想，找解過程可以表達如下：首先放棄組合數(shù)個數(shù)為r的條件，候選組合從只有一個數(shù)字1開始。因該候選解滿足除問題規(guī)模之

7、外的全部條件，擴大其規(guī)模，并使其滿足上述條件1，候選組合改為1，2。繼續(xù)這一過程，得到候選組合1，2，3。該候選解滿足包括問題規(guī)模在內(nèi)的全部條件，因而是一個解。在該解的根底上，選下一個候選解，因a【2】上的3調(diào)整為4，以及以后調(diào)整為5都滿足問題的全部要求，得到解1，2，4和1，2，5。由于對5不能再作調(diào)整，就要從a【2】回溯到a【1】，這時，a【1】=2，可以調(diào)整為3，并向前試探，得到解1，3，4。重復上述向前試探和向后回溯，直至要從a再回溯時，說明已經(jīng)找完問題的全部解。按上述思想寫成程序如下：public static void comb(int n, int r)int i=0, j=0;

8、for (j = 0; j c = j+1;for (j = 0; j Console.Write(c.ToString() + );Console.WriteLine( );i = r - 1;doif (c-i c+;for (j = i + 1; j c = c + 1;for (j = 0; j Console.Write(c + );Console.WriteLine( );i = r - 1;else -i; while (i = 0);3、比擬小結(jié)：運行環(huán)境:本機Mcrosoft windwos XP版本2002 Service Pack 2 , CPU 2.13GHZ,760M

9、 RAM用時秒使用方法在10個數(shù)中取5個在20個數(shù)中取5個在30個數(shù)中取5個在40個數(shù)中取5個用遞歸算法4.32107.39960.613529.49用回溯算法4.37102.70955.473094.56用時秒使用方法在1000個數(shù)中取2個在100個數(shù)中取2個在20個數(shù)中取8個在30個數(shù)中取25個用遞歸算法1270.47190.731232.32912.41用回溯算法1856.73280.961157.57898.77從運行的情況來看,中選出數(shù)字個數(shù)較少時遞歸算法相對較快些,中選出數(shù)據(jù)量相對較大時用回溯法相對會快些。而使用遞歸法，代碼更加簡潔、明了。遞歸方法中遞歸調(diào)用的空間復雜度是Ok m

10、的線性階,因此其時間復雜度為O(log m),而回溯算法的空間復雜度為O( m2 )它的時間復雜度為Om x k遞歸方法適用于問題的規(guī)?？s小到一定的程度就可以容易地解決；該問題可以分解為假設(shè)干個規(guī)模較小的相同問題，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。 利用該問題分解出的子問題的解可以合并為該問題的解；該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子問題。遞歸法的關(guān)鍵是必須有一個遞歸終止條件，即要有遞歸出口。無條件的遞歸是毫無意義的。遞歸方法設(shè)計算法的策略不僅適用于計算數(shù)學問題，而且也適用于非數(shù)值運算領(lǐng)域。遞歸法的優(yōu)點是結(jié)構(gòu)清晰，可讀性強，而且容易用數(shù)學歸納法來證明算法的正確性，因此它

11、為設(shè)計算法、調(diào)試程序帶來很大方便。其缺點是遞歸算法的運行效率較低，無論是消耗的計算時間還是占用的存儲空間都比非遞歸算法要多。而回溯法的優(yōu)點適用于不可能使用實驗研究法的許多情形；可獲得關(guān)于某現(xiàn)象之性質(zhì)的有關(guān)資料；由于近年的技術(shù)與統(tǒng)計方法以及局部控制設(shè)計的改良，便得很多研究結(jié)果，具有可防衛(wèi)性等。其缺點是缺乏對自變項的控制；難確定有關(guān)的因素；事件的發(fā)生，原因可能不只一個；導致現(xiàn)象的原因是多元的；決定兩個變項何者為因，何者為果是很困難的；兩個以上有關(guān)的因素，未必具有因果關(guān)系；基于比擬的目標，把受試者硬分為兩組，常常導致發(fā)生問題；受試者不能隨機分派到處理組等。參考文獻:【1】朱戰(zhàn)立.數(shù)據(jù)結(jié)構(gòu)(C+語言描述) .北京:高等教育出版社,2004.【2】譚浩強.C 程序設(shè)計(第2 版