基于邻接表分解自相交折线的算法设计

寻求能快速、高效分解自相交折线的算法是计算机做二维图形所必须面对的问题。虽然邻接衷和单链表的指针部分耗用了一定量的内存,但在删除、插入等操作上实现了快速、高效,因此非常适合解决这个问题。文中算法的时间复杂度和空间复杂度均达到预期目标,并在实际的应用中确实满足了快速、高效等性能要求。     

谱流形快速学习算法研究

谱流形学习算法的目标是发现嵌入在高维数据空间中的低维表示,其近年来得到了广泛的应用。虽然已经取得了许多令人骄傲的成绩,但是却存在一个很大的瓶颈--计算复杂度太高,这严重阻碍了算法在实际中的应用。提出了谱流形快速学习算法,该算法包括两个降低算法复杂度的技术：（1）通过随机选择或者k-means方法从n个样本点中选出 p个锚点,把每个样本点表达为由锚点的邻域点线性组合的形式,从而设计了邻接矩阵的新形式,降低了邻接图的计算复杂度;（2）利用线性化的流形学习算法有效地计算高维数据到低维数据的映射,从而降低了优化特征值的计算复杂度。该算法在3个常用人脸数据集（Yale、ORL、Extended Yale B）上得到了验证,进一步证明了算法的有效性。     

有向图的谱半径的一个Sharp上界

利用矩阵理论,给出了简单有向图的谱半径可达上界和强连通有向图的谱半径上界.     

建立数字高程模型的多边形区域法

针对利用等高线地形图建立数字高程模型(DEM)时传统方法需先提取离散点数据、构建大量不规则三角形网(TIN)的繁琐过程，提出简便的多边形区域法.对等高线进行完整性处理并按多边形编号存储，利用既有的等高线及其单边邻接关系将整个地形图划分为相互独立的多边形区域,形成DEM模型；通过搜索查询点所在的多边形区域及对应的等高线高程值，采用距离加权平均法计算查询点的高程.该方法建立的DEM模型明显减少了网格数量和存储空间，高程插值计算精度不低于TIN法.利用多边形区域替代传统的TIN，建模效率提高,适合于建立大型的DEM.     

基于极大团和FP-Tree的挖掘关联规则的改进算法

融合了关联规则挖掘的FP-Tree算法和图论的极大团理论的优势,做了以下主要工作:(1) 提出了用邻接矩阵的产生频繁2-项集的改进方法;(2) 提出了极大有序频繁集的概念,证明了Head关系的等价性、划分定理、局部复杂性定理和归并收敛值域定理;(3) 提出并实现了基于极大团划分的MaxCFPTree算法,扫描时间复杂性小于O(n²);(4) 做了相关实验,以验证算法的正确性.新方法缓解了项目数量巨大而内存不足的矛盾,提高了系统效率和伸缩性.     

一种判定图中Hamilton圈的邻接边增长算法

一个图是否为Hamilton图在于图中是否有Hamilton圈。文中提出了变换的方法来寻找图中的Hamilton圈，即在图的顶点集中寻找满足包含给定图中所有顶点的自归邻接边增长变换的方法来寻找给定图中的Hamilton圈。由此，设计了一个在Edmonds意义下的有效算法——自归邻接边增长算法(AEG)来寻找给定图中的自归邻接边增长变换，证明了该算法能正确判断给定简单无向图中有无Hamilton圈且时间复杂度为O(n^2)。最后通过应用实例说明该算法的有效性和实用性。     

A workflow net similarity measure based on transition adjacency relations

Many activities in business process management, such as process retrieval, process mining, and process integration, need to determine the similarity or the distance between two processes. Although several approaches have recently been proposed to measure the similarity between business processes, neither the definitions of the similarity notion between processes nor the measure methods have gained wide recognition. In this paper, we define the similarity and the distance based on firing sequences in the context of workflow nets (WF-nets) as the unified reference concepts. However, to many WF-nets, either the number of full firing sequences or the length of a single firing sequence is infinite. Since transition adjacency relations (TARs) can be seen as the genes of the firing sequences which describe transition orders appearing in all possible firing sequences, we propose a practical similarity definition based on the TAR sets of two processes. It is formally shown that the corresponding distance measure between processes is a metric. An algorithm using model reduction techniques for the efficient computation of the measure is also presented. Experimental results involving comparison of different measures on artificial processes and evaluations on clustering real-life processes validate our approach.     

基于改进区域邻接图的遥感图像多尺度快速分割方法

提出一种针对高分辨率遥感图像的多尺度快速分割方法,首先利用直接分水岭分割得到初始分割结果,而后构建改进的区域邻接图,并在其基础上通过较为快速的区域合并策略得到最终分割结果。合并准则为相邻区域间的特征向量差,合并过程中通过设置区域允许最大标准差和区域允许最大面积两个尺度控制参数以生成不同尺度的分割结果。以QuickBird卫星图像进行实验,通过监督评价以及与eCognition软件进行比较,结果表明本文分割方法在精度和效率方面均效果较好,具备实际应用的潜力。     

基于电力电子变换器邻接表的潜电路分析方法

潜电路分析(SCA)是保障电路系统可靠性的重要方法.本文通过研究电力电子变换器电路结构,提出了一种基于电力电子变换器邻接表模型的潜电路分析方法.该方法通过搜索变换器邻接表得到所有的电路模态,然后根据线索表去除冗余的和正常工作的电路模态,从而得到所有的潜在电路模态.最后以四阶升压谐振开关电容变换器潜电路分析为例,验证了所提出方法和设计软件的正确性.     

基于图的最短路径跨域数据交换实现

最短路径查找的效率决定了跨域数据交换的效率。针对通道较少（e〈n（n-1））的跨域数据交换最短路径查找的问题,文中实现了一种基于图的最短路径查找方法。设计了域标识模型、域表和通道表,建立了域表与通道表的关系模型,根据面向对象的方法基于邻接表存储结构构造了域及通道的邻接表。基于深度优先搜索遍历原理,定义邻接表对象、路径集合,记录域访问历史、路径长度,以递归的方式实现了跨域最短路径的查找。实现了电子政务跨域数据交换时域间最短路径的查找,证实了文中方法的有效性。