赋权有向图最小生成树的表上作业法

每一赋权有向图可用一个赋权表来表示。本文在借助于赋权表而不是赋权有向图本身讨论圈和生成树的基础上,给出了一种求解赋权有向图最小生成树的新方法——表上作业法,证明了方法的最优性。该方法简单易行,借助于计算机Ｓｐｒｅａｄｓｈｅｅｔ软件,如ＭｉｃｒｏｓｏｆｔＥｘｃｅｌ,可很方便地进行大规模复杂问题的求解。     

A Table Based Algorithm for Minimum Directed Spanning Trees

1. INTRODUCTIONSeveral optimal spanning tree methods have been developed for the weighted undirected graph. The commonlyused methods are Kruskal's method (also called Greedy algorithm) and Disorder algorithm [4]. As for theweighted digraph, little work has been done [1]. In practice, the complicated digraph is difficult to be depicted,but easy to be expressed in the form of a table. Based on the table expression instead of the digraph expression,an optimal spanning rooted-tree method cal…     

Table Operation Method for Optimal Spanning Tree Problem

1.INTRODUCTIONSeveraloptimalspanningtreemethodshavebeendevelopedfortheweightundirectedgraph.ThecommonlyusedmethodsareKruskal'sMethod[4](alsocalledGreedyAlgoritlun)andDisorderAlgorithm[4j.Asfortheweightdigraph,littleworkhasbeendone.Inthepractice,thecomplicateddigraphisdifficulttodepict,butitiseasytobeexpressedintheformofatable.Basedoilthetableexpressioninsteadofthedigraphexpression,thispaperdevelopsanoptimalspanningrooted-treemethodcalledtableoperationsmethod(TOM).2.SOMEBASICCONCE…     

网络中的最优控制树问题

众所周知,从通讯网络建设中提出著名的最优支撑树问题,即在一个赋权连通图中求一个包含所有顶点而权(费用)最小的连通子图(支撑树).进而,在交通、通讯、供销系统的干线设计中,考虑的连线(干线)不一定连接网络的所有顶点,但被连接的顶点必须构成一个控制集,即其余任一顶点都有一条边直接与此主干部分相连.这就提出了最优控制树问题.似乎此问题与最优支撑树问题十分类似,但我们将证明它是NP-困难的,并给出一个分枝定界算法及相关性质.     

启发式交叉求解TSP问题的混合遗传算法

在给出度约束最小生成树的快速生成方法的基础上，设计了一种启发式交叉求解TSP问题的混合遗传算法．该算法在交叉操作的设计上，与其他遗传算法有本质的不同，该交叉操作是在不违反度约束和不形成圈的前提下，每次从父代基因所拥有的边中加入权最小的边，从而形成子代．利用该算法得到了TSP CHN144问题迄今为止最好的解．     

ON THE INVERSE MINIMUM SPANNING TREE PROBLEM WITH MINIMUM NUMBER OF PERTURBED EDGES

Let G=be a network with the vertex set V,the edge set E and the length vector L, andlet T~* be a prior determined spanning tree of G. The inverse minimum spanning tree problem withminimum number of perturbed edges is to perturb the length vector L to L+δ, such that T~* is one ofminimum spanning trees under the length vector L+δ and the number of perturbed edges is minimum.This paper establishes a mathematical model for this problem and transforms it into a minimumvertex covering problem in a bipartite graph G_0, a path-graph. Thus a strongly polynomial algorithmwith time complexity O(mn~2) can be designed by using Hungarian method.     

求解度约束最小生成树的快速近似算法

针对带有度约束的最小生成树问题,给出了一种快速近似算法.首先给出了快速近似算法的核心思想:在不违反度约束和不形成圈的前提下,每次加入权最小的边.其次给出了实现快速近似算法的具体步骤,并且证明了该算法的计算时间复杂度是图的顶点数的多项式函数,证明了算法的有效性定理.大量的数值试验表明该近似算法性能良好.最后在此算法的基础上,给出了求解TSP问题的一种快速近似算法.     

度限制最小树的蚂蚁算法

针对度限制最小树问题,给出了一种基于蚂蚁系统思想的求解方法,经大量数据测试和验证,并与其它算法相比较,得到了较好的结果以及一系列意义的结论。     

The Application of Spanning Tree Algorithm in Arabic Language Rules for Contextual Analysis

ＴｈｅＡｐｐｌｉｃａｔｉｏｎｏｆＳｐａｎｎｉｎｇＴｒｅｅＡｌｇｏｒｉｔｈｍｉｎＡｒａｂｉｃＬａｎｇｕａｇｅＲｕｌｅｓｆｏｒＣｏｎｔｅｘｔｕａｌＡｎａｌｙｓｉｓ￥ＢＩＡＮＦｕｐｉｎｇ；ＭＥＮＧＦａｎｚｈｅｎ；ＨＯＵＷｅｎｈｕａ（Ｄｅｐａｒｔｍｅｎｔｏｆ...     

广义最小生成树的遗传算法求解及应用

介绍了最小生成树的概念,分析了最小生成树在实际应用中的局限性。引入了节点的度的定义,据此提出了广义最小生成树的概念。采用遗传算法来求解最小生成树,并针对普通遗传算法求解该问题的不足,提出了自调整的变异算子和限制父代个体数目的混合选择策略。通过一个有线电视网络的建模与仿真,表明了广义最小生成树模型的适用性。分别采用普通遗传算法和改进后的遗传算法进行求解,并将结果进行比较,证明了改进后的遗传算法的有效性。     

求解度限制最小生成树问题的启发式遗传搜索算法

