一种基于的统计的排序算法

本文提出了一种基于统计的快速排序算法，并对该算法的时间复杂度和空间复杂度进行了分析，该算法要求排序关键字满足一定的约束条件，其时间复杂度为O(n)，对该算法做一些简单的修改，还可以将其推广到一般关键字的排序问题。     

基于统计距离的手写数字预处理

数据预处理性能对模式识别系统降低错误率有明显作用。用巴氏距离 (Bhattacharyya distance)来衡量预处理的优劣 ,不需要分类器 ,可对预处理性能预先做出估计。本文提出基于最大巴氏距离的降低噪声规格化预处理 ,错误低、处理速度高、客观性好、简单、有效。对邮政信封直接扫描获得的分辨率为 96× 80的 10 0 0 0个手写体数字样本 ,按照分辨率2 0× 2 0规格化 ,采用正切距离分类 ,其错误率 :不做预处时为14 .5% ,采作本预处理时为 3 .17%。使识别正确率有明显的改善。     

基于子图同构的子电路提取算法

从门级到功能模块级的子电路提取问题在大规模集成电路计算机辅助设计领域有广泛地应用,提出了基于子图同构的方法来解决该问题。针对子电路的特征,选择辐射路匹配和赋标号算法之一作为搜索的主算法。尽管子图同构问题是NP完全问题,算法对实际的电路是快速的,满足工程需要。     

一种基于图同构和单向置换的报文摘要构造算法

为了保护信息的机密性和完整性,该文给出了一种新的报文摘要构造算法,这种新算法是基于图同构的。为了把报文与图联系起来,采用了基于单向置换的报文摘要生成算法,并证明了对该算法而言,不存在多项式时间的概率算法来找到一个“冲突”。最后给出了类似于MD5算法的构造实例。     

具有安全距离和供货距离要求的最优选址

研究了在同时具有安全距离和供货距离的限制条件下,至少要建几个仓库,建在何处,每个仓库各负责为哪些货物需求点提供货物的最优选址问题,建立了该最优选址问题的数学模型,给出了一种使用简便,算法复杂度为[O(n3)]的优化算法。     

基于改进Hausdorff距离的分层景象匹配算法

为克服传统的相似性度量容易受到噪声、遮挡和成像机理等因素影响的缺点,结合人的认知过程,提出了一种分层的模板匹配算法.首先利用了统计指标来对候选匹配区域进行预标记,其次通过对Hausdorff相似性度量的改进来提高其对遮挡、异源图像匹配的鲁棒性.实验结果证明了该方法能够有效地减少搜索区域大小,提高了遮挡情况下的匹配精度,验证了算法的有效性.     

基于关系模型的子图同构检测算法设计与实现

在图分解索引(GDI)算法的基础上,利用关系模型存储图的分解信息,采用B*树对子图结点度进行索引,由此提出一种新的子图同构检测算法——关系图分解索引(RGDI)。实验结果证明,与GDI相比,RGDI可节省更多存储空间,得到的候选集更准确,且子图同构检测效率更高。     

基于距离统计的有序纹理点云离群点检测

三维数据的离群点检测是纹理点云数据处理的重要内容之一，为了有效快速地检测离群点，根据纹理点云的有序结构特征，提出了基于距离统计的检测算法。首先在每个点到其K邻域中其他点距离的基础上计算出K邻域距离；然后根据有序点云中该距离符合正态分布的特点和正态分布3σ定理，将超出3倍方差范围的点认定为离群点。实验结果显示算法采用曼哈顿-最大距离进行检测，当K为4时可以更加快速准确地将有序点云中的离群点检测出来。由此得出，基于距离统计的算法可以有效地将离群点检测出来，同时成功地应用于纹理点云的离群点检测。     

无向网络流的最小费用问题

该文研究了无向网络上,具有流量上限的网络流最小费用问题,建立了它的数学模型,并且给出了相应的算法。     

基于多结点样条磨光函数的几何迭代法

几何迭代法在计算机辅助几何设计(CAGD)中有广泛地应用,为了提高传统的 B-样 条曲线插值在几何迭代中的收敛速度和迭代精度,提出了基于多结点样条磨光函数的几何迭代 法,引入多结点样条磨光函数,在曲线拟合时把多结点样条磨光方法和几何迭代方法结合,经过 磨光和迭代,在 L-BFGS 迭代算法的最优解下构造具有高逼近性的曲线拟合方法。实验结果表明, 在相同精度下,该方法不仅减少了迭代次数,且提高了迭代速度,可以用于飞机、汽车等外形设 计上,亦可用于文物、房屋等外形重构和重建,以及卫星图形图像的处理中。     

简单无向图的同构判定方法

