基于优先队列的最小生成树算法

本文提出一个获取连通网络是小生成树的算法。该算法采用一个优先队列组织各顶点集合，每次根据边的权值对队列头集合进行增长。由于对每个顶点的相关联边进行了按权值分级排序的预处理，算法获取具有。个预示e条边的无向连通网络的最小生成树的期望时间是O（e*loglogn）。     

用平衡树实现集合运算的研究之五

研究了两棵平衡树之间的操作,通过两棵平衡树的同时操作,完成两个集合之间的各种运算,如测试集合包含关系(ISSUBSET)、求集合的并(UNION)、求集合的交(INTERSECT)、求集合的差(DEDUCT)、按关键字序列的连接(CONCATENATE)、拆分(SPLIT)、空间压缩(COMPACT)等算法.重要算法给出了时间复杂度证明.这些算法的实现和良好的时间复杂度,说明BT很好地解决了集合的存储和运算工作,解决了"2-3"树完成集合运算的空间利用率低和个别集合操作不相容问题.     

用平衡树实现集合运算的研究之一

从"二元查找树"和"2-3树"实现集合的表示及其完成的集合操作进行分析,提出目前实现集合运算中存在的问题。通过对"2-3树"的改造,形成一种新的数据结构;即平衡树(BT)。BT解决了"2-3树"实现集合表示的存储空间利用率低问题。同时可以实现求集合的并、交、差、测集合包含关系操作。给出平衡树(BT)的结构定义,并对平衡树结点数据的存储结构进行了规定,对BT的性质进行了证明,然后对BT定义了遍历算法,最后给出了用BT实现集合14种操作的过程、函数的定义。     

通信网络架设中最小生成树问题的一种新算法

本文在Prim算法的基础上,结合最优二叉树的思想,提出了一种新的计算方法,将最小生成树的生成过程划分为几个连通子图的最小生成树生成过程,从而显著的提高算法效率。     

逻辑函数化简语义树

提出了一种逻辑函数化简语义树算法，其特点是在求全部本源蕴涵项和从本源蕴函项集合中选取最小覆盖两步中都采用同一算法，因此，算法程序的编写可较为简单，最后，从解题质量和解题速度等方面对该算法进行了评价。     

图的生成树数的计算方法

本文首先概要介绍了网络图论学科中生成树数的常用计算方法。为改进和简化Num(T)=detAA~T的数树公式,笔者提出了用求网图短路导纳矩阵行列式来获得总树数的途径,并用一些实例进行了验证。文末还给出了笔者根据被一些文献称之为最巧妙的算法之一的“Grecdy Alo-gorithm”,编写的搜索全部树的BASIC程序。     

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

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

非线性流水线优化中MAL的一种计算方法

文章介绍一种将含多环有向多重连通图分解为顶点带环且彼此孤立的有向简单图G1和顶点无环的有向多重连通图G2的方法，并在G2上用启发式搜索算法求非线性流水线的最小平均等待时间MAL。     

穿墙雷达中基于最小生成树的建筑物内部结构重构技术

本文旨在通过穿墙雷达图像对建筑物内部结构进行重构,提出了一种利用图理论中的最小生成树(Minimum Spanning Tree,MST)对建筑物结构进行重构的方法.文中基于建筑物内部墙-墙-地板构成的三面角给出了建筑物布局图模型,并定义了节点集合和边集合,随后给出了图当中任意两个节点之间所连边的权重定义.最后,利用MST方法对建筑物内部结构进行重构,仿真结果和暗室测量结果验证了该方法的有效性.     

一种求偶图的所有完备匹配算法

求给定偶图的所有完备匹配问题在LSI/VLSI的布图设计方面有着重要的应用。本文提出了一种求解这一问题的算法。(1)提出了许配树的概念并讨论了其性质;(2)证明了任意一棵许配树T(xi)对应于给定偶图的所有完备匹配的定理;(3)给出了求给定偶图的所有完备匹配的算法。本算法已在BST 386 CAD工作站上用C语言实现。运行结果证明了算法的正确性。算法已作为正在研充的VLSI积木块布图设计系统中的一个模块。     

求解多目标最小生成树的一种改进的非支配排序遗传算法

