Solving the Euclidean Steiner Minimum Tree Using Cellular Stochastic Diffusion Search Algorithm

The Euclidean Steiner minimum tree problem is a classical NP-hard combinatorial optimization problem.Because of the intrinsic characteristic of the hard computability,this problem cannot be solved accurately by efficient algorithms up to now.Due to the extensive applications in real world,it is quite important to find some heuristics for it.The stochastic diffusion search algorithm is a newly population-based algorithm whose operating mechanism is quite different from ordinary intelligent algorithms,so this algorithm has its own advantage in solving some optimization problems.This paper has carefully studied the stochastic diffusion search algorithm and designed a cellular automata stochastic diffusion search algorithm for the Euclidean Steiner minimum tree problem which has low time complexity.Practical results show that the proposed algorithm can find approving results in short time even for the large scale size,while exact algorithms need to cost several hours.

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.

Minimum Dominating Tree Problem for Graphs

A dominating tree T of a graph G is a subtree of G which contains at least one neighbor of each vertex of G.The minimum dominating tree problem is to find a dominating tree of G with minimum number of vertices,which is an NP-hard problem.This paper studies some polynomially solvable cases,including interval graphs,Halin graphs,special outer-planar graphs and others.

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

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.

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.

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.

MINIMUM ATTRIBUTE CO-REDUCTION ALGORITHM BASED ON MULTILEVEL EVOLUTIONARY TREE WITH SELF-ADAPTIVE SUBPOPULATIONS

Attribute reduction is an important process in rough set theory.Finding minimum attribute reduction has been proven to help the user-oriented make better knowledge discovery in some cases.In this paper,an efficient minimum attribute reduction algorithm is proposed based on the multilevel evolutionary tree with self-adaptive subpopulations.A model of multilevel evolutionary tree with self-adaptive subpopulations is constructed,and interacting attribute sets are better decomposed into subsets by the self-adaptive mechanism of elitist populations.Moreover it can self-adapt the subpopulation sizes according to the historical performance record so that interacting attribute decision variables are captured into the same grouped subpopulation,which will be extended to better performance in both quality of solution and competitive computation complexity for minimum attribute reduction.The conducted experiments show the proposed algorithm is better on both efficiency and accuracy of minimum attribute reduction than some representative algorithms.Finally the proposed algorithm is applied to magnetic resonance image(MRI)segmentation,and its stronger applicability is further demonstrated by the effective and robust segmentation results.

基于R-Tree的高效异常轨迹检测算法

提出了异常轨迹检测算法,通过检测轨迹的局部异常程度来判断两条轨迹是否全局匹配,进而检测异常轨迹.算法要点如下:(1)为了有效地表示轨迹的局部特征,以k个连续轨迹点作为基本比较单元,提出一种计算两个基本比较单元间不匹配程度的距离函数,并在此基础上定义了局部匹配、全局匹配和异常轨迹的概念;(2)针对异常轨迹检测算法普遍存在计算代价高的不足,提出了一种基于R-Tree的异常轨迹检测算法,其优势在于利用R-Tree和轨迹间的距离特征矩阵找出所有可能匹配的基本比较单元对,然后再通过计算距离确定其是否局部匹配,从而消除大量不必要的距离计算.实验结果表明,该算法不仅具有很好的效率,而且检测出来的异常轨迹也具有实际意义.

基于FP-Tree的最大频繁项目集更新挖掘算法

发现最大频繁项目集是多种数据挖掘应用中的重要问题 .在应用中用户需要调整最小支持度 ,以发现更有用的最大频繁项目集 .为此提出了一种最大频繁项目集更新算法 (UMFPA) ,该算法通过对频繁模式树(FP Tree)中的频繁项目头表 (HTable)增加两个域 ,从而将减少在数据库不变而最小支持度变化的情况下的更新挖掘最大频繁项目集的费用 .实验结果表明 。

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

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

基于R^＊-tree的散乱点云截面数据获取算法

为快速准确地获取散乱点云的截面数据,以较少数据准确表达模型信息,提出一种截面数据获取算法.采用R*-tree建立点云的动态空间索引结构,基于该结构快速准确获取截面邻域数据,依据该数据与截平面的位置关系将邻域数据分为正负两个邻域,通过对两邻域数据点配对连线与截平面求交获取截面数据,并采用最小生成树算法对其排序,最终得到有序的截面数据.结果表明,该算法数据适应性强,截面数据获取精度高,运行速度快,且能够以较少数据准确表达模型型面特征.

基于FP-Tree的最大频繁项目集综合更新算法

挖掘最大频繁项目集是多种数据挖掘应用中的关键问题,其挖掘过程的高花费要求对高效更新算法进行深入研究。为此,我们在改进频繁模式树(FP-Tree)的基础上提出了处理最小支持度和数据库都发生变化时的最大频繁项目集更新算法FUMFIA(Fast Updating Maximal Frequent Itemsets Algorithm)。通过对实验结果的分析可以看出,该算法在进行更新挖掘时具有很好的时空效率。

基于FC-tree的频繁闭项目集挖掘算法

目前提出的频繁项目集挖掘算法大多基于Apriori算法思想,但这类算法会产生巨大的候选集并且重复扫描数据库。本文针对这一问题,给出了一种基于FC-tree的频繁闭项目集挖掘算法Max-FCIA,该算法将频繁项目集存储在哈希表中,节省了程序的搜索时间。此外,利用广度优先搜索和有效的剪枝策略,大大限制了候选项目集的生成,缩小了搜索空间从而提高了程序的性能。实验结果表明该算法是快速有效的。

MTree_Nix网络模拟路由策略的研究与优化

路由策略是影响网络模拟规模与性能的一个关键因素。MTree_Nix路由策略是目前网络模拟中综合性能较优的路由策略之一。分析了MTree_Nix路由策略在覆盖率计算以及路由信息预计算方面的缺陷,提出采用端到端的方式进行路由计算存储,并采用阈值与步数相结合的方法来稳定并提高最小生成树覆盖率。实验结果表明,改进后的MTree_Nix路由策略与改进之前相比,存储空间减少了约2%,路由预计算时间减少了约98%,模拟运行时间减少了约38%。

ZigBee网络中Cluster-Tree拓扑的改进与优化

无线传感器网络(WSN)是一种具有感测、计算和传输能力的小型传感器节点的集合。由于单个传感器节点的功能有限,特别是能量的存储和数据的存储,所以需要制定良好的网络拓扑结构和路由协议。文中重点研究基于IEEE 802.15.4标准的Zig Bee无线传感器网络,提出基于最小生成树(MST)的高效聚类拓扑结构MSCT,最终的目的在于以最小的成本构建一个网络拓扑结构。文中的拓扑结构还考虑了室内环境,提出了处理墙壁和障碍物导致的路径损耗和信号衰减的度量,并计算节点之间的链接的权重。最后,通过能量的损耗和网络的寿命来论证文中提出的MSCT拓扑结构比Cluster-Tree拓扑结构更具有优势性。

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

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