基于“最小差值法”的网络模型耗费代价研究

最小生成树算法是数据结构中,求网络模型耗费代价最优解的一个重要工具。现实生活中的连通网络模型复杂而多变,有时还需兼顾其它的目标,一棵最小生成树不足以解决问题,因此找出所有的最小生成树是很有必要的,在此提出一种新的寻找所有最小生成树的算法——最小差值法。无向连通图网络通过去掉连枝生成最小生成树,一个连枝加入最小生成树形成一个圈。这种算法是在一个圈中,用连枝的权与其它树枝的权分别作差,求最小差值。由最小差值是否为零,判断原有的最小生成树能否通过换进换出边,生成新的最小生成树。该算法能够有规律、高效率的寻找出所有的最小生成树。在找出的所有最小生成树方案中,选择符合实时情况的最小生成树方案,该方案即为网络耗费代价的最优解。     

带有度约束的最小耗费生成树的分支限界算法

最小耗费生成树算法已很成熟,如Dijkstra's 算法,Prim’s 算法等。但在实际应用中我们常会碰到一类问题,对最小耗费生成树中每个结点的度数有所限制。这便是带有度约束bi(i=1,2,…,n)的最小耗费生成树(DCMCST)问题,在管道系统、通信、计算机网络中均会遇到这样的问题。本文提出一种分枝界限算法来产生DCMCST。     

最小耗费生成树剔除算法及其正确性证明

文章提出了一种新的最小耗费生成树的算法，并对其正确性进行了证明。该算法通过从原图中逐步别除边来形成生成树，特别适用于当原图中边数较少(相对于顶点数)，或原图规模不大的情形。     

网络最小生成树更新策略

求解最小生成树问题被广泛应用于求解现实中的搜索相关问题。然而现实瞬息万变,一个连通网络的节点常常发生变动。而一旦发生改变,传统算法必须要再次计算最小生成树。但是虽然节点发生了变动,最小生成树未必全部发生改变,这就造成了不必要的浪费。鉴于此提出一种基于Kruskal算法和Prim算法的最小树更新策略,对Kruskal算法和Prim算法做了改进,使其不必重新计算也能在连通图发生改变时更新最小生成树。     

无线传感器网络最小代价转发算法的恢复问题研究

无线传感器网络的应用已经非常普及,不同的应用需求促进了众多路由算法的研究。本文从传感器节点容易失效这一特点出发,研究最小代价转发路由算法在路由中断后的恢复问题,提出一种能够迅速恢复断裂路径的方法。仿真表明该方法在能够恢复断裂路由的同时拥有较小的资源消耗。     

基于最小生成超树的无线传感器网络路由算法研究

设计能量有效的路由协议以延长网络生存周期,提供健壮可靠的网络服务成为资源有限无线传感器网络研究的核心问题.研究并采用超图理论,将大规模,高连通度的无线传感器网络拓扑抽象为超图模型,从而有效减少网络控制消息.并基于超图模型提出同步无线传感器网络最小生成超树路由算法,以建立数据汇聚的最小能耗树.随后理论证明MSHT-SN算法的正确性和有效性.通过仿真,基于超图模型的MSHT-SN算法较优于基于最短路树策略路由算法,其能够有效的提高数据传输成功率,并节省网络总能耗,延长网络生存周期.     

基于Prim算法的通信网络架设仿真研究与应用

为了更好地提高通信网络架设实际问题的工作效率,进行了通信网络架设过程的仿真研究.通过算法的比较选择,对通信网络构架进行了动态规划.以最小代价生成树普里母算法为研究基础,采用数据结构的分析方法进行假设论证.文中结合通信网络构架的实际具体问题,讨论了网络规划中线路权重的选取方法,并在C语言环境下设计了适用于各个城市网络的节点-支路邻接表的数据存储结构.经实例验证,该方法具有计算速度快的优点并有效减少资源浪费,不仅可以保证通信网络架设工作效率,而且可以有效提高通信网络架设经济效益.     

异构传感器网络代价最小模型

研究了单位面积方形内异构传感器网络,基站从局部地区收集数据代价最小模型。在满足连通性、覆盖性、突然死亡效应条件下,得到最小代价情形下所需两类节点数量和能量参数。证明了环形区域宽度在小于或等于中心圆半径时,环形内簇头节点单位周期能耗随环形区域宽度增加而增加。同时计算出中心圆内需多散布的节点数量。实验结果表明,参数近似解与精确解相比较,结果吻合得很好。     

基于最小路由代价树的大规模显微图像拼接方法

