基于加权节点的Steiner树启发式算法

Steiner最小树问题是一个NP完全问题,被广泛应用在通信网络中点到多点的路由选择。为了实现更多链路的共享,减少所求Steiner树的费用,提出了一种基于加权节点求解Steiner树的启发式(NWMPH)算法。该算法构造了非正则点的权值公式,给每一个非正则点赋权值,根据权值对链路的费用进行修正,通过修正费用最短路径依次把所有的正则点连接起来,得到包含所有正则点的最小树。对STEINLIB标准数据集中的部分数据进行计算,结果表明: NWMPH算法与MPH算法所用时间基本相同,得到的Steiner树费用优于MPH算法;NWMPH算法比KBMPH算法所用时间少,得到的Steiner树费用绝大多数优于KBMPH算法。     

近红外分析网络共享平台中复杂工作流实现算法

近红外分析共享平台中的采集工作流是一个以数据为中心的工作流。对系统中复杂采集工作流的跳转执行过程进行了详细分析,针对自由工作流跳转造成的数据和状态不一致性的问题,提出了一个任务执行优先关系算法,计算采集工作流中各个活动任务执行次序关系值,并构造一个执行次序关系树,记录各任务活动的状态信息;在流程回退、撤销、跳转时保证了数据和状态的一致性,较好地实现了跨任务活动的跳转。应用结果表明,此算法能够正确高效地实现复杂流程的跳转。     

一种混合的领域概念分类体系自动构建算法

领域概念分类体系自动构建在人工智能、自然语言处理和信息检索等领域具有重要作用,但现有研究较多关注通用知识,面向特定领域的研究较少,且存在领域概念间关系抽取准确率以及自动构建算法效率较低等问题。为此,提出一种混合的领域概念分类体系自动构建算法,该算法主要包括领域概念间关系抽取模块和分类体系构建模块。领域概念间关系抽取模块设计考虑中文自身的特点,采取句法树和基于规则相结合的方法,以提高抽取领域概念间关系的查准率和查全率;分类体系构建模块设计采取改进的BRT算法,从而在降低算法复杂度的同时,提高领域分类体系构建的查准率。在通信、金融和计算机领域的实验结果均表明,与BRT算法相比,该算法的构建效果较好,查准率最高可达到89.3%。     

WSN中一种基于拓扑优化的数据收集方案

针对现有数据收集方法的不足,提出一种优化的网络拓扑构造算法来实现数据收集。该算法首先从给定的网络全连通图中找到符合条件的k个顶点的子图,使得k个顶点间的距离平方和最小化,然后采用Hungarian算法来实现边的约简,直到得到一颗生成树。另外,为了降低控制开销,还提出一种分布式的网络拓扑构造算法,提高算法的适应性。理论分析和仿真实验结果表明,该方法是有效的,在数据收集延迟以及网络生命周期等方面要优于传统的方法。     

一种改进的基于攻击树的木马分析与检测

木马是一种具有潜在威胁的程序,会对计算机造成不同程度危害,对于木马的检测与防范尤为重要。通过分析程序的PE文件提取API函数调用序列,将其分割为长度为k的短序列与攻击树匹配,再对攻击树各节点计算其发生的概率及恶意性权值,最后综合计算攻击树根节点代表事件的危险指数用来估计该程序与木马的相似程度,从而判断程序为木马程序或者包含木马部分的可能性,以准确地检测和防范木马攻击。     

超分辨率扫描成像系统图像无损压缩算法研究

针对光纤耦合的超分辨率扫描成像系统因传输的数据量过大而导致的丢帧现象,引入无损压缩技术对耦合的图像数据进行压缩传输。系统采用可逆的整数小波变换和集合树分裂算法组成的无损压缩方案,并根据耦合成像的特性,对耦合图像进行分割处理,以满足系统对压缩效率的要求。图像的平均压缩比达到了2.3,传输的波特率降到200 Mbps,目前系统提供的256 Mbps的带宽已经完全满足需求。实验结果表明,无损压缩编解码器的引入,降低了光纤耦合系统对传输带宽的要求,并保证了图像的完全重构。     

基于最小生成树相似测度的耳廓匹配

将树匹配引入身份识别,将每只耳廓表示为一棵最小生成树,通过两棵树的相似测度衡量两只耳廓的相似度,以完成耳廓匹配。首先从耳廓点云数据中选取一定数量的关键点;然后分别对两只耳廓的关键点集采用Kmskal算法生成最小生成树,计算两只耳廓匹配产生的3个相似度测量值;最后经过置信加权求和,求出两只耳廓之间的整体相似度,进而完成耳廓匹配。     

中文分词中的正向增字最大匹配算法研究

针对正向最大匹配算法的长词丢失、匹配次数较多、歧义字段处理的准确率较低等问题,基于Trie树词典提出了3种正向增字最大匹配算法,分别使用逐词扫描、尾部折半扫描和尾部减一扫描这3种扫描方式采集歧义字段,并建立了一套歧义处理方法。实验结果表明,该3种算法在分词速度和准确率上均有显著提高,错误率降低到了原算法的三分之一以下。当文本规模大于200 MB时,3种正向增字最大匹配算法的分词速度均比原最大匹配算法提高30%以上。     

逻辑模型树算法性能分析与改进研究

逻辑模型树(LMT)算法是基于树归纳和逻辑回归的一种分类算法。为验证LMT算法的优势,利用3个UCI标准数据集建模,将LMT算法与其他决策树方法进行对比分析。针对LMT算法在建立逻辑回归模型时会导致较高的计算复杂性的问题,研究利用赤池信息量准则改进LMT算法,提升算法时间性能,避免模型过度拟合。在UCI标准数据集和烟叶综合质量评价数据中应用改进的LMT算法进行建模验证,结果表明,该改进方法在模型精度和召回率方面基本优于其他决策树方法,时间性能比改进前提升50%左右,能较好地评价烟叶综合质量。     

旅行商问题中巡回路径的数据结构

旅行商问题中巡回路径的数据结构对局部启发式算法的效率起着非常关键的作用。巡回路径的数据结构必须能够查询一条回路中每个城市的相对顺序,并且能够将一条回路中的部分城市逆序。分析了数组表示法、伸展树表示法和两级树表示法表示巡回路径时各种基本操作的实现过程及时间复杂度。数组表示法能够在常数时间内确定一条回路中每个城市的相对顺序,但是最坏情况下完成逆序操作需要Ω（n）时间,不适用于大规模的旅行商问题。伸展树表示法执行查询和更新操作的平摊时间复杂度是O（logn）,适用于极大规模的旅行商问题。而两级树表示法在最坏情况下每一个更新操作的时间复杂度是O（n^0.5）,适用于大规模的旅行商问题。