什么是组合算法和组合问题
什么是组合算法?
本书中我们的主兴趣是研究一些涉及组合结构的算法。这些算法可非形式地根据算法目的(desired purpose)进行分类:
生成(generation):构造某种类型的组合结构的全体
可构造的组合结构例子有集合(subsets)、排列、划分(partitions)、树和Catalan families。生成算法会根据指定的序关系列出所有的对象,这样的序如字典序(lexicographic order)。这种(在没有完全生成整个序列前就)预先对生成序列中某个对象定好位置是很有价值的(desirable)。这样就引出了一个论题——评级排列(ranking)和它的反向(unranking),这个论题在二、三章详述。
KEMIN: 所谓“结构”就是有“序”关系的存在,问题是这种“序”是平等的还是有偏向。还有其它的可能序关系吗?
另:《组合数学 (邵嘉裕)》:组合生成也叫组合设计,是研究满足某些特定要求的组态(子集系)的存在性和构造问题。
枚举(enumeration):计算某特定类型的组合结构的总数。
前面的生成算法本身也是一个枚举算法,因为每生成一个对象就是枚举一个组合结构。不过反过来则不然了,一个组合结构计数算法不是一个生成算法。计算一个特殊类型的不同组合结构的总数往往比生成它要来得容易。比如,计算组合数:
从n个元素取k个元素的组合有多少 比生成这些组合要难得多。
很多时候两个表现形式不同的对象却有“相同”的结构。这种现象叫同构(形式化formalized为“同构”这个概念)。例如,我们把同一个图的节点变换为另一种东西,那两个图是同构的,只是节点代表了不同问题的内容罢了。
搜索(search):查找某特定类型组合结构(至少)一个例子(如果存在的话)。
搜索问题的一个典型例子就是查找某图结构的大小的阀值(clique)。生成算法可用作搜索某特定类型组合结构,但这种方式对很多问题来讲是低效的(KEMIN:为什么低效?生成只管“有”不管“好”?)。通常搜索一个结构的例子比枚举组合结构总数和生成这些组合结构来得容易,换句话说,搜索算法比计数算法和生成算法都容易实现。
搜索问题的一个变种是最优化问题。最优化算法试图查找出某组合结构的最佳(optimal)例子。那么什么叫最佳呢?每种特定的组合结构或问题对最佳的标准的定义是不一样的,一般的尺度是利益(profit)或费用(cost)。例如,图的最大阀值问题就是查找出某图结构的最大规模,也就是图所包含的最大节点数。
另:因为人类所从事的一切生产或社会活动均是有目的的,其行为总是在特定的价值观念或审美取向的支配下进行的,经常面临求解一个可行的甚至是最优的方案的决策问题。可以说,最优化思想是数学建模的灵魂。而最优化方法作为一门特殊的数学学科分支有着广泛的实际应用背景。
什么是组合问题?
根据答案的不同性质我们可以把组合问题分为不种类:判定问题、搜索问题、最佳值问题和最优化问题。看以下四个背包问题的变种:
判定问题(decision)
实例:
值 p1,p2,…,pn-1;
重 w0,w2,…,wn-1;
容量 M;和目标值 P
求:
是否存n-元组[x0,x1,…,xn-1] ∈{0,1}^n满足
∑(i=0,n-1)pi•xi ≥ P
且
∑(i=0,n-1)wi•xi ≤ M?
判定问题的答案是“是”和“否”。解决判定问题的算法只需要为每个问题实例提供一个正确的“是”和“否”即可。
搜索问题(search)
实例:
值 p1,p2,…,pn-1;
重 w0,w2,…,wn-1;
容量 M;和目标值 P
找出:
n-元组[x0,x1,…,xn-1] ∈{0,1}^n 满足
∑(i=0,n-1)pi•xi ≥ P
且
∑(i=0,n-1)wi•xi ≤ M
如果这样的元组存在的话
搜索问题几乎与判定问题一模一样,只是搜索问题的答案是满足条件的一个n元组,不只是“是”和“否”。
最佳值问题(optimal value)
实例:
值 p1,p2,…,pn-1;
重 w0,w2,…,wn-1;
容量 M;
找出:P =∑(i=0,n-1)pi•xi 的最大值,满足
∑(i=0,n-1)wi•xi ≤ M
且
n-元组[x0,x1,…,xn-1] ∈{0,1}^n
最佳值问题的问题实例是没有特定目标值的,它要找是最大值。
最优化问题(optimization)
实例:
值 p1,p2,…,pn-1;
重 w0,w2,…,wn-1;
容量 M;
找出:n-元组[x0,x1,…,xn-1] ∈{0,1}^n 满足
P =∑(i=0,n-1)pi•xi 是最大值,
且
∑(i=0,n-1)wi•xi ≤ M
最优化问题与最佳值问题很相似,唯一不同的是最优化问题是查找产生最佳值的n-元组[x0,x1,…,xn-1] ∈{0,1}^n,而不是仅仅一个值。
最优化问题一般会有一些待满足的约束条件。满足约束的一个n元组称为可行方案(feasible solution)。比如上面的问题中,n元组[x0,x1,…,xn-1] ∈{0,1}^n能够满足条件∑(i=0,n-1)wi•xi ≤ M才叫可行的n元组。而每个可行方案(n元组)都有一个对应的目标函数,变量一般是整数或实数,用以算得最佳值。在上面的问题中,目标函数是P =∑(i=0,n-1)pi•xi最大。
本书编写的目的是作为有关组合算法的通用的导论性教材。有关组合算法的教材早70年代就有,不过已经过时了;而现在的教材不是太全面(只谈算法理论)就是太专(谈图算法)。我们感觉有必要编写一本不太泛不太专的组合算法教材,它集中关注组合算法设计基础技术——生成算法、计数算法和搜索算法。
本书中提供了适量的数学知识,这些数学知识是理解算法所必须的。
书中的代码可在以下网站下载:http://www.math.mtu.edu/~kreher/cages.html
The book is organized into eight chapters.
Chapter 1 provides some background and notation for fundamental concepts that are used throughout the book.
Chapters 2 and 3 are concerned with the generation of elementary combinatorial objects such as subsets and permutations, to name two examples.
Chapter 4 presents the important combinatorial search technique called backtracking. It includes a discussion of pruning methods, and the maximum clique problem is studied in detail.
Chapter 5 gives an overview of the relatively new area of heuristic search algorithms, including hill-climbing, simulated annealing, tabu search and genetic algorithms.
In Chapter 6, we study several basic algorithms for permutation groups, and how they are applied in solving certain combinatorial enumeration and search problems.
Chapter 7 uses techniques from the previous chapter to develop algorithms for testing isomorphism of combinatorial objects.
Finally, Chapter 8 discusses the technique of basis reduction, which is an important technique in solving certain combinatorial search problems.
分享到:
相关推荐
因为程序设计的核心是算法研究,而组合算法是算法的主要内容。没有组合数学的基础,就无法深入研究算法和分析算法。竞赛试题的形式和类型干变万化,但通常蕴涵某个组合数学方面的问题,这些问题很能推动人们去...
C++实现生成组合算法
该文档对排列组合问题的算法设计问题进行一系列讲述
主要介绍了基于Vue实现电商SKU组合算法问题 ,本文通过实例代码给大家介绍的非常详细,具有一定的参考借鉴价值,需要的朋友可以参考下
第一章 引论 1.1 组合数学研究的对象 1.2 组合问题典型实例 1.2.1 分派问题 1. 2.2 染色问题 ...11.12 好算法、坏算法和np类问题 11.13 npc类问题 11.14 货郎问题的近似解 习 题... 参考文献
排列组合是常见的数学问题,本文就以完整实例形式讲述了C#实现排列组合算法的方法。分享给大家供大家参考之用。具体方法如下: 首先,数学中排列组合,可表示为:排列P(N,R) 其实排列实现了,组合也就实现了,组合...
针对当前科技水平不足以有效存储电力的情况下产生的发电机机组组合的问题,考虑负荷平衡、输电线传输容量限制等实际情况产生的约束条件,建立机组组合优化模型,追求发电成本最小。同时采用矩阵实数编码遗传算法...
本资源附带文档解释了排列组合算法的实现和原理。其中排列算法是基于递归实现的,组合算法是基于高效的位移法实现的。代码是使用Java版实现的。
PHP实现多种类型的排列组合算法,PHP多种方式实现排列组合算法。非常有用,欢迎下载。
基于多目标粒子群算法的多约束组合优化问题研究.pdf基于多目标粒子群算法的多约束组合优化问题研究.pdf基于多目标粒子群算法的多约束组合优化问题研究.pdf基于多目标粒子群算法的多约束组合优化问题研究.pdf基于多...
组合数学之排列组合生成算法,很好的学习组合排列算法的资料
组合优化算法和复杂性组合优化算法和复杂性组合优化算法和复杂性组合优化算法和复杂性组合优化算法和复杂性
代码 离散型遗传算法求解组合优化代码代码 离散型遗传算法求解组合优化代码代码 离散型遗传算法求解组合优化代码代码 离散型遗传算法求解组合优化代码代码 离散型遗传算法求解组合优化代码代码 离散型遗传算法求解...
excel VBA - 排列组合生成算法 - ,可快速生成指定项目的所有排列组合
这些讲义涵盖了算法,尤其是组合算法,其主要目标是创建正确且始终有效的算法。
组合 算法 C# <br>递归实现M选N,可以用于线性规划,背包问题求解等.
组合算法,在VC中调试通过。改写了排列的一段代码, 可以完成组合功能。
研究生学习阶段,优化理论是不可缺少的。组合最优化算法和复杂性能帮你排忧解难 作者 刘振宏
动态规划,分治算法,概率算法,模拟退火算法,搜索算法,贪婪算法,网上matlab,遗传算法,组合算法.