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.

MINIMUM CONGESTION SPANNING TREES IN BIPARTITE AND RANDOM GRAPHS

The first problem considered in this article reads： is it possible to find upper estimates for the spanning tree congestion in bipartite graphs, which are better than those for general graphs？ It is proved that there exists a bipartite version of the known graph with spanning tree congestion of order n3/2, where n is the number of vertices. The second problem is to estimate spanning tree congestion of random graphs. It is proved that the standard model of random graphs cannot be used to find graphs whose spanning tree congestion has order greater than n3/2.

Brain Functional Network Based on Small-Worldness and Minimum Spanning Tree for Depression Analysis

Since the outbreak and spread of corona virus disease 2019(COVID-19),the prevalence of mental disorders,such as depression,has continued to increase.To explore the abnormal changes of brain functional connections in patients with depression,this paper proposes a depression analysis method based on brain function network(BFN).To avoid the volume conductor effect,BFN was constructed based on phase lag index(PLI).Then the indicators closely related to depression were selected from weighted BFN based on small-worldness(SW)characteristics and binarization BFN based on the minimum spanning tree(MST).Differences analysis between groups and correlation analysis between these indicators and diagnostic indicators were performed in turn.The resting state electroencephalogram(EEG)data of 24 patients with depression and 29 healthy controls(HC)was used to verify our proposed method.The results showed that compared with HC,the information processing of BFN in patients with depression decreased,and BFN showed a trend of randomization.

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)).

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.

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.

On the Minimum Spanning Tree Determined by n Points in the Unit Square

Let P n be a set of n points in the unit square S,l(P n) denoe the length of the minimum spanning tree of P n, andC n= max P nSl(P n), n=2,3,… In this paper,the exact value of C n for n=2,3,4 and the corresponding configurations are given. Additionally,the conjectures of the configuration for n=5,6,7,8,9 are proposed.

Salience adaptive morphological structuring element construction method based on minimum spanning tree

Classical mathematical morphology operations use a fixed size and shape structuring element to process the whole image.Due to the diversity of image content and the complexity of target structure,for processed image,its shape may be changed and part of the information may be lost.Therefore,we propose a method for constructing salience adaptive morphological structuring elements based on minimum spanning tree(MST).First,the gradient image of the input image is calculated,the edge image is obtained by non-maximum suppression(NMS)of the gradient image,and then chamfer distance transformation is performed on the edge image to obtain a salience map(SM).Second,the radius of structuring element is determined by calculating the maximum and minimum values of SM and then the minimum spanning tree is calculated on the SM.Finally,the radius is used to construct a structuring element whose shape and size adaptively change with the local features of the input image.In addition,the basic morphological operators such as erosion,dilation,opening and closing are redefined using the adaptive structuring elements and then compared with the classical morphological operators.The simulation results show that the proposed method can make full use of the local features of the image and has better processing results in image structure preservation and image filtering.

基于最小Spanning树的中继节点部署算法

在能量受限的无线传感器网络(WSNs)中,部署中继节点成为确保通信覆盖的常用方法。提出基于最小Spanning树的中继节点部署算法(MST-DRN)。MST-DRN算法引用基于无线充电的能量模型。再依据节点的能量采集率计算边权值。依据边权值的图模型构建最小Spanning树(MST)。检测MST中不满足生存条件的非支叶节点,在节点附近部署中继节点,维持网络连通。实验数据表明:提出的MST-DRN算法在确保网络连通时,减少了成本(中继节点数),并提高了数据包传递率。

最小生成树的prim算法及minimum函数

本文介绍了最小生成树的prim算法,minimum函数的实现过程及该函数对由prim算法所得到的最小生成树的影响。

Exact Algorithm to Solve the Minimum Cost Multi-Constrained Multicast Routing Problem

The optimal solution of the multi-constrained QoS multicast routing problem is a tree-like hierarchical structure in the topology graph. This multicast route contains a feasible path from the source node to each of the destinations with respect to a set of QoS constraints while minimizing a cost function. Often, it is a tree. In other cases, the hierarchies can return several times to nodes and links of the topology graph. Similarly to Steiner problem, finding such a structure is an NP-hard problem. The usual tree and topology enumeration algorithms applied for the Steiner problem cannot be used to solve the addressed problem. In this paper, we propose an exact algorithm based on the Branch and Bound principle and improved by the Lookahead technique. We show relevant properties of the optimum hierarchy permitting efficient pruning of the search space. To our knowledge, our paper is the first to propose an exact algorithm for this non-trivial multi-constrained optimal multicast route computation. Simulations illustrate the efficiency of the proposed pruning operations. The analysis of the execution time shows that in simple topologies and with tight QoS constraints the exact algorithm requires relatively little execution time. With loose constraints the computation time cannot be tolerated even for off-line route computation. In these cases, the solution is close to a Steiner tree and heuristics can be applied. These results can serve as basis for the design of efficient, polynomial-time routing algorithms.

