组合问题常用算法分析及应用

《组合问题常用算法分析及应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、计算机光盘软件与应用软件设计开发ComputerCDSoftwareandApplications2010年第8期组合问题常用算法分析及应用严煜华(东华大学计算机学院，上海201620)摘要：组合问题是算法分析与设计中一类重要的问题，本文首先对解组合问题常用的两种算法进行了分析和比较，然后给出了基于组合的应用即组合查询树。关键词：组合问题；递归法；回溯法；组合查询树中图分类号：TP311文献标识码：A文章鳊号：1007—9599(2010)08—0136—02Analysis&ApplicationofCo

2、mmonAlgorithmforCombinatorialProblemYanYuhua(DonghuaUniversity，CSTCollege，Shanghai201620，China)Abstract：Combinatorialproblemisoneofthemostimportantissueintheanalysisanddesignofalgorithm．Thistextfirstlypresentacomparisonbetweenthetwocommonalgorithms．Thengiv

3、eanapplicationbasedoncombination—combinationofthequerytree．Keywords：Combinatorialproblem；Recursviemethod；Backtrackingmethod；CombinationofQueryTree一、组合问题简介回溯法在包含问题的所有解的解空间树中，按照深度优先的策略，组合是一个古老的数学问题，中学数学中就有组合数的计算从根结点出发搜索解空间树。回溯算法搜索至解空间树的任一结公式Cnr=n!／r!(n-r)，然而

4、当组合数很大时，要求把每一个组点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不合都写出来就是一个困难的问题了。用人来实现这样的工作是不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先现实的，当组合数的大小达到一定规模时，甚至计算机也是实现结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。不了的。由此，许多学者对组合算法的研究产生了兴趣。Shimon回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有Even给出了纸上作业的方法来写出所有的组合。知识发现领域的子树都已被搜索遍才结束

5、。著名算法Apriorim，其基本数学思想也是组合。许多研究者对该简单地说就是确定解空间，建立解空间树，用深度优先搜索算法进行了改进，有效地降低了时间复杂度和空间复杂度，但其算法递归搜索解空间树，并同时注意剪枝。回溯法适用于求解组基本数学思想不变。算法领域内也已经存在很多比较好的组合算合数较大的问题。法，这些算法都可以从不同的角度给出令人满意的组合问题的解用回溯法求解组合问题的算法思路为首先明确定义好解空法，但是总体上说，现存组合问题的算法还是存在很多值得深究间，在组合问题中解空间是显而易见的，有多少需要处

6、理的集合的地方。因而对组合算法进行研究有重要的意义。本文从算法分解空间就有多少大小。接着应用解空间树，将需处理的集合抽象析实现的角度对组合问题进行研究，并探讨对解组合问题的算法为树上的结点。最后对解空间树进行求解得到问题的解。的优化以及组合问题的应用。三、算法应用二、求解组合问题的常用算法在算法应用方面我们的着眼点在于组合优化问题的应用，得查阅大量文献资料后我们发现，求解组合问题最常用最根本到一个具体的例子是组合查询树在查询以及计算方面的优势。首的只有两种算法，即递归法和回溯法，其他的算法只是对这两种先我们

7、提出组合查询树的定义，组合查询树是由n个以逻辑运算算法的变形或者改进，那么在常用算法举例这一部分我们只就这符和查询条件为结点构成的有限集。可将组合查询树表达为以下两个算法做出解释和比较。其他若干算法我们将在算法优化部分形式：Tree：(c，F)，其中：C是逻辑运算符AND或0R元素的集给出简单的介绍。合；F是查询条件的集合。将逻辑运算符AND或OR元素作为树的(一)递归法非叶结点，条件内容作为树的叶结点。例如有四重条件查询的组直接或间接地调用自身的算法称为递归算法。用函数自身给合表达式为(F1ANDF2)，

8、(F3ORF4)。其组合查询树如图3所出定义的函数称为递归函数。在计算机算法设计与分析中，递归不。技术是十分有用的。使用递归技术往往使函数的定义和算法的描述简洁且易于理解。有些数据结构如二叉树等，由于其本身固有的递归特性，特别适合用递归的形式来描述。另外，还有一些问题，虽然其本身并没有明显的递归结构，但是用递归技术来求解使设计出的算法简洁易懂且易于分析。组合问题本身没有固有的递归特性，其递归结构也不是很明显，但是