中国数学建模-编程交流-组合算法概论

《中国数学建模-编程交流-组合算法概论》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、中国数学建模-编程交流-组合算法概论中国数学建模-编程交流-组合算法概论卜数学思想卜编程交流卜学术朵谈

2、-EnglishFanswh-ee重登录隐身用户控制面板搜索风格论坛状态论坛展区社区服务社区休闲网站首页退出»VC++,C,Perl,Asp...编程学习，算法介绍.我的收件箱(0)屮国数学建模一学术区一编程交流一组合算法概论您是本帖的第623个阅读者*贴子主题：组合算法概论b等级：职业侠客文章:470积分：956门派：黑客帝国注册:2003-8-28鲜花⑴鸡蛋(0)楼主组合算法概论组合算法概论(ABriefIntroductiontoComb

3、inatorialAlgorithm)组合算法是算法分析学当中非常重要的一个分支，关于它在计算机科学的地位我就不敖述了，下面为大家整理了整个材料，算法是我收集的，只是分门别类简单介绍一下，然后把我的材料做了个整理，大家收藏吧，感觉挺有用的，费了我好长吋间和精力呀,我现在准备考研了，没有太多吋间发很多经典文章了，这片算是大部头了。关于组合学问题的算法，计算对象是离散的、有限的数学结构。从方法学的角度，组合算法包括算法设计和算法分析两个方面。关于算法设计，历史上已经总结出了若干带有普遍意义的方法和技术，包括动态规划、回溯法、分支限界法、分治法、贪心法

4、等。下面我们着重谈谈儿个有代表性的组合算法：单纯形法：这是一种线性规划算法，由G.B.Dantzig在1947年提出，后來由他和其他的学者乂提出了单纯形法的变形和改进。这些被实践证明都是行之有效的，线性规划研究线性目标函数在一组线性等式与线性不等式约束下的极值问题。这本来是连续问题，Dantzig发现线性规划问题的可行解集(即满足约束条件的点的全体)是一个超多面体。如果它的最优解存在，那么这个最优解一定可以在超多面体的一个顶点取到。由于超多面体的顶点只有有限个，从而使线性规划成为•个组和优化问题。单纯形法是按照一定的规则，从可行解集的一个顶点转移

5、到另一个顶点，使得目标函数的值不断地得到改进，最后达到最优。尽管单纯形法一直使用得很好，但是在最坏情况下它需要指数运行吋间，从而使线性规划问题是否属于P类一度成为人们关心的问题。后來的椭球算法和投影算法都很好的解决了这个问题。排序和检索：这两部分应当是大家比较熟悉的，所谓排序，就是将给定的元素序列按照某种顺序关系重新排列成有序序列。例如将n个数组成的序列按照从小到大的顺序重新排列；将n个英语单词组成的的序列按照字典顺序重新排列。所谓检索，就是在给定的集合中查找某个特定的元素或是元素组。排序和检索已经成为计算机科学技术中最基本、使用最频繁的算法。下

6、面我们专门谈谈排序算法(sortingalgorithm)o在讨论此种算法时，数据通常是指由若干记录组成的文件，每个记录包含一个或多个数据项，其中能够标志该记录的数据项称为键码。给定一文件的n个记录｛Rl,R2,…,Rn｝及其相应的键码的集合｛K1,K2,…,Kn｝。所谓排序算法就是在数据处理中将文件中的记录按键码的一定次序要求排列起來的算法。若待排序的文件能够同吋装入计算机的主存中，整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序；若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，有一部分必须放在外存上，则称此类排序

7、问题为外部排序。当待排序的文件中包含有一些相同键码的记录时，如果经过排序后这些和同的键码的记录的相对次序仍然保持不变，则相应的排序算法是稳定的，否则为不稳定的。如果排序算法设计成单处理机完成的，则此排序算法称为串行(或顺序)排序算法；如果排序算法时设计成多处理机实现的，则称为并行排序算法。首先谈谈内部排序：内部排序的过程是一个逐步扩大记录的有序序列长度的过程。在排序的过程中，参与排序的记录序列中存在两个区域：有序区和无序区。使有序区中记录的数目增加一个或儿个的操作称为一趟排序。逐步扩大记录有序序列长度的方法大致有下列儿类：一.插入排序假设在排序过

8、程中,记录序列R[l..n]的状态为:则一趟直接插入排序的基本思想为：将记录R插入到有序了序列R[l・•i-l]中，使记录的有序序列从R[l..i-1]变为R[l・.i]。显然，完成这个“插入”需分三步进行：1.查找R的插入位置j+1；2.将R[j+l・・i-1]中的记录后移一个位置；3.将R复制到R[j+1]的位置上。[叮直接插入排序利用顺序查找实现“在R[l・・iT]中查找R的插入位置”的插入排序。注意直接插入排序算法的三个要点：1.从R[i-U起向前进行顺序查找，监视哨设置在R[0]；R[0]二R;//设置“哨兵”for(j=i-l;R[0

9、].key