A NEW ALGORITHM FOR ALL EFFICIENT SPANNING TREES

In Corley′s algorithm for all efficient spanning trees, final solutions include many spanning trees, which are not all efficient. In this paper, a new algorithm is presented, which corrects and modifies Corley′s algorithm. A necessary condition is developed for the subtree of an efficient spanning tree. According to the condition the new algorithm is established and its efficiency is proved.

High-resolution Remote Sensing Image Segmentation Using Minimum Spanning Tree Tessellation and RHMRF-FCM Algorithm

It is proposed a high resolution remote sensing image segmentation method which combines static minimum spanning tree(MST)tessellation considering shape information and the RHMRF-FCM algorithm.It solves the problems in the traditional pixel-based HMRF-FCM algorithm in which poor noise resistance and low precision segmentation in a complex boundary exist.By using the MST model and shape information,the object boundary and geometrical noise can be expressed and reduced respectively.Firstly,the static MST tessellation is employed for dividing the image domain into some sub-regions corresponding to the components of homogeneous regions needed to be segmented.Secondly,based on the tessellation results,the RHMRF model is built,and regulation terms considering the KL information and the information entropy are introduced into the FCM objective function.Finally,the partial differential method and Lagrange function are employed to calculate the parameters of the fuzzy objective function for obtaining the global optimal segmentation results.To verify the robustness and effectiveness of the proposed algorithm,the experiments are carried out with WorldView-3(WV-3)high resolution image.The results from proposed method with different parameters and comparing methods(multi-resolution method and watershed segmentation method in eCognition software)are analyzed qualitatively and quantitatively.

THE DESIGN AND ANALYSIS OF ALGORITHM OF MINIMUM COST SPANNING TREE

This paper provides a method of producing a minimum cost spanning tree (MCST) using set operations. It studies the data structure for implementation of set operations and the algorithm to be applied to this structure and proves the correctness and the complexity of the algorithm. This algorithm uses the FDG (formula to divide elements into groups) to sort (the FDG sorts a sequence of n elements in expected tir O(n)) and uses the method of path compression to find and to unite. Therefore. n produces an MCST of an undirected network having n vertices and e edges in expected time O(eG(n)).

A Novel Binary Firefly Algorithm for the Minimum Labeling Spanning Tree Problem

Given a connected undirected graph G whose edges are labeled,the minimumlabeling spanning tree(MLST)problemis to find a spanning tree of G with the smallest number of different labels.TheMLST is anNP-hard combinatorial optimization problem,which is widely applied in communication networks,multimodal transportation networks,and data compression.Some approximation algorithms and heuristics algorithms have been proposed for the problem.Firefly algorithm is a new meta-heuristic algorithm.Because of its simplicity and easy implementation,it has been successfully applied in various fields.However,the basic firefly algorithm is not suitable for discrete problems.To this end,a novel discrete firefly algorithm for the MLST problem is proposed in this paper.A binary operation method to update firefly positions and a local feasible handling method are introduced,which correct unfeasible solutions,eliminate redundant labels,and make the algorithm more suitable for discrete problems.Computational results show that the algorithm has good performance.The algorithm can be extended to solve other discrete optimization problems.

An Optimal Parallel Algorithm for Constructing a Spanning Tree on Proper Circle Trapezoid Graphs

Given a simple graph G with n vertices and m edges, the spanning tree problem is to find a spanning tree for a given graph G. This problem has many applications, such as electric power systems, computer network design and circuit analysis. For a simple graph, the spanning tree problem can be solved in O(log n) time with O(m+n) processors on the CRCW PRAM. In general, it is known that more efficient parallel algorithms can be developed by restricting classes of graphs. In this paper, we shall propose a parallel algorithm which runs O(log n) time with O(n/log n) processors on the EREW PRAM for constructing on proper circle trapezoid graphs.

The Design of the Minimum Spanning Tree Algorithms

Based on the graphic theory and improved genetic algorithm,an improved genetic algorithm to search the minimum spanning trees is given . The algorithm uses binary code to represent the problem of minimum spanning trees. It designs the corresponding fitness function,operator and few controlling strategies to improve its speed and evolutionary efficiency.Only one solution can be gotten with running traditional al-gorithem atone time.The new algorithm can get a set of the solutions with higher probability in a shorter time.The experiment shows that it has a better performance than traditional methods.

