图谱理论与复杂网络相关算法

基本信息

版　次： 1

页　数： 161

装　帧： 平装

开　本： 32开

所属分类： 图书>科学与自然>数学

内容简介

这些理论与算法不仅适用于工程结构设计，对其他工程优化设计问题亦具有通用性。　《工程优化理论与算法》可供从事航空、航天、机械、造船、车辆、建筑工程等工程设计领域的技术人员学习、使用，也可作为高等院校相关专业（包括力学专业）高年级大学生和研究生的教科书或参考书。2100433B

组合算法单纯形法

单纯形法是G.B.Dantzig在1947年提出的一种线性规划算法，他本人以及其他学者后来又提出多种形式的变形和改进。实践表明，单纯形法及其变形和改进是非常行之有效的，在市场上已经形成许多可以有效解央大型线性规划问题的软件包。线性规划研究线性目标函数在一组线性等式与线性不等式约束下的极值问题。这本来是连续问题，Dantzig发现线性规划问题的可行解集(即满足约束条件的点的全体)是一个超多面体。 如果它的最优解存在，那么最优解一定可以在这个超多面体的某个顶点取到。由于超多面体的顶点只有有限个，从而使线性规划成为一个组合优化问题。单纯形法是按照一定的规划，从可行解集的一个顶点转移到另一个顶点，使得目标函数的值不断地得到改进，最后达到最优。尽管单纯形法一直使用得很好，但在最坏情况下它需要指数运行时间，从而使线性规划问题是否属于P类一度成为人们关心的问题。1979年前一位苏联数学家提出一个多项式时间的线性规划算法——椭球算法， 从而解决了这个问题。1984年印度数学家N.Karmarkar又提出一个新的更好的多项式时间算法——投影算法。

组合算法排序和检索

将给定的元素序列按照某种顺序关系重新排列成有序序列称作排序。例如将n个数组成的序列按照从小到大的顺序重新排列；将n个英语单词组成的序列按照字典顺序重新排列。在给定的集合中查找某个特定的元素称作检索。例如从给定的n个数中找到最大的数。排序和检索算法已经成为数据结构中不可缺少的部分，是计算机科学技术中最基本、使用最频繁的算法。正因为如此，它们也是研究得最细致的一类组合算法(参见排序算法)。

组合算法图与网络优化算法

图与网络优化算法是组合算法中内容最丰富的部分。图论中的计算问题包括图的搜索路径问题、连通性问题可平面性检验、着色问题、网络优化等。图论中的著名算法有求最小生成树的Kruskal算法、求最短路的Dijkstra算法和Floyd算法、求二部图最大匹配(指派问题)的匈牙利算法、求一般图最大匹配的Edmonds"花”算法、求网络最大流和最小割的标号法等。

组合算法贪心法与拟阵

贪心法是求解关于独立系统组合优化问题的一种简单算法，求最小生成树的Kruskal算法就是一种贪心法。但是，贪心法并不总能找到最优独立集，贪心法能求得最优独立集的充分必要条件是L为一个拟阵。事实上，求最大生成树是关于拟阵的组合优化问题，而二部图的所有匹配构成的独立系统U不是拟阵。

组合算法穷举搜索

组合算法要解决的问题只有有限种可能，在没有更好办法时总可以用穷举搜索的办法来解决，即逐个检查所有可能的情况。当情况较多时这样做是很费时的。实际上，并不需要机械地检查每一种情况，常常有可能提前判断出某些情况不可能取到最优解，从而可以提前舍弃这些情况。这样使“隐含地”检查了所有情况，既减少了搜索量，又保证不漏掉最优解。参见回溯法。

组合算法分支限界法

分支限界法是一种用于求解组合优化问题的排除非解的搜索方法。它的基本思想是：把问题分成若干个子问题，估计子问题的目标函数值的上界或下界。对于最大值问题，子问题的下界也是原问题的下界。 当子问题的上界小于原问题的下界时，不可能在这个子问题中取得原问题的最优解，舍去这个子问题。否则将这个子问题再划分成若干更小的子问题，重复上述过程，直到没有需要检查的子问题为止。

其他组合算法还有动态规划，快速传里叶变换等 。2100433B