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

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

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

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

求解度约束最小生成树的一种启发式方法

针对网络设计和优化中度约束最小生成树问题,提出了一种基于贪心思想的启发式算法求解度约束最小生成树.在最小生成树的基础上,将超过度约束的顶点降低度数使之满足度约束条件.经大量数据测试并与其他算法进行比较,表明了该算法的有效性和通用性.     

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

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

无线传感器网络LEACH簇树路由协议研究

基于LEACH的簇树路由协议是目前无线传感器网络研究的热点之一,由于传统的构造最小生成树的算法不能适应网络中节点密度的变化,制约其更广泛的应用。在对LEACH簇树路由和传统的连通网络中构造最小生成树算法的分析基础上,结合动态优化的思想,提出了一种新的基于Prim算法的构造最小生成树算法,并将其应用到簇树路由中,使得网络寿命延长,同时增强了对网络节点密度的适应性。仿真结果说明了该算法的可行性和有效性。     

模糊权值网络最小生成树问题研究

针对边权值为梯形模糊数的模糊权值网络,提出一种求解该网络最小生成树问题的新算法.该算法首先基于梯形模糊结构元加权排序思想,将梯形模糊数转化为其加权特征数进行排序;然后利用经典的Dijkstra算法求解转化为边权值确定的网络的最小生成树问题,即得该模糊权值网络的最小生成树;最后对算法的复杂度进行分析,并通过算例验证了算法的有效性.     

改进的时延约束Steiner树算法

针对现有时延约束Steiner树算法时间复杂度较高以及生成的组播树代价较高的问题,提出了一种改进的时延约束Steiner树算法.该算法采用Dijkstra算法路径递增的基本思想和链路共享的方法,在快速搜索阶段,依次搜索到当前树有最小可行代价的节点,将目的节点通过最小可行代价路径加入组播树;在异常处理阶段,将遗漏的目的节点通过最小时延路径加入组播树,进而生成满足时延约束的Steiner树.理论分析和实验结果表明,与同类算法相比,该算法能够以较低的时间复杂度,取得较好的组播树代价.     

设计无标度网络的一种新方法

提出了一种设计生成满足任意指定幂律要求的无标度网络的新方法.该方法利用了无标度网络的一个重要性质,即无标度网络的最终形成是受其度的几何均值控制的.为此提出了一个算法,该算法从一个合理的小世界网络开始,通过富者愈富的原则不断地对当前网络实施删边和加边操作,同时保证网络中的节点个数、网络中的总边数和网络的连通性不变,直到网络中节点度的几何均值达到了一个特定的值为止,生成一个预定的无标度网络.数据仿真验证了该方法总可以生成一个满足指定幂律要求的无标度网络.     

一种基于多叶节点生成树的低延时数据融合调度算法

无线传感器网络是物联网信息采集的基础载体。数据融合技术在节省无线传感器网络资源的同时会引起较大的延时。在实时应用场景下,研究最小延时数据融合调度问题就非常关键。首先给出了最小延时数据融合调度问题的形式化描述,依据多叶节点融合树有利于增加同时传输的节点数量的思想,提出了一种基于多叶节点生成树的低延时数据融合调度算法(LDAS),该算法包括多叶节点数据融合树的构建阶段和融合调度阶段。最后通过仿真和对比证明了方案的有效性。     

附有条件的最小支撑树算法

传统最小生成树算法不能解决:度约束条件下的最小支撑树问题;动态网络的最小支撑树问题;边约束条件下的最小支撑树问题。遗传算法可以求解度约束条件下的最小支撑树问题,但存在效率低、编码复杂等缺陷。归纳了3类附有条件的最小支撑树数学模型,在最小支撑树传统算法基础上,提出了3类附有条件的最小支撑树算法。算法测试和比较表明:附有条件的最小支撑树算法是完全可行和有效的。     

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

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

基于DPCNN的无向赋权图的最小生成树的求解

 利用脉冲耦合神经网络(PCNN,Pulse Coupled Neural Network)的脉冲波并行传播特性,在其时延脉冲耦合神经网络(DPCNN,Delay PCNN)的基础上提出了一种求解无向赋权图最小生成树的新算法.算法针对最小生成树的权值总和最小且连通的性质,结合时延脉冲耦合神经网络脉冲波的并行传播,通过求解无向赋权图的最短路径并对其连通性进行判断,采用迭代的方法,成功地求解了无向赋权图的最小生成树.最后给出了仿真实验,证明了该方法的有效性,与传统算法比较有一定的优势.     