给出了矩阵同构变换、简单无向图距离矩阵、距离矩阵列和向量以及图的距离谱的定义, 将基于邻接矩阵的同构判定条件推广到简单无向图距离矩阵. 针对简单无向连通图的同构判定问题: 给出了基于距离矩阵特征多项式的同构判定条件; 进一步, 为避免计算误差对判定结果的影响, 给出了基于距离矩阵的秩与列和向量的同构判定条件. 上述两个判定条件均是充要条件且均具有多项式时间复杂度.     

图同构中的一类顶点细分方法

提出一种顶点细分方法.基于顶点之间具有一定长度的路径数等信息,定义了一类顶点不变函数.将该方法与已有的一些顶点细分方法进行了比较.分析表明,基于路径数的顶点不变函数的细分效果,至少不差于基于顶点的度、距离等方法;而一些实例则表明前者要优于后者.基于路径数的顶点分类方法可以有效地用于图同构算法,能够降低所需比较的顶点数,达到快速搜索的效果.     

结点可同名的连通无向图的子图研究

给出了求解结点可同名的连通无向图的所有边极大连通子图的算法,并将其应用于化学领域:将许多具有某种共同属性的物质的分子结构图形分解成子分子结构,进一步地试图找出存在于大多数具有该属性的物质中的子分子结构,并讨论这样的子分子结构导致物质具有该共同属性的可能性。     

基于层序遍历的顶点不变量及其图不变量

为了寻找更好性能的图不变量,利用层序遍历过程中的顶点数据经加权累加定义了15 种顶点不变量,每一种顶点不变量排序后可以组成一种图不变量。层序遍历时将顶点度数分为同层度数、向前度数和向后度数,其中同层度数和向后度数包含回路数信息。依据对顶点的细分能力,挑选出3 种顶点不变量,组成图不变量,其不同组合对于各种非同构连通图具有较好的区分性能,不仅对图顶点数N≤8 的非同构图全部可以区分,而且将N=9 的不可区分图数量从文献[9]的989 种降到40 种,且其简并度将趋近2,随机测试表明这些图不变量具有很好的区分度。     

一种基于无向加权图的距离检索和查询方法

在无向加权图上进行距离检索和对象查询是使用无向加权图的重要工作,也是解决实际问题的重要步骤。该文提出一种基于距离签名的处理方法来实现距离检索和查询,通过距离分级、签名编码和压缩等,实现了检索和查询的高效率,减少了存储空间。描述了建模及处理KNN查询的过程,实验证明了该方法的有效性。     

基于攻击距离的攻击图优化方法

传统网络攻击图的生成随着网络规模扩大存在状态爆炸问题,网络安全管理员往往拿着冗余的攻击图不知所措。为了消除攻击图中不必要的攻击路径,保留下最优的攻击路径以供管理员防御参考,本文利用攻击距离对复杂的攻击图进行了优化。实验结果表明,利用此方法优化后的攻击图保留了最有可能的攻击路径,降低了攻击图的规模,随着网络规模的扩大,效果也越来越明显。     

A Heuristic Algorithm of Recognition of Isomorphism of Graphs

A heuristic polynomial algorithm is presented, which is used for the recognition of isomorphism of graphs and can be assigned to the group of methods that use local characteristic invariants of graphs. At each step, the behavior of the algorithm depends on information obtained at its previous steps. All the theorems stated are proved for a class of nonoriented graphs.     

关于图同构复杂性的分析

图同构问题是指对两个图寻找顶点之间的一个一一映射,使得两图的边在该映射下也保持对应关系,该问题得到许多研究者的关注。在一些论文中对图同构问题的复杂性给出了错误的描述,有的给出了多项式时间算法。本文对此进行了讨论,并给出了一些反例来证明其算法的错误。根据图同构国内外目前的研究进展,图同构既未被归入P问题,也未被归入NPC问题,是一个尚未解决的问题,有待进一步研究。     

一种基于无向加权图的距离检索和查询方法

在无向加权图上进行距离检索和对象查询是使用无向加权图的重要工作,也是解决实际问题的重要步骤.该文提出一种基于距离签名的处理方法来实现距离检索和查询,通过距离分级、签名编码和压缩等,实现了检索和查询的高效率,减少了存储空间.描述了建模及处理KNN查询的过程,实验证明了该方法的有效性.     

基于无向图构建策略的主题句抽取

基于文档句构建无向图,将主题句的抽取问题转换为无向图中节点的权重计算问题。首先利用滑窗方法抽取主题词,构建空间向量并生成无向图,然后基于向量空间模型计算边权重,最后利用文档句相似度矩阵的权重模型对文档句权重进行建模与计算,依据压缩比得到文档的主题句。实验表明,该方法在不同的压缩比下生成的摘要质量高,主题句抽取结果接近于人工摘要,召回率和准确率综合指数较高。