蚂蚁算法建立度限制树在聚类中的应用

针对聚类算法解决大规模数据时间复杂度和空间复杂度都很大的问题，给出了应用蚂蚁算法建立度限制树．同时结合密度思想来解决这一问题的算法．经过数据的测试和验证，得到了较好的结果和一系列有意义的结论．     

基于用户及物品间差异的推荐算法研究

推荐系统是解决信息过载问题最有效的工具之一,协同过滤是目前推荐算法中广泛应用的技术,然而协同过滤算法存在着诸如数据稀疏、难以扩展等问题.在基于偏好算法的基础上,通过把用户评分按照用户评分偏好和物品得分趋势分类,在每类上进行线性回归,得到了基于用户及物品间差异的回归模型.该模型不仅能改善数据稀疏和可扩展性问题,而且能够降低计算复杂度和空间复杂度.实验结果表明改进后的算法在近似的计算复杂度情况下,预测精度比基于偏好算法平均提高了3.97%.     

元皇后问题回溯算法改进

回溯算法是解决N元皇后问题最有效的算法之一.在传统回溯算法的基础上,采用动态规划的思想,对算法进行了改进,改进后的算法大大降低了求解的复杂度和比较次数.文章还给出了改进算法的实现并通过理论分析和实验数据证明了算法的可行性.     

中继网络中基于能量效率的动态用户接入算法

为了解决中继网络中基于能量效率的用户接入问题,将用户数据需求严格受限下基于能量效率最优的动态用户接入问题建模为一个整数优化问题,该问题类似于一个NP-hard的多维背包问题.首先,采用穷搜法分析了该问题最优解的复杂度.然后,提出了一种低复杂度、高效的基于能量效率的动态用户接入算法(UAEEM).该算法在保证用户数据需求严格受限的前提下,按照系统射频端和电路端的能量效率最大原则,动态调整用户归属和中继的工作状态,以实现网络能量效率最大化.最后,通过仿真实验验证所提算法性能.结果表明,UAEEM算法能显著提高系统的能量效率、降低系统的计算复杂度,且其性能接近最优解.     

动态规划算法的时间效率改进

分析了影响动态规划算法时间复杂度的3个因素,分别从3个方面给出了改进动态规划算法时间复杂度的优化措施,从理论上分析了优化方法的有效性和正确性.与传统算法相比,优化后的算法时间复杂度有一定程度的提高,能够适用于数据规模更大的问题.     

基于最小规则自组织映射的入侵检测算法

为了解决入侵检测模型中海量数据处理问题,降低计算复杂度,提高检测精度,提出基于最小规则自组织映射的入侵检测算法;通过在真实的入侵检测数据集上进行仿真实验,将该算法与普通椭圆补丁算法、简单矩形补丁算法以及决策树算法进行对比.结果表明,该算法在检测精度、稳定性和计算时间方面优于对比算法,验证了该算法的有效性.     

基于社团密合度的复杂网络社团发现算法

传统的社团发现算法大多存在划分效果和复杂度相矛盾的问题,为了解决该问题,提出一种新的单社团结构评价标准——社团密合度(group density).在此基础上,设计了一种基于凝聚思想的社团发现算法,该算法通过不断融合小社团,使网络的社团结构向平均社团密合度最大的方向发展,并使用模块度检测算法的划分结果.通过与经典的GN,Fast Newman,LPA等算法对多个数据集进行实验对比,验证了本文算法在获得较好的划分效果的同时具有较低的时间复杂度.     

基于Fisher判别的分布式K-Means聚类算法

为了解决集中式聚类算法不能处理海量大数据的问题,提出基于Fisher判别确定置信半径的分布式聚类算法.应用网络上各个节点的计算、存储能力,以及网络的带宽,将聚类所需的时间复杂度和空间复杂度平摊到各个节点.通过应用Fisher线性判别找到节点在同一子类数据上的稠密和稀疏分布,从而快速确定聚类的置信半径并指导下一步的聚类过程,使得保持聚类精度的同时能提高分布式聚类的速度.对算法进行了数值模拟,并使用真实数据完成了试验.结果表明,所提出算法相比DFEKM聚类算法,能根据数据分布的不同在聚类结果和聚类速度上达到很好的平衡,这表明该算法具有更好的健壮性.     

VMA-OFDM系统中多频偏和信道联合MLE算法

针对虚拟多天线正交频分复用(VMA-OFDM)系统目的节点中数据辅助的多频偏和信道参数估计问题进行了研究,设计了一种次优最大似然估计(MLE)算法.该算法在矩阵的求逆中采用了级数展开,从而使得算法的复杂度与基于最大似然准则估计算法相比显著减小,在算法的性能和复杂度之间进行折衷,解决了最大似然估计算法过于复杂而难以实现的问题.在算法的性能方面,理论分析和仿真结果表明,基于该算法的频偏和信道参数估计的均方误差逼近Cramer-Rao下界(CRB);在算法的效率方面,该算法允许各个中继节点同时发送训练序列,从而降低传输训练序列所占用的时间.     

基于PMF进行潜在特征因子分解的标签推荐

现有社会标签推荐技术存在数据稀疏、时间复杂度高以及可解释性低等问题,鉴于此,提出基于概率矩阵分解(PMF)进行潜在特征因子联合分解的标签推荐算法(TagRec-UPMF),它结合用户、资源及标签3方面的潜在特征,联合构建对应的概率形式的潜在特征向量,然后根据它们两两之间的特征向量内积进行线性组合,从而产生Top-N推荐.该算法解决了数据规模大且稀疏情况下的精度问题,算法的线性复杂度使得其可用于大规模数据.实验结果表明,相比于TagRec-CF,PITF,TTD,Tucker,NMF等算法,本文算法既提高了推荐的准确率,又降低了时间损耗.与PITF算法相比较,准确率得到了提高,而处理时间相差不明显;与TTD算法相比较,在准确率相差不明显的情况下,大大降低了时间损耗.因此,本文的TagRec-UPMF算法相比其他算法表现出了一定的优势.     

