节点加权的Steiner树问题的降阶回溯算法

节点加权的Steiner树问题是组合优化中一个经典的NP-hard问题,现有算法研究该问题时存在时间复杂性高或无法得到最优解的缺点。针对现有算法的不足,提出了一个基于降阶技术的回溯算法。首先研究该问题的数学性质,利用数学性质对该问题进行降阶以缩小问题的规模;接着提出上界子算法和下界子算法,利用上下界子算法对该问题的解空间树进行剪枝,提高搜索效率;最后利用上下界子算法和数学性质设计了一个回溯算法求解该问题。示例分析以及实验的结果表明,该算法不仅时间复杂性较低而且可以得到问题的最优解。

基于加权节点的Steiner树启发式算法

Steiner最小树问题是一个NP完全问题,被广泛应用在通信网络中点到多点的路由选择。为了实现更多链路的共享,减少所求Steiner树的费用,提出了一种基于加权节点求解Steiner树的启发式(NWMPH)算法。该算法构造了非正则点的权值公式,给每一个非正则点赋权值,根据权值对链路的费用进行修正,通过修正费用最短路径依次把所有的正则点连接起来,得到包含所有正则点的最小树。对STEINLIB标准数据集中的部分数据进行计算,结果表明:NWMPH算法与MPH算法所用时间基本相同,得到的Steiner树费用优于MPH算法;NWMPH算法比KBMPH算法所用时间少,得到的Steiner树费用绝大多数优于KBMPH算法。

物流网络中节点带权的Steiner最小树的参数算法

通过优化物流的运输网络,可以有效地降低物流成本。集中配送的物流网络优化问题可以转换成求解节点带权的Steiner最小树问题,这是一个NP-hard问题。运用参数理论,提出一种新的启发式解决算法P-NSMT。算法的思想是:首先尽可能只利用终端节点构造一棵连通的最小生成树,然后逐步向树中添加能减少生成树总权值的Steiner节点,最终生成一棵节点总数不超过参数k的Steiner最小树。实验表明,与同类型其他算法相比,P-NSMT算法具有更好的准确性和时间效率,特别适应于网络规模大、终端配送节点数目较少的物流网络。

E^n空间中Steiner树的性质与极值

将平面上著名的 Steiner树问题推广到 n维欧氏空间 En 中 ,得到了单形中 Steiner点的一些重要性质以及一些加权几何不等式 .

一种节点加权的相似重复XML数据检测算法

XML类型的数据成为当前主流的数据形式,本文提出一种检测XML数据相似性的方法,即将XML文档转换成树结构的基础上,对树结构的节点加权,并结合树编辑距离算法。通过XML带权树各属性权值计算的相似度对数据进行粗略匹配与聚集,而在重新聚集的集合中使用树编辑距离算法更直接的进行相似性检测。由于XML数据集合范围的缩小,树编辑距离算法操作的次数减少,从而节省了一定的时间。

基于加权绝对值距离Steiner最优树的选址问题

提出基于加权绝对值距离Steiner最优树思想的选址模型,给出了该模型的蚂蚁算法实现策略.在此基础上,分析了电子商务环境下企业配送中心选址问题,并用算例验证了该选址方案的可行性.

主网与配电网协调规划的评价指标和规划方法

城市110kV变电站作为连接主网与配电网的纽带,其选址和供电范围的划分是主网与配电网协调(以下简称主配网协调)规划的关键。文中提出协调因子及主配网协调规划评价模型,强调以提高总体运行均衡性为目标的电网规划思想。首先对变电站的基本属性进行分析,提出由运行率和关联度构成的负重系数的概念;然后利用约束圆环协调规划范围,将负重系数作为权值,利用改进后的加权Steiner最小树理论优化变电站选址;进而确定变电站的容量及供电范围。实际算例表明,从主配网协调程度考虑,所提出方法的规划结果优于传统选址规划结果。

全部到全部组播的核管理机制及其算法研究

组播是因特网上的重要应用和具有挑战性的研究问题,现在大多数已有的组播算法是基于有源树的,存在带宽利用率和传输效率问题.有核组播是在网络中选取一个核节点,并以它作为根来建立一棵连接组播组中所有成员节点的单一共享树,而不是为每个源节点建立一棵组播树,这是一种有效的方法.由于核节点选择的不同将导致组播树的不同,核节点实际上决定着有核组播的性能.因此,核选择及核迁移是有核组播里的两个重要问题.针对全部到全部的组播模型,先给出了一个以总代价最优为目标的核选择完全算法,该算法复杂度较低;然后针对实时应用设计了两个核选择近似算法,并分析了它们的近似比;最后提出了一种可扩放的核迁移算法,该算法中的树代价估算机制为核节点的迁移时机提供了一个可信的评价标准.

加权Steiner问题与加权GP猜想

加权Ｓｔｅｉｎｅｒ问题与加权ＧＰ猜想贝清泉（汕头大学数学系，汕头５１５０６３）已给平面上三定点Ａ，Ｂ，Ｃ，求点Ｐ使ＰＡ＋ＰＢ＋ＰＣ极小，这就是古典的Ｓｔｅｉｎｅｒ树问题．如令：ｆ（Ｐ’）一Ｐ’Ａ＋Ｐ’Ｂ＋Ｐ’Ｃ；ｋ＝ｄｒｉｎ什（Ｐ’ｎ＝ｍｉｎＪ＊’Ａ...

无线传感器网络拓扑修复算法综述

在无线传感器网络中,由于能量耗尽以及恶劣环境的影响,传感器节点容易出现故障导致网络不连通。为此,针对无线传感器网络中的拓扑修复问题,总结和分析近年来相关的主要方向和研究成果,同时根据网络故障规模的不同对小规模故障和大规模故障的网络修复算法进行分类总结以及优缺点分析。此外,从算法触发条件以及实现角度等方面对修复算法作进一步分类,并指出当前研究的不足和未来的改进方向。

大规模数据集谱聚类并行优化算法

为解决传统谱聚类算法在应用于大规模数据上时,复杂度较高且资源占用较大,导致算法聚类效果不好甚至无法聚类的问题,提出基于并行框架和采样相结合的改进谱聚类算法,算法在自适应相似矩阵计算基础上,通过数据分块和单向节点并行,提高算法相似矩阵的计算效率,通过Nyström加权抽样逼近,减少拉普拉斯矩阵特征向量的计算复杂度,最后通过KD树结构避免k-mean聚类过程的距离计算,从而提高了聚类效率。仿真实验结果表明,文中算法在取得与传统算法相近的聚类性能的同时,取得更好的加速比,验证了算法对大规模集的良好适应性。