CM（1,1）模型一般以模型还原值与实际值平均相对误差检验模型的模拟精度。本文以模型还原值与实际值平均相对误差最小化为目标函数将CM（1,1）模型转化成一个不用进行灰微分方程参数辨识的优化模型，称之为改进的GM（1,1）模型，简称IGM（1,1）。IGM（1,1）避开了灰微分方程参数辨识时传统的优化无法求解，本文针对IGM（1,1）模型的直接建模。由于IGM（1,1）目标函数非连续，不可导，用传统的优化无法求解，本文针对IGM（1,1）模型的模拟特性设计了求解该优化模型的遗传算法并进行了算例验证，秋解结果表明了IGM（1,1）模型IGM（1,1）模型。     

Algorithms for degree-constrained Euclidean Steiner minimal tree

A new problem of degree-constrained Euclidean Steiner minimal tree is discussed, which is quite useful in several fields. Although it is slightly different from the traditional degree-constrained minimal spanning tree, it is also NP-hard. Two intelligent algorithms are proposed in an attempt to solve this difficult problem. Series of numerical examples are tested, which demonstrate that the algorithms also work well in practice.     

Algorithms for degree-constrained Euclidean Steiner minimal tree

A new problem of degree-constrained Euclidean Steiner minimal tree is discussed,which is quite useful in several fields.Although it is slightly different from the traditional degree-constrained minimal spanning tree,it is aho NP-hard.Two intelligent algorithms are proposed in an attempt to solve this difficult problem.Series of numerical examples are tested,which demonstrate that the algorithms also work well in practice.     

基于最小生成树与概率松弛结合的谱匹配算法

提出了一种基于最小生成树与概率松弛结合的谱匹配算法。该算法分别对给定的两个待匹配的特征点集构建最小生成树,通过最小生成树构造Laplace矩阵,由奇异值分解该矩阵得到的特征值和特征向量,计算出特征点匹配的初始概率,利用概率松弛迭代法,获得最终匹配结果。用大量的真实序列图像进行比较实验,结果验证了该算法的有效性和准确性。     

度约束最小生成树(DCMST)的竞争决策算法

度约束最小生成树是网络设计和优化中的一个NP难题，介绍了一种基于竞争造就优化和决策左右结果的新型算法——竞争决策算法，利用竞争决策算法的通用模型，给出了一种基于竞争决策思想求解度约束最小生成树的快速求解方法，经过数据测试和验证，并与其它算法的结果进行了比较，得到了较好的结果．     

严格第k最小支撑树问题

提出了严格第 k最小树的概念 .利用定长支撑树问题的复杂性 ,证明了求支撑树的长度分布L( G)问题是 NP-C的 ,从而证明了严格第 k最小支撑树问题也是 NP-C的 .对于 k=2的情况 ,给出了一个多项式时间算法 ,其时间复杂性为 $O( | EX| n^2 )$ ,其中 EX是正交换的集合 ,n是顶点数.     

一种基于最小张树的属性聚类算法

结合图论中的最小张树方法 ,提出了相似度以及接触度两个概念 ,并以此为基础建立了一种属性聚类算法 .文中就几个具体问题 ,将其与 FCM及 AKM等方法进行比较 ,以便分析其聚类效果 .很明显 ,我们所介绍的方法弥补了其它方法的一些不足 ,并能在一定程度上解决实际问题.     

Mean-variance model based on filters of minimum spanning tree

This study aims to reduce the statistical uncertainty of the correlation coefficient matrix in the mean-variance model of Markowitz. A filtering algorithm based on minimum spanning tree (MST) is proposed. Daily data of the 30 stocks of the Hang Seng Index (HSI) and Dow Jones Index (DJI) from 2004 to 2009 are selected as the base dataset. The proposed algorithm is compared with the Markowitz method in terms of risk, reliability, and effective size of the portfolio. Results show that (1) although the predicted risk of portfolio built with the MST is slightly higher than that of Markowitz, the realized risk of MST filtering algorithm is much smaller; and (2) the reliability and the effective size of filtering algorithm based on MST is apparently better than that of the Markowitz portfolio. Therefore, conclusion is that filtering algorithm based on MST improves the mean-variance model of Markowitz.     

无线传感器网络中多移动代理分组优化算法

在基于多移动代理的无线传感器网络中,源节点的编组方法是区别于单移动代理系统的核心研究问题。基于跳数的最小生成树原理,提出一种基于最小生成树算法的规划编组方式,通过对无向全连通图中边权值的测量和选取,简单而有效地控制网络中能量消耗与任务延迟间的平衡,从而获得高效的综合性能。最后通过大量的OPNET仿真实验验证了算法的可靠性。

Abstract：

In contrary to the single mobile agent system,the grouping methodology for source nodes is the key issue in multi-agent itinerary planning for wireless sensor networks.A novel approach was proposed based on hop-oriented minimum spanning tree.The scheme achieves flexible trade-off control between energy cost and task duration by dynamically selecting edge weights in the total connected graph.Extensive simulations have shown that the approach outperforms the existing works.     

求解度约束最小生成树的单亲遗传算法

提出了求解度约束最小生成树问题的单亲遗传算法.该算法首先利用Prufer数对生成树进行编码;然后精心地设计了一个随机地产生初始种群的方法,用这种方法产生的初始种群,不会含有任何不可行解;在遗传操作中只使用选择和变异操作,共设计了三种变异操作,其中两种变异操作均不会产生不可行解,只有一种变异操作可能会产生不可行解,需要作树的度的检查和修改;这样就大大的降低了不可行解产生的机会,从而提高了遗传算法的效率;而且只使用变异算子,有效的避免了早熟收敛现象的产生;通过大量的数值试验,表明该算法简单,高效,收敛率高;最后对此算法做了适当推广,并给出了它求解TSP问题的具体步骤和实例。