什么是组合算法和组合问题

什么是组合算法？

本书中我们的主兴趣是研究一些涉及组合结构的算法。这些算法可非形式地根据算法目的（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.