欢迎来到论文网! 加入收藏 | 设为论文网 | 网站地图 | Tags标签 | RSS
论文网 论文网8200余万篇毕业论文、各种论文格式和论文范文以及9千多种期刊杂志的论文征稿及论文投稿信息,是论文写作、论文投稿和论文发表的论文参考网站,也是科研人员论文检测和发表论文的理想平台,lunwenf@yeah.net。
您当前的位置:论文网 > 科技论文 > 数学建模论文

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

时间:2016-04-13  作者:张世良

摘要:本文主要介绍的递归法与回溯法的一般思想,并通过比较与分析用递归法与回溯法求解组合问题,以及比较它们对求解问题的复杂度以及它们优缺点。
论文关键词:递归法,回溯法,组合问题,算法比较分析
  下面就以回溯法与递归法解决组合问题进行比较分析:
  问题描述:找出从自然数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]再回溯时,说明已经找完问题的全部解。

查看相关论文专题
-------------------------------------------------------------------------
加入收藏  打印本文
上一篇论文:一种基于向量空间模型的构件库设计
下一篇论文:谈谈数学建模对社会的推动作用
科技论文分类
科技小论文 数学建模论文
数学论文 节能减排论文
数学小论文 低碳生活论文
物理论文 建筑工程论文
网站设计论文 农业论文
图书情报 环境保护论文
计算机论文 化学论文
机电一体化论文 生物论文
网络安全论文 机械论文
水利论文 地质论文
交通论文
相关数学建模论文
最新数学建模论文
读者推荐的数学建模论文