SOLVING MINIMUM SPANNING TREE PROBLEM WITH DNA COMPUTING

Molecular programming is applied to minimum spanning problem whose solution requires encoding of real values in DNA strands. A new encoding scheme is proposed for real values that is biologically plausible and has a fixed code length. According to the characteristics of the problem, a DNA algorithm solving the minimum spanning tree problem is given. The effectiveness of the proposed method is verified by simulation. The advantages and disadvantages of this algorithm are discussed.

NeuroPrim:An attention-based model for solving NP-hard spanning tree problems

Spanning tree problems with specialized constraints can be difficult to solve in real-world scenarios,often requiring intricate algorithmic design and exponential time.Recently,there has been growing interest in end-to-end deep neural networks for solving routing problems.However,such methods typically produce sequences of vertices,which make it difficult to apply them to general combinatorial optimization problems where the solution set consists of edges,as in various spanning tree problems.In this paper,we propose NeuroPrim,a novel framework for solving various spanning tree problems by defining a Markov decision process for general combinatorial optimization problems on graphs.Our approach reduces the action and state space using Prim's algorithm and trains the resulting model using REINFORCE.We apply our framework to three difficult problems on the Euclidean space:the degree-constrained minimum spanning tree problem,the minimum routing cost spanning tree problem and the Steiner tree problem in graphs.Experimental results on literature instances demonstrate that our model outperforms strong heuristics and achieves small optimality gaps of up to 250 vertices.Additionally,we find that our model has strong generalization ability with no significant degradation observed on problem instances as large as 1,000.Our results suggest that our framework can be effective for solving a wide range of combinatorial optimization problems beyond spanning tree problems.

The Minimum Centroid Branch Spanning Tree Problem

For a spanning tree T of graph G,the centroid of T is a vertex v for which the largest component of T-v has as few vertices as possible.The number of vertices of this component is called the centroid branch weight of T.The minimum centroid branch spanning tree problem is to find a spanning tree T of G such that the centroid branch weight is minimized.In application to design of communication networks,the loads of all branches leading from the switch center should be as balanced as possible.In this paper,we prove that the problem is strongly NP-hard even for bipartite graphs.Moreover,the problem is shown to be polynomially solvable for split graphs,and exact formulae for special graph familis,say Kn_(1),n_(2),...,n_(k)and P_(m)×P_(n),are presented.

融合均值榜样的反向互学习水母搜索算法

为解决水母搜索算法(jellyfish search algorithm,JS)的洋流运动缺乏多样性、群内运动缺乏引导性、种群间信息无交流,造成搜索速度慢、稳定性差及易早熟的问题,构建了一种融合均值榜样的反向互学习水母搜索算法(oppositional-mutual learning jellyfish search algorithm based on mean-value example,OMLJS).首先在水母跟随洋流运动(全局搜索)部分,利用前两代水母的平均位置代替只考虑上一代水母的平均位置来引导水母个体的位置更新,提高算法的全局搜索能力;其次在水母的群内主动运动(局部搜索)部分,利用最优个体代替随机个体来引导水母进行更有效的搜索,加快算法的收敛速度;然后在水母进入下一次迭代前增加对水母种群进行动态反向互学习步骤,增加种群多样性及增强种群间的信息交流,达到互补另外两个策略,提高算法的整体优化性能.选用12个经典的基准测试优化函数,将OMLJS与5个对比算法从解的平均值、最优值及方差进行对比分析,并用于求解最小生成树问题,OMLJS能够更快地找到最小生成树.实验结果表明,OMLJS的收敛速度、求解精度明显提高.

增广立方体上边独立生成树的并行构造

