ON THE FAULT-TOLERANT ROUTING IN DISTRIBUTED LOOP NETWORKS

Based on their "Theorem 2", an O(δ)-time algorithm of searching for the shortest path between each pair of nodes in a double loop network was proposed by K.Mukhopadyaya, et al.(1995). While, unfortunately, it will be proved that both "Theorem 2" and its proof are in error. A new and more faster O(△)-time, △≤δ, algorithm will be presented in this paper.

运动链基本环路集新的定义及其生成方法

环路是运动链结构的固有特征,已有研究和应用多集中在基于环路的构型综合、同构判定、刚性子链消除等方面。给出了基本环路集的新定义,提出了运动链的树状结构表达及相关理论,以及基于此的基本环路集提取原则,方便快捷地获得各种运动链的基本环路集。案例分析证明,所提方法规则简单,便于计算机程序化实现,可快速地获得结构复杂、对称性高的运动链的基本环路集。通过实例证明了上述理论的正确性和有效性。

双环网D(N,h)的最短路径选择算法

双环网是分布式系统常用的一种拓扑结构。它的寻径问题是人们关心的主要问题之一。本文给出了一个求双环网中任意两个节点间的最短路径算法,此算法所需时间为O(△),其中△是该网络的直径。

双环网络DL(N,h)(h｜N)的最短路径算法

对双环网络ＤＬ（Ｎ，ｈ）（满足最大公因数 ｇ（ Ｎ，ｈ）＝ｈ）进行了分析，证明了这类双环网络中最短路径形式唯一且可用简单的数学表达式来描述，给出了最短路径的公式。在此基础上给出了一个求最短路径的简便算法，讨论了该类网络的直径等有关问题，证明了两点间的平均距离等于直径的一半。

双环网络[+1]边优先最短路径及其寻径策略

双环网络是一种非常重要的互联网络结构 .传统的最优寻径方法没有充分利用这一网络中同一节点到不同节点的最短路径之间的关系 ,所给的算法不是最优的 .定义了双环网络的一种最短路径—— [+ 1]边优先最短路径 ,在此形式下 ,不仅最短路径的形式唯一而且同一源节点到不同目的节点的最短路径之间存在递推关系 .给出了相应的递推公式 ,运用此公式 ,平均不到两次加法运算和一次比较即可找到源节点到所有其它节点的最短路径 .利用所得结果 ,源节点只需存储很少的信息就可以通过简单计算求得到任意其它节点的最短路径 .与传统方法相比 。

一类双环网络的最短路径问题

对双环网络 DL (N ,h) (满足 gcd(N ,h- 1) =h- 1)进行了分析 ,证明了这类双环网络中任意两节点间的最短路径可用简单的数学表达式来描述 ,且当最短路径形式不唯一时 ,给出了所有形式的最短路径的公式。在此基础上给出了一个求最短路径的非常简便的算法。

最短路问题的Floyd改进算法

目前在不含负回路的网络中,对于求解任意两节点之间最短路问题的方法有很多,Floyd算法是最经典的算法之一,但随着节点数量的增加,重复的计算量也随之增大,从而降低了计算效率。为此,文中通过迭代矩阵和下标标注法对Floyd算法进行了改进,改进后的算法既能快速地计算出网络中任意两节点之间的最短路长值,又能更直观地找出最短路径。通过具体实例分析表明,Floyd改进算法减少了重复计算,简化了路径标注方法,提高了计算效率。

有向双环网络G(N;h)的容错路由算法

针对有向双环网络G(N;h)的容错问题,研究了有向双环网络G(N;h)容错节点所对应的等价节点的分布规律,给出一种有向双环网络G(N;h)的容错路由算法.给出了当有向双环网络任意两个节点之间的最短路径出现故障时,找出另一条最短路径的方法.此算法的时间复杂度为O(d).

控制网最小独立闭合环的搜索算法

针对人工和一些商业软件搜索独立闭合环的不准确性及其低效性,本文借助图论知识,提出了一种有效而简便的算法,可以利用计算机自动搜索出所有的独立闭合环。即用无向连通图表示控制网,构建矩阵表示控制网观测边的关系,通过处理变换矩阵使计算机能快速准确搜索到最小独立闭合环;通过实例分析证明此种方法在GPS控制网的可行性,且理论上该方法也能较好地运用于平面网及水准网闭合差中闭合环的的搜索及解算问题,对工程测量中闭合差的求解有一定借鉴作用。

一种应用于路由规划的实用无环K路算法

在对已有第K条最短路算法进行分析和比较的基础上提出了一种新的无环K路算法。该算法基于最短路计算，具有复杂度较低、收敛快以及无环等特点，在路由规划中的应用以及仿真分析都证明本算法是有效、实用的。

基于最短路径的配电网单负荷转移

对多电源供电的配电网进行了分析,给出了基于最短路径理论的合环路径选择模型及有效的算法,该算法充分利用了最短路径的数学理论基础和从经济最优的角度对合环路径进行选择,并用实例证明了这种方法的实用性和可行性。

最短路径的可达矩阵算法

