正则化的近似最大公因子的图像盲复原算法

针对近似最大公因子图像盲复原算法对噪声敏感的问题,提出了一种基于全变分正则化的近似最大公因子图像盲复原算法。该算法利用近似最大公因子盲复原算法估算出点扩散函数,然后利用全变分正则化迭代解卷积求得复原图像。改进算法从抑制噪声和反卷积运算约束两个方面去改进近似最大公因子图像盲复原算法,提高算法的鲁棒性。最后给出仿真实验,在同一噪声水平下改进算法的PSNR提高了1～5dB,SSIM提高了0.09～0.3,验证了改进算法有较好的效果。     

线性划分问题的一个改进算法

给定一个由n个非负数构成的序列X={x1, x2, …, xn}及正整数k≤n, 线性划分问题要求将该序列划分为不大于k段子序列,使得最小化各段子序列元素之和为最大值。目前已知该问题的最好算法是时间复杂度为O(kn2)和空间复杂度为O(kn)的动态规划算法。利用非负数序列的性质,给出一个快速改进算法,其时间复杂度为O(knlogn),空间复杂度为O(n)。     

基于神经网络的最短路算法及其应用

提出一种基于递归神经网络的最短路算法,降低了神经元之间的连接复杂度,能稳定收敛到准最优解。并将其应用于基于流量的动态分布式路由。仿真表明,该处上敛稳定。     

基于模拟退火聚类的室内定位算法

针对大型室内场景下现有指纹定位算法运算复杂度高、定位精度低的问题,提出一种基于模拟退火聚类的室内定位算法。该算法采用模拟退火聚类的方法完成对指纹空间的聚类和划分,有效降低了指纹匹配所需的候选指纹数量,并消除了具有一定特征相似性的奇异点,从而降低了运算复杂度,提高了定位精度。实验结果表明,该算法可计算出定位环境下指纹空间的最优聚类数从而确保定位精度,较K 均值聚类定位算法和KNN算法定位精度高,且定位精度不受初始值影响。     

关于丢番图方程 x2p+2kyp=z2

设A、B、C是两两互素的正整数,m,n,r是大于1的正整数，对于丢番图方程Ax^m+Byⁿ=Cz^r，(x,y,z)=1，1/m+1/n+1/r＜1，1989年,Tijdeman猜想：该方程仅有有限多组整数解(x,y,z)；1997年，Andrew Bal猜想：如果A=B=C=1,m,n,r均大于2，则该方程没有正整数解.关于上述猜想，本文作者获得了如下结果：设p为奇素数，证明了丢番图方程x^2p+2^ky^p=z²,(x,y)=1，k≥1，y≠0仅有整数解k=3,｜x｜=y=1,｜z｜=3和k=2pl+3,｜x｜=2l,y=1,｜z｜=3·2^pl .从而更正了王云葵关于上述方程所获得的结果.     

前N条最短路径问题的算法及应用

现有最短路径问题指的是狭义最短路径问题，针对该问题而设计的算法只能求得最短的一条路径。前N条最短路径拓宽了最短路径问题的内涵（即不仅要求得最短路径，还要求得次短、再次短…第N短路径），是广义最短路径问题，在图论理论基础上分析问题之后，设计了一个递归调用Dijkstra算法的新算法，该算法可以求取前N条最短路径，而且时间、空间复杂度都为多项式阶。该算法已经成功应用于一个交通咨询系统中，自然满足实时应用需要。     

基于CSA无监督模糊聚类算法的异常检测方法

为解决模糊k 均值算法对初始化敏感及易陷入局部极值的不足,提出了基于克隆选择算法(CSA)的无监督模糊聚类异常入侵检测方法. 应用结合了具有进化搜索、全局搜索、随 机搜索和局部搜索特点的克隆算子快速得到了全局最优聚类,并应用模糊检测算法检测网络中的异常行为模式. 该方法的优点是不需要人工对训练集分类,并且可以检测出未知的攻击. 仿真试验表明,该方法不但能检测出未知的攻击,而且具有较低的误报率和较高的检测率.     

一种基于搜索空间分解的报文分类算法

报文分类算法的关键问题是查找准确且快速,最简单的分类算法就是线性查找,该算法的时间复杂度和空间复杂度均为O(N),线性查找的思想简单、易于实现、空间复杂度好,可以和其它算法混合使用,进而提高算法的分类速度。快速的分类算法采用很复杂的数据结构,牺牲空间来换取时间,甚至过分要求分类的快速性,忽略了空间性。文章根据这一问题进行展开,详细分析了经典的报文分类hicuts算法,分析其时间复杂度和空间复杂度的关系,并提出一种不过分降低分类速度的前提下,有效降低空间复杂度和预处理时间的改进方法。     

一种求所有最长增量子序列的算法

对计算最长增量子序列(longest increasing subsequence, LIS)的CM (Cover-Making) 算法进行详细地分析,提出一个基于CM算法的新算法,可以求出一个序列的所有最长增量子序列。 它的时间复杂度是O((m+1)k+(n-k)log k), 空间复杂度是O(n+km)。     

基于点割集的并行最短路径算法

在研究和分析了Dijkstra算法的基础上,在Dijkstra算法中通过引入点割集和割点的思想来改进Dijkstra算法,该方法首先利用点割集或割点把原问题分解成多个子图,然后对每个子图并行求最短路径,最后通过点割集或割点求出整个原问题的最短路径,从而降低算法的时间复杂度,提高算法的效率.     

星图应用哈米尔顿拉丁方的并行路由算法

