共查询到18条相似文献,搜索用时 46 毫秒
1.
节点加权的Steiner树问题是组合优化中一个经典的NP-hard问题,现有算法研究该问题时存在时间复杂性高或无法得到最优解的缺点。针对现有算法的不足,提出了一个基于降阶技术的回溯算法。首先研究该问题的数学性质,利用数学性质对该问题进行降阶以缩小问题的规模;接着提出上界子算法和下界子算法,利用上下界子算法对该问题的解空间树进行剪枝,提高搜索效率;最后利用上下界子算法和数学性质设计了一个回溯算法求解该问题。示例分析以及实验的结果表明,该算法不仅时间复杂性较低而且可以得到问题的最优解。 相似文献
2.
构造最小代价树问题可形式化为图论中Steiner树问题。而Steiner树的求解已经被证明是一个NP-complete问题,不可能在多项式时间求得其精确解,所以出现许多启发式算法:在可接受时间内,得到一棵近似的最优多播树。这些算法一般先指定所有链接边的费用,通过一定方法或规则,找出包含源端和所有目的端的一棵近似最优的多播树。很显然,它们并没有考虑由于路径的共享重叠而引起最小生成树链接边费用的变化。现利用CBT算法思想对变化的费用进行建模并对典型启发式算法作了改进,以适应不断变化了的链路费用。 相似文献
3.
基于MPH的时延约束Steiner树算法 总被引:2,自引:0,他引:2
为了在时延约束条件下进一步优化组播树代价,并降低算法计算复杂度,研究了时延受限的Steiner树问题.分析了MPH(minimum path heuristic)算法的计算复杂度;在此基础上设计了一个时延约束Steiner树算法DCMPH(delay constrained MPH)用于构造时延约束最小代价组播树.该算法中每个目的结点通过与当前组播树有最小代价的路径加入组播树;若时延不满足要求,则通过合并最小时延SPT(shortest path tree)树进而产生一个满足时延约束的最小代价组播树.仿真实验表明,DCMPH算法生成的组播树在保证时延要求的情况下,与同类算法相比取得了很好的代价性能和较低的计算复杂度. 相似文献
4.
介绍了一种工程上有十分重要的运用价值的污水网络最短树中Steiner点位置的算法。文中从工程实际出发,将高阶非线性方程组转化成多个一阶或二阶的线性方程组,使计算机进行快速迭代运算成为可能。文章对算法的收敛性作了严格的数学证明。该方法用于 无锡市的污水改造工程,取得了令人满意的结果。 相似文献
5.
分析了时延受限的Steiner树问题,总结了在构建组播树过程中的代价和计算复杂度变化规律,并根据实际网络环境,从优化最短路径出发,提出了一种基于优化最短路径的时延受限组播路由算法AOSPMPH。该算法以MPH算法为基础,利用Floyd最短路径优化算法求出节点对之间的最短路径,选择满足时延要求的最小代价路径加入组播树,进而产生一棵满足时延约束的最小代价组播树。仿真结果表明,AOSPMPH不但能正确地构造时延约束组播树,而且其代价和计算复杂度与其他同类算法相比得到了优化。 相似文献
6.
通过优化物流的运输网络,可以有效地降低物流成本。集中配送的物流网络优化问题可以转换成求解节点带权的Steiner最小树问题,这是一个NP-hard问题。运用参数理论,提出一种新的启发式解决算法P-NSMT。算法的思想是:首先尽可能只利用终端节点构造一棵连通的最小生成树,然后逐步向树中添加能减少生成树总权值的Steiner节点,最终生成一棵节点总数不超过参数k的Steiner最小树。实验表明,与同类型其他算法相比,P-NSMT算法具有更好的准确性和时间效率,特别适应于网络规模大、终端配送节点数目较少的物流网络。 相似文献
7.
8.
低代价最短路径树是一种广泛使用的多播树.它能够在保证传送时延最小的同时尽量降低带宽消耗.在DDSP(destination-driven shortest path)算法的基础上,通过改进节点的搜索过程,提出了快速低代价最短路径树算法FLSPT(fast loW-coSt shortest path tree).该算法构造的最短路径树与DDSP算法构造的树具有相同的性能,但其时间复杂度低于DDSP算法.随机网络模型的仿真结果表明,FLSPT算法效率更高. 相似文献
9.
10.
11.
针对基于分辨矩阵约简算法中存在冗余元素,从而导致空间存储代价高的问题,提出一种基于加权浓缩树的属性约简算法。该算法可以进一步剔除冗余元素,压缩存储分辨矩阵中的信息,并且在构建树结构的过程当中考虑了属性重要度的影响。实验结果与C-Tree及差别信息树算法进行比较,提出的算法可以获得更优的属性约简结果,有效地降低了空间复杂度。 相似文献
12.
针对无线传感器网络容易遭受恶劣环境破坏,连通恢复后各关键节点的能量损耗远大于其他节点从而导致网络断连的问题,提出基于斯坦纳树和泰森多边形的连通恢复算法(CRAST)。首先,将被分割的节点分区抽象为离散点,枚举出离散点区域内的所有非退化四边形,再使用四边形斯坦纳树结构对这些非退化四边形部署中继节点以达到连通恢复。然后,用关键节点构建Delaunay三角网,通过Delaunay三角网构建出整个无线传感器网络的泰森多边形拓扑结构。最后,在泰森多边形所有顶点部署可移动的备用中继节点,在关键节点损坏时通过比较备用节点所占关键节点对应的所有备用节点比重选择要移动的备用节点,移动备用中继节点替换损坏的关键节点。整个算法能使传感器网络以最少的代价实现连通恢复,并且拥有较强的高效性和健壮性。 相似文献
13.
针对二叉树支持向量机多分类算法准确率与分类效率较低的问题,提出了一种基于加权模糊隶属度的二叉树支持向量机多分类算法(binary tree support vector machines multi-classification algorithm based on weighted fuzzy membership,PF-BTSVM)。该算法依据最大最小样本距离与质心距离构造出一个近似完全二叉树,提高了整体结构的分类效率;利用模糊隶属度函数以及正负辅助惩罚因子对训练集进行筛选,剔除掉对分类无用的样本与噪声值,实现了训练集的提纯并且削弱了不平衡分类时超平面的偏移。在数据集上的实验结果表明,与其他二叉树多分类算法相比,该算法在提高了分类准确率以及稳定性的的同时还加快了训练与分类的速度,而且这种优势当分类的不平衡度越大时越明显。 相似文献
14.
15.
16.
在构造决策树的过程中,分裂属性选择的标准直接影响分类的效果。分析了现有改进的ID3算法不同程度地存在学习效率偏低和对多值属性重要性的主观评测等问题,提出一种高效而且可靠的基于灰色关联度的决策树改进算法。该算法通过灰色关联分析建立各特征属性与类别属性之间的关系,进而利用灰色关联度来修正取值较多但非重要属性的信息增益。通过实验与其它ID3改进算法进行了比较,验证了改进后的算法是有效的。 相似文献
17.
18.
在深入研究了异步可延伸能效(SEAD)算法和MintRoute算法的基础上,提出了剩余能量树路由算法,该算法将网络中的节点分成能量相近的区域,再利用SEAD算法的思想,在每个能量相近的区域中构建以采样节点为根,传递节点作为枝叶的树状网络结构模型,将树最末端的节点作为代理节点,Sink节点移动时,只需要保持同代理节点的通信,便可以保证Sink节点同整个网络连通。运用该路由算法可以很好地解决无线传感器网络中的因某个节点过早死亡而导致网络路由"瓶颈"问题和节点间的信息泛洪问题。采用剩余能量树路由算法,可以使网络能量得到更均衡合理充分的利用,仿真实验结果表明,该算法可以很好地延长网络寿命。 相似文献