混合图在无向图割集生成中的应用

为了进一步提高生成无向图割集的递归收缩算法的执行效率,将无向图转换为一类特殊的混合图,并将转换结果代替无向图输入递归收缩算法进行处理,修改了递归收缩算法中相应的算法步骤,使得改进算法可以更高效地生成无向图的割集.在理论上论证了改进算法的正确性,并通过理论分析和实验比较了改进算法和现有算法的时间复杂度和空间复杂度.理论分析结果和实验比较结果均表明改进算法明显比现有算法高效.     

基于CREW遍历图的一种并行算法

针对串行算法模型下基于顶点遍历图的情况,提出了一种在CREWPRAM并行模型下遍历无向图的算法。该算法是找出无向图的一棵最短路径生成树,由向上和向下两条有向边替换最短路径生成树的每条边形成欧拉回路,运用欧拉回路技术计算前缀和,前缀和所对应的顶点即为遍历无向图的顺序。得出了该算法时间复杂度为O（n＋logn）的结论。     

基于最大信息系数的贝叶斯网络结构学习算法

为了得到正确的节点次序,构造接近最优的贝叶斯网络结构,利用最大信息系数与条件独立性测试相结合的方法,提出了一种新的贝叶斯网络结构学习算法（MICVO）。该算法利用最大信息系数衡量变量之间的依赖关系,生成初始的无向图,引入惩罚因子δ减少图中冗余边的数量,并将这个无向图分解成多个子结构,确定图中边的方向,最后生成正确的节点次序作为K2算法的输入学习网络结构。在两个基准网络Asia和Alarm中进行实验验证,结果表明基于最大信息系数的贝叶斯网络结构学习算法可以得到接近最优的节点次序,学习到的网络结构与数据的拟合程度更好,分类准确性更高。     

寄存器传输级测试用例生成算法

基于控制流图／数据流图层次模型,以分支覆盖、位功能覆盖以及语句可观测覆盖为目标,给出一个高层次测试用例生成算法,并最终实现一种可行的RTL级测试生成算法．实验结果表明,在较少的测试生成时间下,该算法可生成相对短的测试序列,得到与其他方法相当或略差的测试效果．此外,该算法因采用了测试用例技术而具有良好的灵活性．     

平面连杆机构分析与仿真专家系统

任意平面连杆机构，在拓扑组成上，可表示为无向图，本文研究了从机构无向图出发建立机械运动生成链和分离可独立求解杆件组，建立规则库自动按照约束性质生成约束方程式和采遥用变异几何方法数值求解机构运动，本文介绍了一个按上述原理实现的任意连杆机构分析仿真专家系统。     

一种提高3D模型浅浮雕建模质量的方法

顶点数较少的3D模型本身细节不够丰富,浅浮雕建模生成的浮雕效果较差.针对低分辨率3D模型本身细节不够丰富的问题,引入深度学习的方法对3D模型生成的法向图做超分辨率放大,设计出一种基于法向图的超分辨率卷积神经网络,丰富低分辨率法向图的细节,网络的输入是低分辨率3D模型的法向图,输出是高分辨率法向图.实验结果表明:该算法可以有效提升低分辨率法向图的细节,显著提升低分辨率3D模型的浅浮雕建模质量.     

搜索图的全部可能回路的新算法

51．引言如何找出一种简便算法来判断一个图中的所有回路是网络图论学者所关心的重要问题之一，也是计算机网络和操作系统理论所研究的重要课题．对于无向图而言，传统的做法是先找出图的基本回路，然后形成其全部线性组合，再从中删去不是回路的组合．这种算法比较繁琐．本文提出的算法是以图中某一顶点为参考点，找出与该点相关联的边组成的二元组合、三元组合、等等，其中每一个闭组合就是一条回路，从而生成通过参考点的所有回路．输出后再删除该参考点及其关联边，生成退化图．对该退化图，重新进行上述搜索，直至退化图成为空留或度数…     

无向图与有向图的全部生成树的计算机算法