近年来,围绕互连网络的研究工作越来越多。其中独立生成树(Independent Spanning Trees,ISTs)可以应用于信息的可靠传输、并行传输、安全分发以及故障服务器的并行诊断中,因此受到了许多研究者的关注。在一对多广播、可靠通信、多节点广播、容错广播、安全消息分发、IP快速重路由等网络通信中,边独立生成树(Edge-Independent Spanning Trees,EISTs)发挥着重要作用。n维增广立方体AQ_(n)是n维超立方体Q_(n)的节点对称变型,它具有超立方体及其变型所没有的一些可嵌入性质。然而,目前增广立方体上边独立生成树的构造方法都是串行构造的。文中首先提出了一种并行算法,用于构造以AQ_(n)中的任意节点为根的2n-1棵树。然后证明算法得到的2n-1棵树是高度为n的边独立生成树,算法的时间复杂度为O(N),其中N表示增广立方体中的节点数。最后通过模拟实验来验证了所提方法的准确性。

基于改进Prim算法的路径规划研究

文中提出一种基于聚类分析改进Prim(普里姆)最小生成树的路径规划算法,采用二分法将站网中的站点先聚类,分成多个微小的站点聚类中心,再以各聚类中心进行Prim最小生成树的路径规划,量化站网空间分布特征,通过聚类增强最小生成树,达到路径优化的目的。实践结果证明,改进的Prim算法适用于大型稠密的站网,在稠密的连通图中,只要调整指数进而控制聚类中心的数量,就能简化站网布局,降低算法的空间复杂度,达到更好的实际应用。

Approximation Algorithms for Solving the 1-Line Minimum Steiner Tree of Line Segments Problem

We address the 1-line minimum Steiner tree of line segments(1L-MStT-LS)problem.Specifically,given a set S of n disjoint line segments in R^(2),we are asked to find the location of a line l and a set E_(l) of necessary line segments(i.e.,edges)such that a graph consisting of all line segments in S ∪ E_(l) plus this line l,denoted by T_(l)=(S,l,E_(l)),becomes a Steiner tree,the objective is to minimize total length of edges in E_(l) among all such Steiner trees.Similarly,we are asked to find a set E_(0) of necessary edges such that a graph consisting of all line segments in S ∪ E_(0),denoted by T_(S)=(S,E_(0)),becomes a Steiner tree,the objective is to minimize total length of edges in E_(0) among all such Steiner trees,we refer to this new problem as the minimum Steiner tree of line segments(MStT-LS)problem.In addition,when two endpoints of each edge in Eo need to be located on two different line segments in S,respectively,we refer to that problem as the minimum spanning tree of line segments(MST-LS)problem.We obtain three main results:(1)Using technique of Voronoi diagram of line segments,we design an exact algorithm in time O(n log n)to solve the MST-LS problem;(2)we show that the algorithm designed in(1)is a 1.214-approximation algorithm to solve the MStT-LS problem;(3)using the combination of the algorithm designed in(1)as a subroutine for many times,a technique of finding linear facility location and a key lemma proved by techniques of computational geometry,we present a 1.214-approximation algorithm in time O(n^(3) log n)to solve the 1L-MStT-LS problem.

基于遗传的海上风电集电系统拓扑优化

针对海上风电工程集电线路拓扑的自动优化布置,文章以集电线路的全寿命周期成本作为目标函数,海缆选型和海缆交叉规避作为主要约束条件,建立数学模型,同时基于动态边权最小生成树算法改进遗传算法的种群生成方式以扩大算法的搜索解空间,以期凭借较好的寻优能力求解集电系统拓扑优化问题,提升海上风电场的综合效益。海上风电场项目算例结果验证了方法的有效性和快速性,可为海上风电集电系统规划设计提供具有实用价值的参考。

多无人机覆盖路径算法的设计

为了解决在野外和受灾地区中多无人机路径规划后任务负载不平衡问题提出一种基于覆盖路径生成算法STC和生成树覆盖算法的负载平衡多无人机覆盖路径算法,基于STC算法优化路径分区过程设计平衡切割算法迭代的优化路径分区负载权值,解决了多无人机在完成目标区域覆盖时工作负载不均的问题,通过对比仿真实验验证了方法的可行性。结果表明,此算法可以在有限资源限制条件下找到多无人机最优路径分区并有效平衡多无人机负载。

A-STC: auction-based spanning tree coverage algorithm for motion planning of cooperative robots