原油价格不确定性测度及其对宏观经济的非对称影响研究

有效测度原油价格不确定性并研究其对我国宏观经济的影响,具有重要的理论和现实意义。本文基于最小生成树模型,从全局视角衡量原油多元定价机制中195个影响因素的相对重要程度,并采用高维因子非预期条件波动率模型测度国际原油价格的不确定性。基于收敛交叉映射模型,本文对原油价格不确定性与宏观经济间的非线性因果关系进行识别,研究发现仅存在原油价格不确定性对固定资产投资、产出增速的单向因果关系。进一步地,在厘清原油价格不确定性对宏观经济影响机制的基础上,利用包含马尔可夫区制转移特征的向量自回归模型考察原油价格不确定性对我国宏观经济的影响,理论与实证结果均表明原油价格不确定性对我国宏观经济具有显著负向影响;在不同经济状态下,原油价格不确定性对投资、产出增速的影响具有非对称性。本研究为有效防范原油市场风险、保障能源安全和推动经济稳定增长提供了理论支持。

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

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

一种无线传感器网络节能负载平衡树型数据聚合方案

为了延长无线传感器网络的生命周期,并从节点能耗负载均衡的角度进行数据传输,提出了一种高效的基于负载均衡树的数据聚合方案(LB-TBDAS)。该方案将传感区域划分为网格中的多个单元,选出剩余能量最大的传感器节点作为每个单元中的头部单元;利用最小生成树算法建立树状路径。在数据传输过程中,头部单元负责采集每个单元内的传感数据,采集到的数据沿树状路径传输到基站。仿真结果表明,提出的LB-TBDAS方案的总能耗明显低于GB-PEDAP和PED-AP。与GB-PEDAP和PEDAP相比,LB-TBDAS方案延长了一倍以上无线传感器网络的生命周期,可以避免传感器节点在多跳数据传输过程中产生过多的能量消耗。

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.

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

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

基于局部密度峰和标签传播的最小生成树聚类

基于最小生成树(minimum spanning tree,MST)的聚类算法能够识别具有任意形状的簇,该算法在如何有效构建最小生成树和识别无效边方面存在不足,而且易受到噪声点影响.本文利用密度峰值聚类算法思想的优点来寻找局部密度峰,局部密度峰在保留原始数据集分布结构的同时,排除了噪声点,因此,将局部密度峰与最小生成树聚类算法相结合,采用标签传播,提出了基于局部密度峰和标签传播的最小生成树聚类算法(DPMST).该算法采用了局部密度峰之间基于共享邻的距离,利用局部密度峰之间的邻域信息,有效构造最小生成树和识别无效边,使算法能够发现具有复杂结构的簇.标签传播增强强标签,削弱弱标签,以细化错误的标签,特别是对于边界点以及揭示复杂流形,能够提高聚类结果的质量.人工和真实数据集上的实验结果表明,与经典聚类算法DPC、MST、K-means、DBSCAN、AP、SC和BIRCH比较,DPMST算法表现优异.

格式塔原则下的建筑群空间分布智能理解

在格式塔原则下对建筑群进行聚类是计算机理解建筑群空间分布特征并实现地图自动综合的基础.在格式塔原则约束下,首先,利用最小生成树的阈值聚类及参数聚类,实现了对集中和分散均匀排列建筑群空间分布特征的挖掘,并利用C_(v)^(-)值定量评价了挖掘质量;其次,提出了阈值聚类和参数聚类的异同,以及阈值聚类具有局限性的原因;最后,根据建筑物语义特征获得最终聚类结果.试验表明:1)传统的MST阈值聚类不能维持分散均匀排列建筑群的空间分布特征;2)MST参数聚类的适应性要高于阈值聚类,更加符合人类的视觉认知.该方法更有助于提高计算机对建筑群空间分布的智能理解能力.

最小生成树分割下小样本图像纹理提取研究

图像的纹理特征是图像的重要视觉特征,对于小样本图像的纹理特征提取时,存在纹理信息提取精度不佳、纹理信息提取错误等问题,严重影响了图像纹理提取的效果。为了有效解决以上问题,提出最小生成树分割下小样本图像纹理提取方法。采用Shearlet变换和多尺度Retinex方法对小样本图像实行增强处理,以提高其可识别性和区分度。利用最小生成树分割方法,对小样本图像分割处理;通过Gabor滤波器实现小样本图像的纹理提取。实验结果表明,所提方法能够有效地提取出小样本图像的纹理特征,其提取精度在97%以上,且图像增强效果佳。