有向图最多叶子生成树问题研究

为求解有向图最多叶子生成树(出分枝)问题,提出了一些规约规则,对有向图实施这些规约规则能降低原图的规模;随后设计了近似算法在规约后的图中求解指定根节点的最多叶子出分枝问题。对于用近似算法求得的出分枝,又结合前面的规约规则设计了优化规则,以进一步通过优化变换增加出分枝的叶子节点。仿真实验表明,规约规则、近似算法和优化规则是有效的。     

最小生成树的算法

本文提出了一个利用集合运算生成最小生成树的算法。研究了实现集合运算的数据结构及施加在这个结构上的算法。该算法利用公式分组排序。利用路径压缩的方法进行查找，并运算。该算法将有Ｎ个顶点Ｅ条边的无向连通网络生成最小生成树的期望时间是Ｏ。     

基于最小生成树的LEACH路由算法研究

设计能量有效的路由协议以延长网络生存周期,提供优化可靠的网络服务成为资源有限的无线传感器网络研究的核心问题.为了节省无线传感器网络整体能耗,基于最小生成树理论,提出建立数据汇聚的最小能耗树.通过仿真比较.新的路由算法较优于传统LEACH路由算法.该路由算法能够延长网络生存周期,有效节省网络总能耗.     

最小生成树的算法——减枝算法

最小生成树是数据结构中图的一种重要应用,对于具有n个顶点的带权连通图可以建立许多不同的生成树.Kruskal算法和Prim算法是求最小生成树的常用算法.本文讨论了一种新的算法.     

一种无向图的生成树算法

求无向图的生成树是在网络和回路分析中经常遇到的重要问题。文章描述采用计算树的方法求解无向图的生成树,这种方法是通过列举生成树之间的差别来实现的。     

最小比率生成树的竞争决策算法

最小比率生成树是找出目标函数形式为两个线性函数比值最小的生成树,例如总代价与总收益比值最小的生成树。当不限制分母的符号时,这是一个NP-hard问题。在分析最小比率生成树数学性质的基础上,提出了最小比率生成树的竞争决策算法。为了防止算法陷入局部最优,采用edge_exchange操作来增加算法的搜索范围。为了验证算法的有效性,采用无关和相关两种策略产生测试数据,并使用Delphi 7.0实现了算法的具体步骤。     

算术表达式的最优并行计算树的生成算法

本文根据机器人动力学控制计算的需要,提出了一种关于算术表达式的最优并行计算树的生成算法,利用该算法在 MIMD 计算机上计算一个表达式所需的时间可以达到最短.     

赋权有向图的最小生成树算法

针对赋权有向图最小生成树问题存在可行解的情况,根据树节点入度最大值为1的性质,提出赋权有向图最小生成树性质。采用反证法,调整生成树根节点到弧头的路径来证明赋权有向图MST性质的正确性。基于赋权有向图MST性质,给出改进的Prim和Kruskal算法及其时间复杂度分析。实验给出构造某赋权有向图实例最小生成树的具体步骤,表明这2种算法能正确有效地构造赋权有向图最小生成树。     

基于Prim算法和Kruskal算法的最小生成树优化研究

文章从目前最常见的两种在图最小生成树算法,即Prim和Kruskal算法,展开了阐述和分析,运用了大量的数据和实例对这两种计算方法进行了分析和研究。通过试验并对Prim算法进行改进,从图中每个顶点的度数入手,采取删除某些无用边的思想方法,给出了一个寻找最小生成树的算法,使其能动态调整自身的性能,既适合于稠密图,又适合于稀疏图。     

生成树算法在网桥中的应用

本文阐述了在局域网环境中,使用网桥的原因、网桥连接多个子网时出现的问题,以及如何使用生成树算法来解决。     

顶点覆盖问题线性内核算法

参数复杂性作为算法研究的一个重要分支近10年在国际上受到了广泛的关注,线性内核问题作为参数复杂性研究的一类重要问题被广泛研究.主要给出了顶点覆盖问题的线性内核算法,在国内首次从理论上证明了顶点覆盖问题存在线性内核.算法首先通过顶点覆盖问题的2近似算法,将图的顶点集合分成两个顶点集合A,B,进而通过一系列规约将原始图的顶点覆盖问题转换到新图的顶点覆盖问题,然后证明了新图的顶点数目至多为2k,并且2k是这个问题的下界(k为参数具体定义见文章).     

多参数最小支撑树问题的复杂性和算法

建立了多参数最小支撑树问题（ＲＭＳＴ）的模型,并证明该问题是ＮＰ－完全的。利用经典Ｇｒｅｅｄｙ算法,给出了该问题的一个近似算法,并分析了该近似算法的性能比,证明了所给出的界是紧的。     

最小生成树灵敏度分析算法研究