The multi-robot coverage motion planning(MCMP) problem in which every reachable area must be covered is common in multi-robot systems. To deal with the MCMP problem, we propose an efficient, complete, and off-line algorithm, named the "auction-based spanning tree coverage(A-STC)" algorithm. First, the configuration space is divided into mega cells whose size is twice the minimum coverage range of a robot. Based on connection relationships among mega cells, a graph structure can be obtained. A robot that circumnavigates a spanning tree of the graph can generate a coverage trajectory. Then, the proposed algorithm adopts an auction mechanism to construct one spanning tree for each robot. In this mechanism, an auctioneer robot chooses a suitable vertex of the graph as an auction item from neighboring vertexes of its spanning tree by heuristic rules. A bidder robot submits a proper bid to the auctioneer according to the auction vertexes' relationships with the spanning tree of the robot and the estimated length of its trajectory. The estimated length is calculated based on vertexes and edges in the spanning tree. The bidder with the highest bid is selected as a winner to reduce the makespan of the coverage task. After auction processes, acceptable coverage trajectories can be planned rapidly. Computational experiments validate the effectiveness of the proposed MCMP algorithm and the method for estimating trajectory lengths. The proposed algorithm is also compared with the state-of-the-art algorithms. The comparative results show that the A-STC algorithm has apparent advantages in terms of the running time and the makespan for large crowded configuration spaces.

A Gene-Pool Based Genetic Algorithm for TSP

Based on the analysis of previous genetic algorithms (GAs) for TSP, a novel method called Ge- GA is proposed. It combines gene pool and GA so as to direct the evolution of the whole population. The core of Ge- GA is the construction of gene pool and how to apply it to GA. Different from standard GAs, Ge- GA aims to enhance the ability of exploration and exploitation by incorporating global search with local search. On one hand a local search called Ge- Lo-calSearch operator is proposed to improve the solution quality, on the other hand the modified Inver-Over operator called Ge InverOver is considered as a global search mechanism to expand solution space of local minimal. Both of these operators are based on the gene pool. Our algorithm is applied to 11 well-known traveling salesman problems whose numbers of cities are from 70 to 1577 cities. The experiments results indicate that Ge- GA has great robustness for TSP. For each test instance, the average value of solution quality, found in accepted time, stays within 0. 001% from the optimum.

A novel genetic algorithm based on all spanning trees of undirected graph for distribution network reconfiguration

Network reconfiguration is of theoretical and practical significance to guarantee safe and economical operation of distribution system.In this paper,based on all spanning trees of undirected graph,a novel genetic algorithm for electric distribution network reconfiguration is proposed.Above all,all spanning trees of simplified graph of distribution network are found.Tie branches are obtained with spanning tree subtracted from simplified graph.There is one and only one switch open on each tie branch.Decimal identity number of open switch on each tie branch is taken as the optimization variable.Therefore,the length of chromosome is very short.Each spanning tree corresponds to one subpopulation.Gene operations of each subpopulation are implemented with parallel computing method.Individuals of offspring after gene operation automatically meet with radial and connected constraints for distribution network operation.Disadvantages of conventional genetic algorithm for network reconfiguration that a large amount of unfeasible solutions are created after crossover and mutation,which result in very low searching efficiency,are completely overcome.High calculation speed and superior capability of the proposed method are validated by two test cases.

Efficient Minimum Spanning Tree Algorithms on the Reconfigurable Mesh

The reconfigurable mesh consists of an array of processors interconnected by a reconfigurable bus system. The bus system can be used to dynamically obtain various interconnection patterns among the processors. Recently, this model has attracted a lot of attention. In this paper, two efficient algorithms are proposed for computing the minimum spanning tree of an n-vertex undirected graph. One runs on an n×n reconfigurable mesh with time complexity of O(log^2 n). The other runs with time complexity of O(log n) on an n^(1+E)×n reconfigurable mesh, where < E < 1 is a constant. All these improve the previously known results on the reconfigurable mesh.

Gradient Gene Algorithm: a Fast Optimization Method to MST Problem

The extension of Minimum Spanning Tree(MST) problem is an NP hard problem which does not exit a polynomial time algorithm. In this paper, a fast optimization method on MST problem——the Gradient Gene Algorithm is introduced. Compared with other evolutionary algorithms on MST problem, it is more advanced: firstly, very simple and easy to realize; then, efficient and accurate; finally general on other combination optimization problems.