组合算法概论

核心提示：组合算法概论(A Brief IntrodUCtion to Combinatorial Algorithm) 组合算法是算法分析学当中非常重要的一个分支，关于它在计算机科学的地位我就不敖述了，组合算法概论，下面为大家整理了整个材料，算法是我收集的，3，…, n, 实现整个序列的排序，只是分门别类简单介绍一下，然后把我

组合算法概论(A Brief IntrodUCtion to Combinatorial Algorithm)
　　组合算法是算法分析学当中非常重要的一个分支，关于它在计算机科学的地位我就不敖述了，下面为大家整理了整个材料，算法是我收集的，只是分门别类简单介绍一下，然后把我的材料做了个整理，大家收藏吧，感觉挺有用的，费了我好长时间和精力呀，我现在预备考研了，没有太多时间发很多经典文章了，这片算是大部头了。
　　关于组合学问题的算法，计算对象是离散的、有限的数学结构。从方法学的角度，组合算法包括算法设计和算法分析两个方面。关于算法设计，历史上已经总结出了若干带有普遍意义的方法和技术，包括动态规划、回溯法、分支限界法、分治法、贪心法等。下面我们着重谈谈几个有代表性的组合算法：
单纯形法：
　　这是一种线性规划算法，由G.B.Dantzig在1947年提出，后来由他和其他的学者又提出了单纯形法的变形和改进。这些被实践证实都是行之有效的，线性规划研究线性目标函数在一组线性等式与线性不等式约束下的极值问题。这本来是连续问题，Dantzig发现线性规划问题的可行解集（即满足约束条件的点的全体）是一个超多面体。假如它的最优解存在，那么这个最优解一定可以在超多面体的一个顶点取到。由于超多面体的顶点只有有限个，从而使线性规划成为一个组和优化问题。单纯形法是按照一定的规则，从可行解集的一个顶点转移到另一个顶点，使得目标函数的值不断地得到改进，最后达到最优。尽管单纯形法一直使用得很好，但是在最坏情况下它需要指数运行时间，从而使线性规划问题是否属于P类一度成为人们关心的问题。后来的椭球算法和投影算法都很好的解决了这个问题。
排序和检索：
　　这两部分应当是大家比较熟悉的，所谓排序，就是将给定的元素序列按照某种顺序关系重新排列成有序序列。例如将n个数组成的序列按照从小到大的顺序重新排列；将n个英语单词组成的的序列按照字典顺序重新排列。所谓检索，就是在给定的集合中查找某个特定的元素或是元素组。排序和检索已经成为计算机科学技术中最基本、使用最频繁的算法。下面我们专门谈谈排序算法（sorting algorithm）。
　　在讨论此种算法时，数据通常是指由若干记录组成的文件，每个记录包含一个或多个数据项，其中能够标志该记录的数据项称为键码。给定一文件的n个记录{R1,R2,…,Rn}及其相应的键码的集合{K1,K2,…,Kn}。所谓排序算法就是在数据处理中将文件中的记录按键码的一定次序要求排列起来的算法。若待排序的文件能够同时装入计算机的主存中，整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序；若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，有一部分必须放在外存上，则称此类排序问题为外部排序。当待排序的文件中包含有一些相同键码的记录时，假如经过排序后这些相同的键码的记录的相对次序仍然保持不变，则相应的排序算法是稳定的，否则为不稳定的。假如排序算法设计成单处理机完成的，则此排序算法称为串行（或顺序）排序算法；假如排序算法时设计成多处理机实现的，则称为并行排序算法。
　　首先谈谈内部排序：内部排序的过程是一个逐步扩大记录的有序序列长度的过程。在排序的过程中，参与排序的记录序列中存在两个区域：有序区和无序区。
使有序区中记录的数目增加一个或几个的操作称为一趟排序。
　　逐步扩大记录有序序列长度的方法大致有下列几类：
一．插入排序
　　假设在排序过程中，记录序列R[1..n]的状态为：
则一趟直接插入排序的基本思想为：将记录R
插入到有序子序列R[1..i-1]中，使记录的有序序列从R[1..i-1]变为R[1..i]。
　　显然，完成这个“插入”需分三步进行：
1．查找R的插入位置j+1；
2．将R[j+1..i-1]中的记录后移一个位置；
3．将R复制到R[j+1]的位置上。
[I]直接插入排序
　　利用顺序查找实现“在R[1..i-1]中查找R的插入位置”的插入排序。
　　注重直接插入排序算法的三个要点：
1．从R[i-1]起向前进行顺序查找，监视哨设置在R[0]；
　R[0] = R;　　// 设置“哨兵”
　for (j=i-1; R[0].key<R[j].key; --j); // 从后往前找
　return j+1;　　 // 返回R的插入位置为j+1
2．对于在查找过程中找到的那些要害字不小于R.key的记录，可以在查找的同时实现向后移动；
　for (j=i-1; R[0].key<R[j].key; --j);　
　R[j+1] = R[j]
3．i = 2，3，…, n, 实现整个序列的排序。
　template<class Elem>
　void InsertionSort ( Elem R[],　int n)
　{
　　　// 对记录序列R[1..n]作直接插入排序。
　　　for ( i=2; i<=n; ++i )
　　　{
　　　　　R[0] = R;　　　　　　// 复制为监视哨