A new algorithm for degree-constrained minimum spanning tree based on the reduction technique

The degree-constrained minimum spanning tree （DCMST） is an NP-hard problem in graph theory. It consists of finding a spanning tree whose vertices should not exceed some given maximum degrees and whose total edge length is minimal. In this paper, novel mathematical properties for DCMST are indicated which lead to a new reduction algorithm that can significantly reduce the size of the problem. Also an algorithm for DCMST to solve the smaller problem is presented which has been preprocessed by reduction algorithm.     

A new algorithm for degree-constrained minimum spanning tree based on the reduction technique

The degree-constrained minimum spanning tree (DCMST) is an NP-hard problem in graph theory. It consists of finding a spanning tree whose vertices should not exceed some given maximum degrees and whose total edge length is minimal. In this paper, novel mathematical properties for DCMST are indicated which lead to a new reduction algorithm that can significantly reduce the size of the problem. Also an algorithm for DCMST to solve the smaller problem is presented which has been pre-processed by reduction algorithm.     

遗传算法在网络最短路径问题上的应用

将网络最短路径问题抽象为求最小生成树问题,分析了最小生成树在解决实际问题时的局限性,引入了节点的度的概念;针对一般遗传算法在求解某些工程问题时存在的一些不足,提出了用量化约束条件来改进适应值函数、节点与度约束相结合编码的二进制编码方式、基于节点域的交叉和变异运算的策略.通过对公路交通网络的仿真表明,采用一般遗传算法与普通遗传算法分别求解,数值计算结果证明了改进后的遗传算法的可行性.     

基于最小生成树的R~*-树结点分裂算法

针对R*-树应用到逆向工程领域时遇到的适用性差等问题,提出了一种新的R*-树结点分裂算法.该算法将R*-树索引结点表示为轴向包围盒,依据轴向包围盒外接球间的重叠度计算结点相似度,并将其作为权值构建结点无向连通图,用来求解结点无向连通图的最小生成树.沿最大权值边将最小生成树分裂为2棵子树,并基于结点外接球体积对R*-树结构进行优化,从而实现了R*-树结点分裂.实例表明,R*-树结点分裂算法可处理各种复杂数据的结点分裂问题,能够有效地提高R*-树的构建效率及空间数据的查询效率.     

多目标优化问题的研究

针对传统方法求解多目标优化问题的局限性,应用一种新的算法求解。遗传算法从问题解的串集开始搜索,覆盖面大,可以同时处理群体中的多个个体,利于全局择优,减少陷入局部最优的风险,而最小生成树具有过程简单清晰、适用性广泛的特点,结合两者的优点,构造了基于生成树的遗传算法。首先通过加权目标规划法求出最优解,然后通过遗传算法和基于生成树的遗传算法求解,结果表明,对于小规模的多目标优化问题,两种算法都可以求出最优解,在求解时间方面,基于生成树的遗传算法比遗传算法更优越。     

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

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

Optimization in the Migration Problem of Mobile Agents in Distributed Information Retrieval Systems

In this paper,we employ genetic algorithms to solve the migration problem (MP).We propose a new encoding scheme to represent trees,which is composed of two parts;the pre-ordered traversal sequence of tree vertices and the children number sequence of corresponding tree vertices.The proposed encoding scheme has the advantages of simplicity for encoding and decoding,ease for GA operations,and better equilibrium between exploration and exploitation.It is also adaptive in that,with few restrictions on the length of code,it can be freely lengthened or shortened according to the characteristics of the problem space.Furthermore,the encoding scheme is highly applicable to the degreeconstrained minimum spanning tree problem because it also contains the degree information of each node.The simulation results demonstrate the higher performance of our algorithm,with fast convergence to the optima or sub-optima on various problem sizes.Comparing with the binary string encoding of vertices,when the problem size is large,our algorithm runs remarkably faster with comparable search capability.