在最小生成树数学性质的基础上,给出最小生成树灵敏度分析算法.该算法在图的各种属性发生变化(如边的权值变化、增加或删除边或结点)的情况下,在原有最小生成树的基础上快速调整,而不是从头计算来得到新的最优解.算法还给出了每边权值在何范围内变化时,最优解不变.最后通过一个示例来说明算法的原理及应用.     

基于蚂蚁搜索度约束最小生成树的改进算法

针对度约束最小生成树问题,对基本的蚁群算法进行改进。提出了度信息的概念来改进转移概率,保证算法获得可行解;同时采用基于度的禁忌表这种数据结构来表示度约束生成树,并与深度优先搜索的思想结合,保证得到树的连通性;将遗传算法中的变异特征引入蚁群算法,对生成树进行局部优化。不仅提高算法的效率,而且避免早熟收敛。通过数值试验验证新算法的可行性,并与其他算法进行比较,取得了良好的效果。     

一种基于最小生成树的多目标进化算法

怎样保证朝Pareto最优解的方向搜索和如何获得均匀分布且范围广泛的非支配解是多目标进化算法(MOEA)设计时的两个关键问题,它们很大程度上取决于适应度赋值和外部种群维护这两个重要部分.提出了一种基于最小生成树的多目标进化算法(MST_MOEA).在考虑了个体间支配关系的基础上,利用个体与非支配集的距离和不同等级个体的树聚集密度来对适应度赋值;在外部种群的非支配解个数超过规定的种群规模时,用树的度数和树聚集密度对其进行修剪.将其应用于不同维数下9个测试函数,并与NSGA-II,SPEA2进行对比,结果证实了算法良好的收敛性和分布性.     

一种新的求解度约束最小生成树的遗传算法

染色体编码是遗传算法的关键内容,编码的优劣并直接影响算法的性能.提出了基于过程控制的生成树编码方法--PC编码.PC码为定长的整数向量,使用PC编码求解特定生成树问题时,首先选定的一个有效算法,并将修改为可控算法,然后用编码向量控制算法的运行过程,从面得到唯一生成树.为了求解度约束最小生成树(DCMST)问题,在D-Prim算法的基础上,设计r过程可控的度约束生成树构造PC-Prim算法.给出了以PC-Prim算法作为译码器的求解DC-MST问题的遗传算法.仿真结果表明遗传算法求解精度和运行时间均优于参与其他算法.     

求解多目标最小生成树问题的改进算法

多目标最小生成树问题是典型的NP问题,Zhou和Gen提出了一种用于计数多目标最小生成树问题的所有非劣最优最小生成树的算法,但该算法无法保证能够找到所有非劣最优最小生成树.针对此问题,提出一种改进的计数算法,并定性说明改进算法能够找到问题的所有非劣最优最小生成树.改进算法在进行子树剔除时增加了一些条件.模拟实验结果表明,改进后的计数算法能够找到所有的非劣最优解.这也说明该算法具有应用的潜力.     

加权3-Set Packing问题的核心化

Packing和Matching问题是一类重要的NP难解问题,该类问题的参数算法和核心化研究受到了人们广泛的关注.主要研究了加权3-SetPacking的核心化算法.对于加权3-SetPacking问题,基于对问题结构的深入分析,提出并证明了2个简化规则.首先限定加权3-SetPacking问题实例中包含给定2个元素的集合的个数,然后在限定问题实例中包含1个给定元素的集合的个数.基于对集合个数的限定,得到问题实例中总的集合个数的上界.并基于上述性质得到2个简化规则,可得到加权3-SetPacking问题大小为27k3-36k2+12k的核,该核心化结果是加权3-SetPacking问题的首个核心化结果.得到的加权3-SetPacking的核心化过程同样适用于加权3D-Matching问题的核化,可得到与加权3-SetPacking问题同样大小的问题核.     

Approximating the Maximum Internal Spanning Tree problem

Given an undirected connected graph G$G$ we consider the problem of finding a spanning tree of G$G$ which has a maximum number of internal (non-leaf) vertices among all spanning trees of G$G$. This problem, called Maximum Internal Spanning Tree problem, is clearly NP-hard since it is a generalization of the Hamiltonian Path problem. From the optimization point of view the Maximum Internal Spanning Tree problem is equivalent to the Minimum Leaf Spanning Tree problem. However, the two problems have different approximability properties. Lu and Ravi proved that the latter has no constant factor approximation–unless P = NP–, while Salamon and Wiener gave a linear-time 2-approximation algorithm for the Maximum Internal Spanning Tree problem.     

一种基于最小生成树的非均匀分簇路由算法

分簇式路由是无线传感器网络路由协议研究的重点,本文提出一种新的基于最小生成树的非均匀分簇路由算法,该算法利用EECS路由协议产生大小非均匀的簇,簇内结点通过单跳的方式将数据发送给簇首结点,所有簇首结点构成最小生成树路由网络,并通过树内结点的多跳通信,最终将数据发送给sink结点.实验证明,本文算法与EECS相比能够更加有效地降低整个网络的能量消耗,延长网络的生命周期.