在改进的非支配排序遗传算法(NSGA-Ⅱ)的基础上,提出了一种基于生成树边集合编码求解多目标最小生成树问题的进化算法。通过快速非支配排序法,降低了算法的计算复杂度,引入保存精英策略,扩大采样空间。实验结果表明:对于多目标最小生成树问题,边集合编码具有较好的遗传性和局部性,而且基于边集合编码的进化算法在求解效率和解的质量方面都优于基于Pr(?)fer编码的进化算法。     

论图的坚韧度(Ⅱ)

连通图G的坚韧度,记作τ(G),定义为τ(G)=min{|S|/ω(G-S);S∈C(G)},其中ω(G-S)表示图G-S的连通分支数,C(G)表示图G中所有点割集构成的集合。本文解决了坚韧度τ(G)=τ的p阶连通图G可能具有的最大边数及相应图构造的方法和步骤。     

一种计算随机流网络可靠性的新算法

提出了一种计算随机流网络可靠性的新方法。通过一定的规则生成网络的状态树，使得每一个分支都是全序集合。在生成状态树的同时搜索每一个分支，对状态采用基于割集的方法进行判断。每个分支上的最小的有效状态就是网络的d-下界点。求得所有的d-下界点，进而求出网络的可靠性。     

N个城市间的最经济的网络建设

N个城市闾有多种的网络建设方案,本文使用最小支撑树的原理,运用算法中的普林算法进行运算。褥到的最小生成树使n个城市闻的连接是连通的,而且是最经济的在各种网络建设方案中。     

通信网中节点重要性的评价方法

提出了一种对通信网中节点重要性进行评价的方法,并给出了简洁的归一化解析表达式。通过比较生成树的数目,可以判断图中任意数目的两组节点的相对重要性。从图中去掉节点以及相关联的链路后,所得到的图对应的生成树数目越少,则表明该组节点越重要。实验结果表明,该方法计算简单,更为精确地反映基于网络拓扑的节点重要性。     

基于空间方向小波等级树的图像编码

本文提出了等级树集合分区算法(SPIHT)的一种改进方案,对图像的小波变换域的三个空间方向(水平、垂直和对角)上的系数构成等级树型结构,并对各空间方向等级树单独进行编码,使得在不影响恢复图像质量的情况下,进一步提高压缩比.仿真实验表明了本算法的有效性.     

基于泛序测试法的逻辑门故障诊断树的自动生成

在逻辑门电路测试技术中,可以在泛序测试法基础上建立故障诊断树,用于完成单电路故障的检测与定位诊断。文章采用最小完全检测测试集和故障表Ｆ＾＊矩阵将故障诊断树为矩阵集合,进而利用关系数据库加以描述,并采用相应的算法自动生成。该研究旨在探索一种用数据库技术自动生成故障诊断树的方法,以达到测试参数自动获取这一目的。     

基于背景位平面向低位位移的ROI压缩算法研究

针对JPEG2000中一般位移法消耗大量的比特数编码形状信息和最大位移法不能控制感兴趣区域(ROI)与背景(BG)区域相对质量的问题,以及经典多级树集合分裂(SPIHT)压缩算法中忽略小波子带兄弟间相关性的缺点,提出了一种应用于ROI压缩编码的BG位平面向低位位移的移位方法,并对SPIHT压缩编码算法的零树结构进行了改进,在解码端即使BG部分未被反向平移,仍能有较好的结果。通过缩小BG幅值及改进零树结构的SPIHT压缩算法的仿真实验表明,该方法实用有效,适用于较大压缩比及低码率传输的情况。     

基于图的邻接点优先的联合树算法的研究与实现

贝叶斯网络是以概率理论为基础的不确定知识表示模型,联合树算法是一种应用广泛的贝叶斯网络推理算法。提出了基于邻接点优先的联合树算法,从图模型和计算效率两个方面对联合树算法（JT）和基于图的邻接点优先的联合树（AD-JT）算法进行推理时间的比较,实验表明：基于图的邻接点优先的联合树算法能够有效地处理大规模数据,极大地减少了消耗时间,计算效率有显著改进。     

利用奇偶树实现测试响应压缩

为了减少利用奇偶树压缩测试响应时的邦联覆盖损失,提出了一种输出端分组压缩的方法。遇敏感邦联对输出端的影响把电路的输出疝集合分成若干子集,依然再把每个子集中的输出连接到各自的奇偶树,构成一个奇偶树集,从而可以实现对偶敏感故障的检测,进而提高对可检测邦联的覆盖。最后,分析了由于奇偶树的引入带来的故障覆盖率的损失及奇偶树中故障的检测。