找有向图与无向图的全部生成树的问题,产生于解电网络的问题中。这个问题国外一直在进行研究,已经提出了各种有效的算法。近几年来,国内这方面的研究也在开展。 迄今为止,求无向图与有向图中所有生成树的最好算法是Gabow和Myers在1978年给出的算法(以下简称G-M算法)。本算法(以下称BST算法——即基于子树集的     

基于Prim算法的最小生成树优化研究

在图的最小生成树算法中,Prim和Kruskal算法分别适用于稠密图和稀疏图,但两种算法都不能根据图的顶点数、顶点的度数以及边的分布情况自适应地改变自身.由此,对Prim算法进行改进,从图中每个顶点的度数入手,采取删除某些无用边的思想方法,给出了一个寻找最小生成树的算法,使其能动态调整自身的性能,既适合于稠密图,又适合于稀疏图,经实例验证,利用改进的Prim最小生成树算法,根据无向图的顶点数和顶点的度数动态确定求解最小生成树的时间,并将求解的时间复杂度最小化.     

基于UML时序图的集成测试序列自动生成

该文研究了基于UML时序图的集成测试序列自动生成方法。该方法分析了时序图的语义信息并添加语义约束规约生成可测试模型,从中提取相关信息生成有限状态机;然后使用Wp方法构造测试序列;最后使用中国邮递员算法对Wp方法进行改进生成最优测试序列。该方法生成的测试序列长度相对较短,并能充分满足测试用例覆盖需求。     

故障诊断的发展(续)

三、系统级测试系统级测试的研究对象是多机系统。这个课题的研究虽然早已开始[35],但目前仍处于理论研究,还没有实践性结果。多机系统的各种系统模型都是图的模型。用图G=(V,E)表示系统,V是节点集,表示各单机,E是边集,表示单机间的通讯线,因通讯线都是双向的,故系统图是个无向图。目前的各种算法可归结为有硬核(hardcore)和无硬核两类。在有硬核的算法中,各机要把     

基于事件流图的GUI自动化测试系统的开发

针对目前GUI自动化测试方法中存在着一定程度的手工依赖性以及对测试用例和测试覆盖率缺乏系统管理等问题,本文结合Microsoft UI Automation框架开发了一个基于事件流图的GUI自动化测试系统。该系统先对被测标准GUI进行逆向工程以得到GUI的事件流图和期望的结果,然后分别采用基于蚁群算法的日常冒烟测试用例生成算法和基于宽度优
先搜索的深度回归测试用例生成算法生成测试用例,并用这些生成的测试用例来测试新的GUI。测试结果表明,该GUI自动化测试模型是切实可用的,为在Windows环境下提高GUI测试的自动化程度提供了一种更为有效的途径。     

赋权图上优化问题的DNA计算方法研究

对赋权图上经典优化问题的DNA计算方法进行探讨,改进原有DNA计算模型中的权值编码方法,提出一些新的DNA编码方法及DNA算法．具体地说,通过设计赋权无向图的相对长度图给出了旅行商问题的一种相对长度DNA编码方法及DNA算法,通过设计赋权无向图的广义边图给出了中国邮递员问题的一种广义边图DNA编码方法及DNA算法,通过选取DNA序列的最佳逆补比对给出了最小生成树问题的一种基于逆补比对的DNA编码方法及DNA算法,通过设计从顶点覆盖问题到Hamilton回路问题的一种改进多项式变换给出了顶点覆盖问题的一种基于多项式变换的DNA编码方法及DNA算法．所设计的DNA计算方法提高了DNA计算中表示数值和处理数值的能力．     

两种基于UIO序列的测试序列生成算法及比较

在通信协议一致性测试中,生成测试序列是非常重要的。基于FSM(FiniteStatemachine)的测试序列生成的形式化方法有很多种,其中基于UIO序列(Uniqueinput/outputsequences)的U方法是最常用的。本文主要介绍了两种基于UIO序列的测试序列生成算法,并以TCP协议的FSM图为例,分别应用这两种算法生成了测试序列,进而从错误覆盖度、测试序列的长度、算法复杂度等方面对这两种算法进行了比较研究。     

网络攻击图逆向深度优先生成算法

大规模网络节点数量多,连接关系复杂,现有攻击图生成方法存在节点爆炸问题,针对大规模网络的这种特点,提出了一种逆向深度优先攻击图生成算法。首先对攻击图的相关概念进行了简要介绍,并分析了逆向生成算法流程。然后,鉴于生成攻击图过程中要对网络可达性进行测试,因此,同时提出了基于区间树的规则匹配算法,最后,对攻击图生成算法进行了实际环境测试,并对测试结果进行了验证分析。实验结果表明,该攻击图生成算法能以O（lgn）的时间复杂度高效检测网络可达性,优化网络攻击图生成结果。     

用图的着色方法求解考试时间安排问题

无向图的m着色问题已被证明为NP-难度问题,若已知图由带权值的团所构成,可用m种颜色对该图进行着色.给出了一种能在多项式时间内进行的新算法,可得到一个可接受的方案.此算法改善了求解的时间复杂度,通过一个考试时间安排的实例说明了本算法的可行性、实用性和优越性.     

基于量子进化算法的时序电路测试生成

本文介绍将量子进化算法应用在时序电路测试生成的研究结果。结合时序电路的特点，本文将量子计算中的量子位和叠加态的概念引入传统的测试生成算法中，建立了时序电路的量子进化算法测试生成模型。在国际标准电路上的验证结果表明，与同类算法相比，该算法模型可获得较高的故障覆盖率和较小的测试矢量集。     

对数空间可构造的无向图遍历序列

研究了为无向连通子图设计环状遍历序列（TSC）的空间复杂性问题。通过定义对数空间的Cook归约,分析了TSC问题与无向图连接性问题及通用遍历序列构造问题的关系,证明了TSC问题以及无向图遍历问题是对数空间可解的,并给出了一个TSC一般性构造方法。最后还提出了一个更有效的针对树状图的TSC构造算法。     

新的二部图判定算法

二部图是现代图论中一类非常重要的图,然而关于其判定的充要条件却很少,而且用算法实现它们很复杂.需要指数级的时间代价.利用图的广度优先遍历,提出了一个易于实现的二部图判定的充要条件:无向图G是二部图当且仅当G的广度优先生成森林中的同一层上的任意两点在G中不邻接.给出了该判定条件的实现算法,算法的时间复杂度是O(n2),很好地解决了二部图的判定问题.     

Power图的离散生成

Power图是一种特殊的加权Voronoi图，该图中每个生成元点pi都带有权值wi．给出了一种直接构造Power图的算法．以每个生成元点Pi为圆心，Power距离,√wi为半径画圆；然后将这些圆以不同颜色填充，并以相同速率向外扩展这些圆的边界，直到屏幕上所有像素点都涂上颜色为止，环绕Pi的新边界构成Power图．该算法改进了在Voronoi图基础上构造Power图的传统方法，具有较高的效率．