求組合問題的不同算法比較分析
摘要:本文主要介紹的遞歸法與回溯法的一般思想，并通過比較與分析用遞歸法與回溯法求解組合問題，以及比較它們對求解問題的復雜度以及它們優(yōu)缺點。
論文關鍵詞：遞歸法,回溯法,組合問題,算法比較分析
下面就以回溯法與遞歸法解決組合問題進行比較分析：
問題描述：找出從自然數(shù)1，2，…，m中任取k個數(shù)的所有組合。
1、用純遞歸法求解
能采用遞歸描述的算法通常有這樣的特征：為求解規(guī)模為N的問題，設法將它分解成規(guī)模較小的問題，然后從這些小問題的解方便地構造出大問題的解，并且這些規(guī)模較小的問題也能采用同樣的分解和綜合方法，分解成規(guī)模更小的問題，并從這些更小問題的解構造出規(guī)模較大問題的解。特別地，當規(guī)模N=1時，能直接得解。
我們可以采用這樣的遞歸思想來考慮求組合函數(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ù)的組合問題轉化成求m-1個數(shù)中取k-1個數(shù)的組合問題。設函數(shù)引入工作數(shù)組a[ ]存放求出的組合的數(shù)字，約定函數(shù)將確定的k個數(shù)字組合的第一個數(shù)字放在a[k]中，當一個組合求出后，才將a[ ]中的一個組合輸出。第一個數(shù)可以是m、m-1、……、k，函數(shù)將確定組合的第一個數(shù)字放入數(shù)組后，有兩種可能的選擇，因還未去掉組合的其余元素，繼續(xù)遞歸去確定；或因已確定了組合的全部元素，輸出這個組合。細節(jié)見以下程序中的函數(shù)comb。
public static void comb(int m, int k)
{
int i = 0, j = 0;
for (i = m; i >= k; i--)
{
a[k] = i;
if (k > 1)
{
comb(i - 1, k - 1);
}
else
{
for (j = a[0]; j > 0; j--)
{
Console.Write(a[j].ToString() + ' ');
}
Console.WriteLine(' ');
}
}
2、用回溯法求解：
回溯法也稱為試探法，該方法首先暫時放棄關于問題規(guī)模大小的限制，并將問題的候選解按某種順序逐一枚舉和檢驗。當發(fā)現(xiàn)當前候選解不可能是解時，就選擇下一個候選解；倘若當前候選解除了還不滿足問題規(guī)模要求外，滿足所有其他要求時，繼續(xù)擴大當前候選解的規(guī)模，并繼續(xù)試探。如果當前候選解滿足包括問題規(guī)模在內的所有要求時，該候選解就是問題的一個解。在回溯法中，放棄當前候選解，尋找下一個候選解的過程稱為回溯。擴大當前候選解的規(guī)模，以繼續(xù)試探的過程稱為向前試探。
(1)回溯法的方法
對于具有完備約束集D的一般問題P及其相應的狀態(tài)空間樹T，利用T的層次結構和D的完備性，在T中搜索問題P的所有解的回溯法可以形象地描述為：
從T的根出發(fā)，按深度優(yōu)先的策略，系統(tǒng)地搜索以其為根的子樹中可能包含著回答結點的所有狀態(tài)結點，而跳過對肯定不含回答結點的所有子樹的搜索，以提高搜索效率。具體地說，當搜索按深度優(yōu)先策略到達一個滿足D中所有有關約束的狀態(tài)結點時，即“激活”該狀態(tài)結點，以便繼續(xù)往深層搜索；否則跳過對以該狀態(tài)結點為根的子樹的搜索，而一邊逐層地向該狀態(tài)結點的祖先結點回溯，一邊“殺死”其兒子結點已被搜索遍的祖先結點，直到遇到其兒子結點未被搜索遍的祖先結點，即轉向其未被搜索的一個兒子結點繼續(xù)搜索。
在搜索過程中，只要所激活的狀態(tài)結點又滿足終結條件，那么它就是回答結點，應該把它輸出或保存。由于在回溯法求解問題時，一般要求出問題的所有解，因此在得到回答結點后，同時也要進行回溯，以便得到問題的其他解，直至回溯到T的根且根的所有兒子結點均已被搜索過為止。
(2)回溯法的一般流程和技術
在用回溯法求解有關問題的過程中，一般是一邊建樹，一邊遍歷該樹。在回溯法中我們一般采用非遞歸方法。下面，我們給出回溯法的非遞歸算法的一般流程：
在用回溯法求解問題，也即在遍歷狀態(tài)空間樹的過程中，如果采用非遞歸方法，則我們一般要用到棧的數(shù)據(jù)結構。這時，不僅可以用棧來表示正在遍歷的樹的結點，而且可以很方便地表示建立孩子結點和回溯過程。
若采用回溯法找問題的解，將找到的組合以從小到大順序存于a[0]，a[1]，…，a[r-1]中，組合的元素滿足以下性質：
(1) a[i+1]>a[i]，后一個數(shù)字比前一個大；
(2) a[i]-i<=n-r+1。
按回溯法的思想，找解過程可以敘述如下：首先放棄組合數(shù)個數(shù)為r的條件，候選組合從只有一個數(shù)字1開始。因該候選解滿足除問題規(guī)模之外的全部條件，擴大其規(guī)模，并使其滿足上述條件（1），候選組合改為1，2。繼續(xù)這一過程，得到候選組合1，2，3。該候選解滿足包括問題規(guī)模在內的全部條件，因而是一個解。在該解的基礎上，選下一個候選解，因a[2]上的3調整為4，以及以后調整為5都滿足問題的全部要求，得到解1，2，4和1，2，5。由于對5不能再作調整，就要從a[2]回溯到a[1]，這時，a[1]=2，可以調整為3，并向前試探，得到解1，3，4。重復上述向前試探和向后回溯，直至要從a[0]再回溯時，說明已經找完問題的全部解。
按上述思想寫成程序如下：
public static void comb(int n, int r)
{
int i=0, j=0;
for (j = 0; j < r; j++)
c[j] = j+1;
for (j = 0; j < r; j++)
{
Console.Write(c[j].ToString() + ' ');
}
Console.WriteLine(' ');
i = r - 1;
do
{
if (c[i]-i < n - r+1)
{
c[i]++;
for (j = i + 1; j < r; j++)
c[j] = c[j - 1] + 1;
for (j = 0; j < r; j++)
{
Console.Write(c[j] + ' ');
}
Console.WriteLine(' ');
i = r - 1;
}
else --i;
} while (i >= 0);
}
3、比較小結：
運行環(huán)境:本機Mcrosoft windwos XP版本2002 Service Pack 2 , CPU 2.13GHZ,760M RAM
用時秒
使用方法
在10個數(shù)中
取5個
在20個數(shù)中取5個
在30個數(shù)中取5個
在40個數(shù)中取5個
用遞歸算法
4.32
107.39
960.61
3529.49
用回溯算法
4.37
102.70
955.47
3094.56
用時秒
使用方法
在1000個數(shù)中取2個
在100個數(shù)中取2個
在20個數(shù)中取8個
在30個數(shù)中取25個
用遞歸算法
1270.47
190.73
1232.32
912.41
用回溯算法
1856.73
280.96
1157.57
898.77
從運行的情況來看,當選出數(shù)字個數(shù)較少時遞歸算法相對較快些,當選出數(shù)據(jù)量相對較大時用回溯法相對會快些。而使用遞歸法，代碼更加簡潔、明了。
遞歸方法中遞歸調用的空間復雜度是O（k – m） 的線性階,因此其時間復雜度為O(log m),而回溯算法的空間復雜度為O( m2 )它的時間復雜度為O（m x k）．
遞歸方法適用于問題的規(guī)模縮小到一定的程度就可以容易地解決；該問題可以分解為若干個規(guī)模較小的相同問題，即該問題具有最優(yōu)子結構性質。 利用該問題分解出的子問題的解可以合并為該問題的解；該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子問題。遞歸法的關鍵是必須有一個遞歸終止條件，即要有遞歸出口。無條件的遞歸是毫無意義的。遞歸方法設計算法的策略不僅適用于計算數(shù)學問題，而且也適用于非數(shù)值運算領域。
遞歸法的優(yōu)點是結構清晰，可讀性強，而且容易用數(shù)學歸納法來證明算法的正確性，因此它為設計算法、調試程序帶來很大方便。其缺點是遞歸算法的運行效率較低，無論是耗費的計算時間還是占用的存儲空間都比非遞歸算法要多。而回溯法的優(yōu)點適用于不可能使用實驗研究法的許多情形；可獲得關于某現(xiàn)象之性質的有關資料；由于近年的技術與統(tǒng)計方法以及部分控制設計的改進，便得很多研究結果，具有可防衛(wèi)性等。其缺點是缺乏對自變項的控制；難確定有關的因素；事件的發(fā)生，原因可能不只一個；導致現(xiàn)象的原因是多元的；決定兩個變項何者為因，何者為果是很困難的；兩個以上有關的因素，未必具有因果關系；基于比較的目標，把受試者硬分為兩組，常常導致發(fā)生問題；受試者不能隨機分派到處理組等。
參考文獻:
[1]朱戰(zhàn)立.數(shù)據(jù)結構(C++語言描述) [M].北京:高等教育出版社,2004.
[2]譚浩強.C 程序設計(第2 版)[M].北京:清華大學出版社,2003.
[3] Anany Levitin. introduction to The Design and Analysis of Algorithms.USA [M] . 北京:清華大學出版社,2005
[4] 朱玉龍,任文嵐. 遞歸程序設計的公式化方法[J ] .小型微型計算機系統(tǒng),2001 ,22 (11) :1 389～1 390.
[5]M.H.Alsuwaiyel. Algorithms design Techniques and Analysis 沙特吳偉旭.方世昌等譯 電子工業(yè)出版社,2004.
下一篇:體能訓練身體練習組合的理論方法