提出了一种星图的信息路由算法.在星图中,从一个源节点到一个目的节点传递k个数据包,令第i个数据包将沿着第i条路径传输(1≤i≤k).对所有的数据包,要保证每个数据包的路径与其余数据包的路径不相交.为了构造这样的路由,提出了应用哈米尔顿循环拉丁方的星图信息路由算法,并给出该算法的时间复杂度是O(n2).     

求GF(pm)上周期为kn的序列线性复杂度的快速算法

提出和证明了求GF(p^m)上周期为kn的序列线性复杂度和极小多项式的一个快速算法, 其中p是素数, gcd(n, p^m-1)=1且p^m-1=kt, n,k与t均为正整数．该算法推广了陈豪提出的求GF(p^m)上周期为3n的序列线性复杂度的一个快速算法, 其中p是素数, gcd(n, p^m-1)=1且p-1=3t, n与t均为正整数．结合一些已知的快速算法, 可以快速计算GF(p^m)上周期为kn的序列线性复杂度, 最后给出一个具体例子．     

一种采用权重因子的低复杂度空间调制检测算法

针对空间调制系统的最大似然算法复杂度较高的问题,提出一种改进的最大比合并算法.定义一种权重因子,其下标对应发射天线序号;通过对权重因子的值进行降序排列,选取前L个值所对应的天线组成天线候选集,假设天线候选集中的某一根天线被激活,利用迫零算法计算该天线下的发送符号;最后对天线候选集中所有天线和对应的估计符号进行最大似然搜索.仿真结果表明,所提出的新算法在保证次优检测性能的前提下,明显降低了算法的复杂度.     

分块递归序列比对算法

利用分块递归的思想,结合检查点计算方法,提出一种线性空间复杂度序列比对算法,对于给定长为m和n的2条序列,空间需求约5(m+n)+Lsmin(m-1,n-1)+C2~5(m+n)+Ls(m+n-2)+C2,而时间需求一般情况下约1.5mn~3mn,在待比对序列相似度较高时约1.5mn~2mn,并通过同源物种全基因组序列比对实验证明,如果归一化编辑距离小于0.25,那么该算法比Hirschberg算法快10%以上.     

模逆算法的分析、改进及测试

公钥密码实现中,模逆算法经常是算法实现的瓶颈。通常求模逆的运算方法牵涉到大量的除法和减法操作,而除法操作需要大量的运算开销。基于现有的求最大公因子的方法,分析利用扩展欧几里德求模逆的方法,以及二进制扩展欧几里德算法,提出了利用二进制扩展欧几里德算法求模逆的方法,给出了几种算法性能比较的测试环境和测试结果。测试结果表明:改进的算法比利用扩展欧几里德求模逆的方法速度更快,对硬件实现更具有普遍性。     

利用双堆栈降低时间复杂度的新算法

分析了由树的前序序列和中序序列建树问题的递归算法的最坏时间复杂度和平均时间复杂度,以及利用哈希表改进查找得到的算法的时间复杂度;提出了利用两个堆栈构造的新算法,并证明其最坏时间复杂度与平均时间复杂度均为Ｏ（ｎ）。     

改进的Polar码的最小和译码算法

提出了改进Polar码的最小和译码算法,修正了最小和译码算法中的节点更新公式,即利用分段线性函数来逼近置信度传播译码算法中的函数lncosh（x）.相比于最小和译码算法,改进的算法在增加少许复杂度的情况下,增强了译码性能.相比于置信度传播译码算法,该算法在几乎不损失性能的情况下,大大降低了算法的计算复杂度,更易于硬件实现.该算法是基于最小和算法和置信度传播算法提出的,是在复杂度和性能上的一种折中.仿真结果表明,改进的最小和译码算法与置信度传播译码算法的性能几乎相同,比最小和译码算法的性能好.     

量子k-means算法

为提高经典k-means算法的计算效率,引入量子计算理论得到量子k-means算法。先将聚类数据和k个聚类中心制备成量子态,并行计算其相似度,接着利用相位估计算法将相似度信息保存到量子比特中,然后利用最小值查找量子算法查找最相似的聚类中心点。对比两种算法的复杂度可知,在一定条件下,相对经典算法而言,量子k-means算法的时间复杂度降低,空间复杂度得到指数级降低。     

固定序Bellman-Ford算法的一个改进

通过对固定序Bellman?Ford算法进行修正,获得了一种求解边数不大于k的最短路问题的新算法．相对于原始算法,修正后的算法通过改变点的标号过程,使得在第k次迭代后每一条路径的边数均不超过k．新算法被证明是正确的,它的计算复杂性为O（ km）．实验表明,在大规模情形下,相对于修正的先进先出算法,该算法具有显著的竞争优势．     

完全线性多阈值Otsu快速算法

针对经典多阈值Otsu算法在对图像进行分割的过程中采用穷举方法来寻找最优阈值,从而导致算法计算量庞大,并且随着阈值个数的增多时间复杂度呈指数增长的问题,本文提出了一种时间复杂度为O(n)的多阈值Otsu快速分割算法,即完全线性多阈值Otsu快速算法。该算法首先从理论上分析了导致多阈值Otsu算法计算量大、时间复杂度过高的主要因素。并在此基础上,从数值计算、多阈值的划分以及对于最优阈值的搜索三个主要方面,对经典的多阈值Otsu算法进行改进,采用动态规划的思想优化分割过程中的数值计算。然后对于多阈值的问题进行递归求解,将多阈值问题分解为多个单阈值问题。最后使用多种群粒子群(Multi-population PSO)算法对最优阈值进行搜索。实验结果表明,该算法大大降低了多阈值Otsu算法的时间复杂度,能够较好地应用于实时性环境。