求组合问题的不同算法比较分析

摘要:本文主要介绍的递归法与回溯法的一般思想，并通过比较与分析用递归法与回溯法求解组合问题，以及比较它们对求解问题的复杂度以及它们优缺点。
论文关键词：递归法,回溯法,组合问题,算法比较分析

　　下面就以回溯法与递归法解决组合问题进行比较分析：

　　问题描述：找出从自然数1，2，…，m中任取k个数的所有组合。

　　1、用纯递归法求解

　　能采用递归描述的算法通常有这样的特征：为求解规模为N的问题，设法将它分解成规模较小的问题，然后从这些小问题的解方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法，分解成规模更小的问题，并从这些更小问题的解构造出规模较大问题的解。特别地，当规模N=1时，能直接得解。

　　我们可以采用这样的递归思想来考虑求组合函数的算法。

　　设函数为void comb(int m,int k)为找出从自然数1、2、……、m中任取k个数的所有组合。当组合的第一个数字选定时，其后的数字是从余下的m-1个数中取k-1数的组合。这就将求m个数中取k个数的组合问题转化成求m-1个数中取k-1个数的组合问题。设函数引入工作数组a[ ]存放求出的组合的数字，约定函数将确定的k个数字组合的第一个数字放在a[k]中，当一个组合求出后，才将a[ ]中的一个组合输出。第一个数可以是m、m-1、……、k，函数将确定组合的第一个数字放入数组后，有两种可能的选择，因还未去掉组合的其余元素，继续递归去确定；或因已确定了组合的全部元素，输出这个组合。细节见以下程序中的函数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、用回溯法求解：

　　回溯法也称为试探法，该方法首先暂时放弃关于问题规模大小的限制，并将问题的候选解按某种顺序逐一枚举和检验。当发现当前候选解不可能是解时，就选择下一个候选解；倘若当前候选解除了还不满足问题规模要求外，满足所有其他要求时，继续扩大当前候选解的规模，并继续试探。如果当前候选解满足包括问题规模在内的所有要求时，该候选解就是问题的一个解。在回溯法中，放弃当前候选解，寻找下一个候选解的过程称为回溯。扩大当前候选解的规模，以继续试探的过程称为向前试探。

　　(1)回溯法的方法

　　对于具有完备约束集D的一般问题P及其相应的状态空间树T，利用T的层次结构和D的完备性，在T中搜索问题P的所有解的回溯法可以形象地描述为：

　　从T的根出发，按深度优先的策略，系统地搜索以其为根的子树中可能包含着回答结点的所有状态结点，而跳过对肯定不含回答结点的所有子树的搜索，以提高搜索效率。具体地说，当搜索按深度优先策略到达一个满足D中所有有关约束的状态结点时，即“激活”该状态结点，以便继续往深层搜索；否则跳过对以该状态结点为根的子树的搜索，而一边逐层地向该状态结点的祖先结点回溯，一边“杀死”其儿子结点已被搜索遍的祖先结点，直到遇到其儿子结点未被搜索遍的祖先结点，即转向其未被搜索的一个儿子结点继续搜索。

　　在搜索过程中，只要所激活的状态结点又满足终结条件，那么它就是回答结点，应该把它输出或保存。由于在回溯法求解问题时，一般要求出问题的所有解，因此在得到回答结点后，同时也要进行回溯，以便得到问题的其他解，直至回溯到T的根且根的所有儿子结点均已被搜索过为止。

　　(2)回溯法的一般流程和技术

　　在用回溯法求解有关问题的过程中，一般是一边建树，一边遍历该树。在回溯法中我们一般采用非递归方法。下面，我们给出回溯法的非递归算法的一般流程：

　　在用回溯法求解问题，也即在遍历状态空间树的过程中，如果采用非递归方法，则我们一般要用到栈的数据结构。这时，不仅可以用栈来表示正在遍历的树的结点，而且可以很方便地表示建立孩子结点和回溯过程。

　　若采用回溯法找问题的解，将找到的组合以从小到大顺序存于a[0]，a[1]，…，a[r-1]中，组合的元素满足以下性质：

　　(1) a[i+1]>a[i]，后一个数字比前一个大；

　　(2) a[i]-i<=n-r+1。

　　按回溯法的思想，找解过程可以叙述如下：首先放弃组合数个数为r的条件，候选组合从只有一个数字1开始。因该候选解满足除问题规模之外的全部条件，扩大其规模，并使其满足上述条件（1），候选组合改为1，2。继续这一过程，得到候选组合1，2，3。该候选解满足包括问题规模在内的全部条件，因而是一个解。在该解的基础上，选下一个候选解，因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、比较小结：

　　运行环境:本机Mcrosoft windwos XP版本2002 Service Pack 2 , CPU 2.13GHZ,760M RAM

　　用时秒

　　使用方法

　　在10个数中

　　取5个

　　在20个数中取5个

　　在30个数中取5个

　　在40个数中取5个

　　用递归算法

　　4.32

　　107.39

　　960.61

　　3529.49

　　用回溯算法

　　4.37

　　102.70

　　955.47

　　3094.56

　　用时秒

　　使用方法

　　在1000个数中取2个

　　在100个数中取2个

　　在20个数中取8个

　　在30个数中取25个

　　用递归算法

　　1270.47

　　190.73

　　1232.32

　　912.41

　　用回溯算法

　　1856.73

　　280.96

　　1157.57

　　898.77

　　从运行的情况来看,当选出数字个数较少时递归算法相对较快些,当选出数据量相对较大时用回溯法相对会快些。而使用递归法，代码更加简洁、明了。

　　递归方法中递归调用的空间复杂度是O（k – m） 的线性阶,因此其时间复杂度为O(log m),而回溯算法的空间复杂度为O( m2 )它的时间复杂度为O（m x k）．

　　递归方法适用于问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。 利用该问题分解出的子问题的解可以合并为该问题的解；该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。递归法的关键是必须有一个递归终止条件，即要有递归出口。无条件的递归是毫无意义的。递归方法设计算法的策略不仅适用于计算数学问题，而且也适用于非数值运算领域。

　　递归法的优点是结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。其缺点是递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。而回溯法的优点适用于不可能使用实验研究法的许多情形；可获得关于某现象之性质的有关资料；由于近年的技术与统计方法以及部分控制设计的改进，便得很多研究结果，具有可防卫性等。其缺点是缺乏对自变项的控制；难确定有关的因素；事件的发生，原因可能不只一个；导致现象的原因是多元的；决定两个变项何者为因，何者为果是很困难的；两个以上有关的因素，未必具有因果关系；基于比较的目标，把受试者硬分为两组，常常导致发生问题；受试者不能随机分派到处理组等。

参考文献:
[1]朱战立.数据结构(C++语言描述) [M].北京:高等教育出版社,2004.
[2]谭浩强.C 程序设计(第2 版)[M].北京:清华大学出版社,2003.
[3] Anany Levitin. introduction to The Design and Analysis of Algorithms.USA [M] . 北京:清华大学出版社,2005
[4] 朱玉龙,任文岚. 递归程序设计的公式化方法[J ] .小型微型计算机系统,2001 ,22 (11) :1 389～1 390.
[5]M.H.Alsuwaiyel. Algorithms design Techniques and Analysis 沙特吴伟旭.方世昌等译 电子工业出版社,2004.