基于量化相对约简格的分类规则发现

分类是数据挖掘中的一个重要问题．概念格通过概念的内涵和外延及泛化和例化之间的关系来表示知识,因而适用于从数据库中挖掘规则的问题描述．在量化的相对约简格基础上,提出一种新的分类规则发现算法,该算法的生成结果剔除了冗余的分类规则,算法在时间性能、空间性能等方面均有较大的提高．     

EHWSNs中面向吞吐量和能耗优化的时隙分配算法研究

针对在具有移动汇聚结点(Sink)的能量收集无线传感器网络中,如何在数据收集时提升网络吞吐量和降低能耗的问题,分析了Sink移动距离与节点数据传输的时间周期之间的关系,将面向吞吐量和能耗优化的数据收集问题建模为基于混合整数线性规划的优化问题,并提出了一种基于有效传输周期的时隙分配算法来对其进行求解。算法主要分2个阶段进行：移动Sink在每个时间周期内识别出可进行数据传输的邻居节点,并为其分配时隙;移动Sink根据数据可用性对节点进行排序,并最终决定哪些节点在各个时隙期间发送数据。理论分析和仿真实验结果表明,所提算法在吞吐量和能耗方面的性能优于当前典型算法,且计算复杂度更低。     

A TCAM-based Two-dimensional Prefix Packet Classification Algorithm

Packet classification (PC) has become the main method to support the quality of service and security of network application. And two-dimeusioual prefix packet classification (PPC) is the popular one. This paper analyzes the problem of ruler conflict, and then presents a TCAM-based two-dimensional PPC algorithm. This algorithm makes use of the parallelism of TCAM to lookup the longest prefix in one instruction cycle. Then it uses a memory image and associated data structures to eliminate the conflicts between rulers, and performs a fast two-dimeusional PPC. Compared with other algorithms, this algorithm has the least time complexity and less space complexity.     

对最大团问题的HEWN算法分析

对最大团问题的HEWN(hierarchicaledge-weightnetwork)算法进行了复杂性分析.首先通过分析HEWN的结构特点和所需进行的操作,设计了一种实现HEWN算法的数据结构,指出了在HEWN算法中HEWN的存储宜采用邻接多重表和二叉链表相结合的链表表示法,然后从HEWN的存储结构入手,剖析了HEWN的构造过程,在剖析过程中,通过与MCST(maximumcompletesub-graphtree)比较,指出了当2j>n时潜在的、指数的生成和修改GM的次数存在于HEWN算法中.因而,HEWN算法的时间复杂度是指数的,而不是O(n8.5).     

求二元关系传递闭包的新方法

二元关系的闭包运算在网络、语法分析以及开关电路中的故障检测和诊断等领域有着重要的作用 .通过求二元关系各幂的并获得关系闭包方法后来被认为是十分困难的和甚为繁琐的 .在三十多年前 ,War Shall给出了一种算法 ,使问题得以简便解决 .但是该算法存在着大量不必要的重复计算 .本文就此做了改进 .改进的算法比 War Shall的算法在时间复杂度从 O( n3)上能够降低到 O( n2 )     

度、半径约束最小生成树问题及其算法

提出了度、半径约束最小生成树问题,证明了该问题是NP-完全的.建立了该问题的数学规划模型.进一步给出了快速启发式求解算法,并分析了该算法的时间复杂性.分析和实例实验表明该算法具有良好的效果.     

机动目标空间群生成算法

提出了一种机动目标的空间群生成算法,该算法的思想是定义空间群目标间的多种特征相似度,通过一级融合获得的信息,计算目标多种特征相似度矩阵并融合求得合群结果。该方法用特征相似度空间属性计算代替了测量空间的目标属性计算,提高了可靠性。该算法的时间复杂度仅为O(n2)。仿真实验表明,该算法具有较高的合群效率,结果可信。     

柔性流水作业排序问题的贪心算法求解

柔性流水作业排序问题是一类复杂的车间作业调度问题。针对通常情况下调度问题求解困难的问题,给出了求解柔性流水作业排序问题近似解的贪心算法,并对其性能进行了分析测试。结果表明,虽然该贪心算法求出的近似解与最优解相比有一定误差,但由于其时间复杂度较小,因此对求解车间作业调度问题仍有一定的现实意义。     

基于动态时间的个性化推荐模型

在推荐系统中,往往会存在数据的非实时性、稀疏性和冷启动性等问题,文中通过引入遗忘曲线来跟踪用户对资源偏好程度随时间变化情况,利用提出一种改进的K-Means聚类算法对用户集进行聚类,根据改进的个性化推荐算法对用户进行推荐,建立了一种基于动态时间的个性化推荐模型. 通过实验验证,文中提出的个性化推荐模型能够获取准确的用户偏好信息,并缓解冷启动问题,降低算法计算的时间空间复杂度,提高个性化推荐算法的推荐质量.     

Active XML Document Rewriting Based on Tree Automata Theory

The problem of document rewriting is a fundamental problem in active XML（AXML） data exchange and usually has a higher complexity. Prior work was focused on string automaton theory. This paper tries to solve it by using tree automaton. More precisely, the paper firstly defines a new tree automaton, active XML tree automaton （AXTA）, which can efficiently represent the set of AXML documents produced by an AXML document or AXML document schema. And then, an algorithm for constructing AXTA automaton is also proposed. Finally, a polynomial time（PTIME） determining algorithm for AXML document rewriting is presented based on AXTA automaton.