为了提高传统最短路径算法的效率,文中在细致分析传统算法的基础上,提出了一种在业务流程中计算最短路径及寻找不合理活动环的新方法,此方法被称为最短路径的可达矩阵算法.与原有的最短路径算法相比,该方法将可达矩阵的思想引入到最短路径的计算中,可以在矩阵中显示出活动环及活动路径值.文中还详细描述了该方法所涉及的定义及运算规则.最后,将该方法应用于具体实例,并快速地找到了活动环及活动路径,为业务流程再造提供了一种新的解决方案.

关于有向环网平均直径的研究

根据有向双环网络平均直径与其最小路径图(L-型瓦)4个几何参数(a、b、p和q)之间的关系,提供了平均直径的计算公式,并提供了快速计算平均直径的算法。提供了构造有向三环网络的最小路径图(等价树)的新方法,研究了三环网络的任意2点之间的最短路径与等价树的层之间的关系,给出了三环网络平均直径的计算公式和算法。实验结果表明:同一网络的平均直径约为直径的一半;在一个无限族中,直径达到最小值时平均直径不一定为最小值,但平均直径为最小值时直径一定为最小值。研究表明平均直径比直径更能准确地反映环网的传输效率,所以平均直径应成为设计最优网络重要的依据之一。

网孔自动搜索算法在水电仿真中的设计与实现

将电路抽象为图论中的图,在验证了网孔和最小独立闭合环一致性的基础上,把求电路中网孔的问题转化为抽象图中搜索最小独立闭合环的问题;然后以图论中图的广度优先搜索算法为基础,给出了基于广度优先搜索的最小独立闭合环自动搜索算法(BSA)的基本原理和算法描述.实验表明,该算法可以准确高效地搜索出图中所有的最小独立闭合环,算法的运行速度快,占用的空间小,完全可以满足实时性和内存空间的需求.

基于距离可达矩阵识别业务流程中的活动环的新方法

在可达矩阵的基础上,提出了距离可达矩阵识别的新方法.该方法将距离值引入到可达矩阵中,从而可以直接显示出活动间的最短距离并在业务流程中快速地寻找不合理活动环.详细描述了该方法所涉及的定义及运算规则.算例表明该方法能快速方便地找到活动环、活动路径及最短距离,为业务流程再造提供了一种新的解决方案.

基于生成树的控制网最小独立异步环搜索方法研究

实现控制网最小独立异步环的计算机自动搜索是一项较为复杂、繁琐的工作,目前介绍此工作方法的文献大多是阐述过程中的某一部分,并且部分细节问题讨论得较少。文中以帮助初学者对此项工作形成完备的认识并能够自主编程实现为目的,以GNSS控制网为例,详细介绍基于生成树的控制网最小独立异步环自动搜索方法,内容包括生成树的定义及建立方法,最短路径搜索-Dijkstra算法的原理与实现步骤,利用生成树与最短路径搜索算法搜索最小独立闭合环的原理及具体实现步骤,以及同步观测环的自动搜索方法。最后以一个控制网实例说明此方法的可行性。

双环网络的[＋h]边优先寻径策略

提出一种先走[+h]边、当走[+h]边不利时才走[+1]边的[+h]边优先寻径策略;得出[+h]边优先最短路径和双环网络的"竹筏"(一种新L形瓦)型空间解;"竹筏"中节点之间的[+h]边优先最短路径存在递推关系;由节点的[+h]边优先最短路径推出双环网络的直径公式;利用VB6.0和SQLServer2000仿真了[+h]边优先寻径策略;作者曾提出的[+1][+h]双边寻径策略是固定路径,寻找节点,而[+h]边优先寻径策略是固定节点,寻找路径;传统L形瓦难以构造但易求其等价双环网络的直径,而新L形瓦易构造但难以求其等价双环网络的直径;指出了陈忠学文中的几个错误.

Ford算法的改进算法

Ford算法是求解不含负回路网络中从源节点到其余各节点最短路径的经典算法。但每次逼近中,都要计算所有节点的入弧,重复计算量大,降低了计算效率。为此,文中通过引入两个数组和只计算权值变小的节点的所有出弧对Ford算法进行改进,改进后的算法既能快速地计算从源节点到其余各节点的最短路权值,又能更直观地找出最短路径。最后通过具体实例分析和仿真结果表明,改进算法不仅简化了计算量,降低了时间复杂度,而且增强了寻路直观性。

基于层的双环网络G(N;h)的最短路径算法

提出基于层的方法来研究双环网络G(N;h)路由特性;给出基于层的路由策略;给出了双环网络G(N;h)直径等于其树型结构的最大层数的重要结论;研究了双环网络G(N;h)的最短路径问题,给出了0节点到其它任意节点的最短路径算法,并利用面向对象的Java语言实现了这一算法.

有向双环网络最优路由算法

最优路由的研究对于网络节点的传输具有重要意义,但关于有向双环网络节点的最优路由研究,目前尚无统一的算法。现有有向双环网络的最优路由算法,主要集中在单位步长双环网络及一些特殊双环网络上,对于为数较多的非单位步长有向双环网络最优路由的研究较少。已知有向双环网络的MDD图形为L形瓦,基于L形瓦参数设计提出一种通用的有向双环网络最优路由算法。该算法适用于单位步长和非单位步长有向双环网络。仿真结果表明,与基于[+h]边优先路由及基于二叉树的最优路由算法相比,该算法无需建造竹筏及二叉树的空间,执行效率明显提高。