求解最大度约束下最小生成树的新算法

针对网络优化中度约束最小生成树问题的特征,融合破圈法的基本思想,提出了一种求解网络G关于指定节点的最大度约束下最小生成树的新算法。该算法在保证指定节点最大度的前提下,每次通过去掉圈中权最大的边,最终构造出网络G关于指定节点的最大度约束下的最小生成树。算法证明和算例都表明了该算法的有效性。     

一类度约束最小生成树问题的Dijkstra算法

度约束最小生成树问题是网络设计和优化中的一个NP难题。结合该问题的特征,基于Dijkstra算法的基本思想,提出了一种求解网络G关于指定节点的最大度最小生成树的新算法。该算法在保证指定节点最大度的前提下,每次通过选取剩余边中权最小的边加入当前网络,最终得到网络G关于指定节点的最大度最小生成树。同时对算法的复杂度进行了分析。最后通过与其他算法的仿真比较和算例,表明了新算法的有效性。     

具有两个次限制点的第n棵次限制最小树

给定赋权在通图G=(V,E),指定P_1,P_2∈V,且P_1P_2在G中无边相连,再给定两对正整数a_1≤b_1,a_2≤b_2,若G的一棵支撑树T在P_i处的次|T(P_i)|满足a_1≤≤|T(P_i)≤b_i,则称为一棵次限制树。本文讨论了有序地寻找第n棵次限制最小树。把R.N.BurnS和C.E.Haff有关第n棵支撑树的结果推广到次限制树的情况。     

一类特殊的极大＋和支撑树在调整和权值下的逆问题

本文研究的是一类特殊的极大＋和支撑树在调整和权值下的逆问题．给定一个边赋权连通网络G=（VE,c,w）,对于每一条边e∈E,已知一个费用c（e）和一个权值叫（e）,极大＋和支撑树问题是指寻找一棵支撑树T＊,使得其是权值marxw（e）＋∑c（e）最小的一棵支撑树．而在极大＋和支撑树的逆问题中,给定一棵支撑树％,eET它不是已知网络中最优的极大＋和支撑树,要求调整网络中各边的费用c（e）,使死变成调整后网络中最优的极大＋和支撑树,目标函数是使得在l1模意义下的边权调整费用尽可能的小．本文针对已知网络中各边费用都相等这一特殊情况,给出了求解该逆问题的列生成算法,每次迭代时入基向量的选择可以转化为一个新参数下的极大＋和支撑树问题,从而可在多项式时间内确定入基向量的选择．本文最后给出了一个实例说明算法的有效性．     

多目标MIN-MAX度最小树问题及其求解

在多目标最小生成树问题和MIN-MAX度最小树问题的基础上,探讨使生成树最大顶点度数以及总权重都尽可能小的另类多目标MIN-MAX度最小生成树问题。分析了这一特殊的顶点度约束与Hamilton路的关联性质,在此基础上设计了先Hamilton路再MIN-MAX度最小树的独特求解方案。根据初始条件不同,当网络图不存在Hamilton路时,引入改进的蚁群优化算法,将转移概率由基本的指数形式改进为线性形式,在不影响求解质量的前提下,提高计算效率。针对以上策略,设计了相应的求解方案,并在计算机上用Delphi编程实现。大量数值算例验证表明,算法能快速有效地求解多目标情形下的MIN-MAX度最小生成树问题。     

O（n）—时间有序树生成算法

以平面上长2π—2的简单、封闭随机行走为编码,构造了n结点有序树的顺序生成和随机生成算法.并证明顺序生成或随机生成任意一棵n结点有序树均是O(n)-时间的。对于有序树的生成来说,简单、封闭的随机行走是最有效的编码.     

最小度生成树的最大度算法

最小度生成树问题是一个NP难问题.给出了求最小度生成树的一个直观近似算法:找到图G的最大度,从其所在的基本圈上删掉1条与其关联的边,如此循环,直到图G的最大度不在任何基本圈上,如还有其它基本圈,删掉圈上的1条边,得到1棵生成树.这种算法得到的生成树的最大度数比最优解的度数至多大1.     

论迭代思维

创造性思维的特征是表现在创造性思维的具体过程中的,而创造性思维过程是遵循一定的具体方法进行的。一般认为创造性思维的基本方法或有效途径是求异思维与求同思维的反复结合。现引进数学上的一种计算方法——迭代法概括创造性思维方法。一、数学上的迭代法: 迭代法是数学上的一个重要方法。在计算方法中除了用它求方程和方程组的根外,还可以用来求解微分方程以及其它许多问题。其主要思想是:首先建立一个迭代格式如A_i=B·A_(i-1),通过迭代计算可求出A_i的一个序列,其极限收敛于真解A(满足一定的精确度即可)。收敛速度的快慢是衡量迭代法的一个重要准则。而每次迭代中计算的工作量也是一个重要标     

基于Prim算法的度约束最小生成树问题研究

针对一类度约束最小生成树问题,基于传统最小生成树问题的Prim算法,设计了一种求解算法.该算法在保证网络中指定节点的度不变的前提下,构造了网络关于指定节点的最大度最小生成树.与经典的Gloveklingman算法进行了仿真比较,结果表明,该算法是求解度约束最小生成树问题的一种有效算法.     

先长成大树

正一棵小树苗刚从土里钻出来不久,它喜欢那蓝蓝的天,飘浮的云,它更喜欢那空中飞过的鸟。一天,一只翠鸟落在小树的身边,小树欢喜极了,说:"小鸟小鸟,快来跟我玩吧!"翠鸟蹦了几下,瞅了它一眼,还没等回答,就"啾"的一声飞走了。小树很遗憾,心想:它大概是不喜欢我。又过了几天,小树看见一大群五颜六色的鸟,落在几棵高耸入云的大