组合算法_matlab源码.rar

中国数学建模-编程交流-组合算法概论 ├数学思想 ├编程交流 ├学术杂谈 ├English Fans wh-ee 重登录 隐身 用户控制面板 搜索 风格 论坛状态 论坛展区 社区服务 社区休闲 网站首页 退出 >> VC++,C,Perl,Asp...编程学习,算法介绍. 我的收件箱 (0) 中国数学建模 → 学术区 → 编程交流 → 组合算法概论 您是本帖的第 623 个阅读者 * 贴子主题：组合算法概论 b 等级：职业侠客 文章：470 积分：956 门派：黑客帝国 注册：2003-8-28 鲜花(1) 鸡蛋(0) 楼主 组合算法概论 组合算法概论(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; // 复制为监视哨 for ( j=i-1; R[0].key < R[j].key; --j ) R[j+1] = R[j]; // 记录后移 R[j+1] = R[0]; // 插入到正确位置 } } // InsertSort 时间分析： 实现排序的基本操作有两个： （1）“比较”序列中两个关键字的大小； （2）“移动”记录。 对于直接插入排序： [II]折半插入排序 因为R[1..i-1]是一个按关键字有序的有序序列，则可以利用折半查找实现“在R[1..i-1]中查找R的插入位置”，如此实现的插入排序为折半插入排序。其算法如下： template<class Elem> void BiInsertionSort (Elem R[]， int n) { // 对记录序列R[1..n]作折半插入排序。 for ( i=2; i<=L.length; ++i ) { R[0] = R; // 将R暂存到R[0] low = 1; high = i-1; while (low<=high) { //在R[low..high]中折半查找插入的位置 m = (low+high)/2; // 折半 if (R[0].key < R[m].key)) high = m-1; // 插入点在低半区 else low = m+1; // 插入点在高半区 } for ( j=i-1; j>=high+1; --j ) R[j+1] = R[j]; // 记录后移 R[high+1] = R[0]; // 插入 } } // BInsertSort 折半插入排序比直接插入排序明显地减少了关键字间的“比较”次数，但记录“移动”的次数不变。 [III]表插入排序 为了减少在排序过程中进行的“移动”记录的操作，必须改变排序过程中采用的存储结构。利用静态链表进行排序，并在排序完成之后，一次性地调整各个记录相互之间的位置，即将每个记录都调整到它们所应该在的位置上。 算法描述如下： template<class Elem> void LInsertionSort (Elem SL[]， int n) { // 对记录序列SL[1..n]作表插入排序。 SL[0].key = MAXINT ; SL[0].next = 1; SL[1].next = 0; for ( i=2; i<=n; ++i ) for ( j=0, k = SL[0].next; SL[k].key <= SL.key ; j = k, k = SL[k].next ) { SL[j].next = i; SL.next = k; } // 结点i插入在结点j和结点k之间 }// LinsertionSort 关于如在排序之后调整记录序列： 算法中使用了三个指针: 其中：p指示第i个记录的当前位置； i指示第i个记录应在的位置； q指示第i+1个