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

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

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

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

基于LEACH的簇树网络路由算法研究

分簇算法是目前无线传感器网络(WSN)研究的重点之一;在对LEACH算法(低功耗自适应聚类路由算法)进行研究分析的基础之上,针对LEACH算法中簇头节点与基站(BS)之间单跳通信能耗较大的问题,采用连通网络中最小生成树的Prim算法,提出了一种簇树网络路由算法;该算法使得簇头节点间通信代价耗费降低,仿真结果说明了该算法的可行性和有效性。     

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

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

逼近最优的更新最小生成树的并行算法

给定连通无向赋值图G=(V,E),|V|=n,|E|=m,当G的某边的赋值改变时,必引起其最小生成树的改变。本文给出了一个快速有效地求新的最小生成树的并行算法,时间为O(log m),处理器个数为O(m~(1/2)),计算模型为EREW-PRAM。预处理也仅需O(log~2m)时间O(m)个处理器,与求初始最小生成树的耗费一样。我们的算法的并行时间与处理四个数的乘积为O(m~(1/2) log m)(此问题已知最快的串行算法时间为O(m~(1/2)))。     

基于降阶的最小生成树快速算法*

在分析最小生成树问题数学性质的基础上,给出了一种基于降阶技术的快速最小生成树算法。该算法采用降阶技术,大大加快了算法的求解速度,在最坏情况下算法的时间复杂度为O(m);另一方面,算法易于找到问题的全部最小生成树。     

构造最小生成树的量子算法

图的最小生成树问题是网络优化中的一类基本问题。目前构造最小生成树的算法都是基于传统计算机的算法如Prim算法和Kruskal算法。该文提出了一个用于构造图的最小生成树的量子算法,它结合量子搜索的方法和经典Kruskal算法的思想,对于n个节点m条边的图,依次搜索出n-1条边使它们构成一棵最小生成树。这一算法的时间复杂性为O(nm√)。与经典Kruskal算法相比,在同等条件下,该文的算法有较快的加速。     

求解度约束最小生成树问题的新算法

针对网络设计和组合优化中的度约束最小生成树问题,基于第k最小生成树的求解算法,提出了一种求解网络G关于指定节点的最小k度生成树的新算法。该算法通过对网络G的最小生成树作最优可行变换,逐步构造出指定节点的度数越来越接近度约束k的最小i度生成树,最终得到了网络G关于指定节点的最小k度生成树。给出了算法实施的具体步骤,并证明了算法的正确性。最后通过仿真结果和一个运输实例,表明了该算法在解决度约束最小生成树问题中的有效性。     

基于剪枝的最小生成树算法在供水管网的应用

在进行供水管网网络设计时,如何使铺设的供水管网线路最短,构建的供水管网造价最低是设计者需要重点考虑的问题之一。文章就此问题提出了一种基于剪枝的最小生成树算法。算法首先将交叉点(街道的交汇处)和节点(用户)都视为图的顶点,然后求出最小生成树,最后再将最小生成树中以交叉点为末梢的枝叶剪掉。该算法简洁、快速、易于实现。对铺设公路,架设网线等一类网络问题也有实际的参考意义。     

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

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