为了对大规模显微图像进行高质量的拼接,首先提出拼接图的概念及获得高质量全景图像的3个原则,然后采用分块-空间聚类算法配准相邻图像,同时评估配准质量,并计算拼接图的边的权值;最后在此基础上,提出了一种基于最小路由代价生成树的图像拼接方法,该方法通过计算拼接图的最小路由代价生成树来确定所有图像的全局位置,并用来生成全景图像。实验结果表明,该方法可获得高质量的全景图像。     

机场噪声监测无线传感网络最小连通覆盖集研究

针对机场噪声监测无线传感网络中的最小连通覆盖集问题,设计了一种基于目标区域Voronoi划分的集中式近似算法,用于分析完全覆盖目标区域所需的最低要求的节点集;为了更好地调整噪声监测节点的感知半径Rs与通信半径Rc的比值关系,在通信半径小于两倍感知半径时,提出了一种基于最小生成树的连通算法用以确保CVT算法构造的覆盖集连通所需的辅助节点。理论分析与仿真实验表明,与现有常用的集中式贪婪算法和DVC算法相比,CVT(+MST)算法的性能在时间复杂性和连通覆盖集大小等两方面都较优。     

“最小代价通信网”案例实现与分析

《数据结构》是一门理论性和逻辑性较强的专业基础课程。而图论算法则是数据结构课程中的重难点部分。文章以"最小代价通信网"案例为例,详细介绍了图论算法通过具体案例学习的具体过程,并对案例的实现过程进行了详细分析,从而说明了案例学习法在数据结构课程中的重要性。通过案例可以更好的掌握算法涉及的理论知识,更全面深刻的理解算法思想。同时通过算法在实际问题中的应用及程序的实现,获得学习的成就感和兴趣。     

一种最小代价组播树的快速算法

本文对KMB算法进行了改进,提出了一种快速的最小代价组播树算法,它只需使用一次PRIM算法,也不需要判断叶结点,从而快速地获得了最小代价组播树,减少了算法的运行时间。随机网络模型的仿真实验表明：该算法的计算时间远小于KMB算法,是一种快速、稳定、高效的算法。     

基于最小代价和生成树的算法研究

最小生成树问题是一类经典的组合优化问题,已有许多快速有效的算法。但是在实际中更多存在这样的网络,除边有权值外,结点也有权值,并且结点的权值有多种情况,这就产生了基于代价和最小的生成树问题。根据结点权值的取值情况,对几种最小代价和生成树问题进行分类和求解,得到了一些有价值的性质和算法,有一定的实际应用背景。     

最小代价前向协议的研究

文章对无线传感器网络的最小代价前向协议进行了研究,在原有协议的基础上引入随机选择、报警机制,并且增加了具有相同代价的相邻节点集。用跳数作为代价分析了改进后的协议性能,并进行计算机仿真,结果表明改进后的协议具有更低的网络负荷和更长的生命周期。     

覆盖组播的最小覆盖代价路由算法

与IP组播相比,覆盖组播通常会消耗更多的底层网络资源。因此,在覆盖网中构造组播转发树时,考虑合理地利用底层网络资源具有一定的实际意义。给出覆盖代价的概念,把覆盖组播路由问题归结为求无向完全图的度和延迟受限、具有最小覆盖代价的生成树问题,求解的目标是在满足应用需求和端用户主机性能要求的同时使所消耗的底层网络资源最少。给出了求解该问题的启发式遗传算法,通过仿真实验验证了该算法的有效性。     

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

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

基于覆盖架构的NCS最小代价调度策略

将覆盖网络引入到基于Internet的网络控制系统（NCS）中,讨论了一种适合于Internet网络控制系统的相近最小代价调度（MLCS）策略,并对其进行了优化。通过仿真系统表明,该基于覆盖网络的调度及其优化策略能有效地保证网络服务质量QoS,从而提高NCS的性能。     

基于最小生成树法的网络充电路线规划模型

无线传感器网络WSN在生活中的应用也越来越广泛,每个传感器都有特定的能量消耗,为了减少移动充电器在路上的能量消耗,基于最小生成树理论建立数学模型研究移动充电器的充电路线.计算出每个传感器和数据中心之间的距离以及传感器与传感器之间的距离,最后经过计算求出路程最短的一条路线即就是能量消耗最少的路线.     

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

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

Ad Hoc网络区域最小覆盖方法研究

覆盖控制作为无线传感器网络中的一个基本问题,反映了网络所能提供的“感知”服务质量,可以使无线传感器网络的空间资源得到优化分配,进而更好地完成环境感知、信息获取和有效传输的任务.如何计算同时满足“覆盖要求”（工作节点必须能够完全覆盖目标区域）和“连通性要求”（工作节点组成的通信网络必须是连通的）的最小节点集合,是一个NP难问题.本文设计了一种基于目标区域Voronoi划分的改进集中式近似算法,用于计算完全覆盖目标区域所需要的近似最小节点集.