一种改进的APDZS运动估计算法

在A．M．Tourapis的APDZS算法基础上，提出了一种改进的APDZS算法（IAPDZS）。通过对具体数据的分析，表明原来的APDZS算法存在较大搜索冗余，因此IAPDZS算法对此进行了相应改进。首先是初始候选向量的选择，增加（0，0）向量作为候选初始向量；相应的第二处改进在搜索顺序上，IAPDZS算法去除了以（0，0）为中心进行的第二次搜索；第三处改进在具体搜索过程中，IAPDZS算法根据不同的搜索模式，提出了改进方案。实验结果表明，IAPDZS算法能够在确保视频图像质量的前提下，有效提高搜索效率，总体搜索点数比APDZS算法降低20％左右。     

基于多级顺序排除算法(MSEA)的改进

块匹配运动估计是视频编码国际标准中广泛采用的关键技术.许多快速块匹配法通过限制搜索点数来减少运算量,但与全搜索算法相比极易出现匹配误差.该文介绍了一种应用新的判别条件的多级顺序排除算法（MSEA）,并在此基础上提出一种新的算法,该算法引入了尺度化的部分失真消除（PDE）技术,用于尺度化累积部分误差和当前最小误差.实验证明,相对于一脉相承的同为穷举搜索算法的全搜索算法（FS）、顺序排除算法（SEA）、多级顺序排除算法（MSEA）等,该算法大幅度提高了搜索效率.与多级顺序排除算法相比,平均每宏块节省了大约75%的运算次数.该算法在保证图像质量的前提下,使视频编码的速度大大提高.     

基于MWST-CS-K2算法的贝叶斯网络结构学习

针对K2算法依赖最大父节点数和节点顺序的不足,提出了一种改进的贝叶斯网络结构学习算法（MWST-CS-K2）。该算法先通过构造最大支撑树（MWST）得到最大父节点数;再利用变量间的关联度和更新系数对加边、减边和反转边进行规则设定,通过改进的布谷鸟算法对鸟巢位置进行寻优,应用广度优先搜索策略搜索遍历得到节点顺序;最后将最大父节点数和节点顺序作为K2算法的输入搜索得到最终网络。实验表明,所提出的MWST-CS-K2算法在标准的ASIA、SACHS和CHILD网络数据测试中的平均正确边比率分别达到了97.3%、87.7%和95.6%,学习效果优于其他对比算法,获得的网络结构和标准的网络结构最为相似。     

低复杂度序列高斯逼近MIMO检测算法

提出一种多入多出（MIMO）系统空间复用模式下的低复杂度序列高斯逼近（LC-SGA）算法。该算法把序列高斯逼近（SGA）算法在复数域进行路径搜索的问题近似为实数域的搜索问题,从而降低了计算复杂度。仿真结果表明,LC-SGA算法在相同搜索路径数的情况下,其误比特率（BER）性能与传统的SGA算法相当,且当搜索路径数较大时接近最大似然检测的性能。     

基于分层网络拓扑结构的最优路径算法

由于Dijkstra算法的基础是平面网络拓扑模型，因此当计算网络的节点数目较大时，计算的时间将急剧膨胀。为了快速地搜索到最优路径，基于分层网络拓扑结构（HiTopo），提出了双向分层搜索最优路径算法（BHWA）；该算法对现有分层路径算法进行了以下两点改进：（1）将分级网络的局部连通性作为划分子图的指标；（2）在路径计算过程中，使用弧段作为搜索目标，并采取了双向搜索策略。通过北京道路数据的实验表明：该算法在保持分层路径算法高效性的基础上，还提高了路径搜索结果的准确性；通过进一步研究表明，如果使用启发式搜索来对算法进行优化，则可以使算法的速度有更大的提升。     

一类排污问题在树图上的线性算法

ＭＥＧＩＤＤＯ等人证明了图搜索问题的ＮＰ完全性并给出一个树图上的算法，可在Ｏ（ｎ）时间内求解树的搜索数，在Ｏ（ｎｌｏｇ（ｎ））时间内求解树搜索方案．本文通过引入搜索方案边序表示法给出一个线性算法，可在Ｏ（ｎ）时间内同时求得树的搜索数和搜索方案．     

增强开发能力的改进人工蜂群算法

为解决人工蜂群（ABC）算法收敛速度慢、精度不高和易于陷入局部最优等问题，提出一种增强开发能力的改进人工蜂群算法。一方面，将得出的最优解以两种方式直接引入雇佣蜂搜索公式中，通过最优解指导雇佣蜂的邻域搜索行为，以增强算法的开发或局部搜索能力；另一方面，在旁观蜂搜索公式中结合当前解及其随机邻域进行搜索，以改善算法的全局优化能力。对多个常用基准测试函数的仿真实验结果表明，在收敛速度、精度和全局优化能力等方面，所提算法总体上优于其他类似的ABC算法（例如ABC/best）和集成多种搜索策略的ABC算法（例如ABCVSS（ABC algorithm with Variable Search Strategy）和ABCMSSCE（ABC algorithm with Multi-Search Strategy Cooperative Evolutionary））。     

基于改进的十字-菱形搜索算法的运动估计

通过对序列运动矢量概率分布分析，发现了该概率分布的方向性特性，提出了一种新的块匹配运动估计算法——改进的十字-菱形搜索（ICDS）算法。该算法在搜索的初始阶段使用小十字搜索模型对小运动矢量进行搜索，强调运动矢量分布的中心偏置特征；而对于大的运动矢量使用具有方向性的菱形搜索模型进行搜索，强调运动矢量分布的方向性，从而提高了运动矢量的搜索速度。该算法与菱形（DS）和十字-菱形块（CDS）匹配算法相比，在保证搜索质量的前提下，其搜索速度分别可以提高60％和35％。理论分析和实验结果证明ICDS算法有效，且具有较强的鲁棒性。     

基于混合智能优化算法的复杂软件可靠性分配

软件可靠性是系统设计、研究和运行过程中必须考虑的关键因素之一.与目前大多数软件可靠性分配的研究主要局限于简单的串并联模型不同,本文将最优化算法应用于大型复杂软件系统的可靠性分配.针对分布估计算法收敛速度快,全局搜索能力强,但是易于陷入局部最优;而差分进化算法局部搜索能力强,但搜索速度略慢的问题,本文提出一种元启发式算法——基于罚函数的混合分布估计和自适应交叉差分进化的优化算法（PHEDA-SCDE）,该算法收敛速度快,全局搜索能力强且不易陷入局部最优.基于四种特定的体系结构风格——顺序、并发、循环、容错,对复杂软件可靠性进行评估.为不失算法通用性,本文采用三个仿真算例进行实验,分别为单输入单输出系统,单输入多输出系统和多输入多输出系统.实验结果表明,PHEDA-SCDE算法在软件可靠性分配方面与同类算法相比,具有明显的可行性和有效性.     

双十字搜索算法的快速块匹配运动估计

在块运动估计中，不同形状、不同大小的搜索模型对搜索速度和搜索质量有很大的影响．通过运动矢量概率分布分析，发现了运动矢量概率分布具有除中心十字偏置特性以外的方向性特性，提出了一种快速的双十字搜索（DCS）运动估计算法．该算法首先根据运动矢量概率分布的中心十字偏置性，采用小十字搜索模型（SCSP）和大十字搜索模型（LCSP）对小运动矢量进行搜索，从而减少搜索点数．然后，根据运动矢量概率分布的方向性，使用非完全对称十字搜索模型（NFSCSP）对大运动矢量进行搜索，进一步提高了搜索速度．在保持相当搜索质量的前提下，双十字搜索算法与菱形搜索算法（DS）和十字-菱形搜索（CDS）算法相比，搜索速度分别可提高70％和40％．实验结果证明双十字搜索算法是非常有效的，且具有较强的鲁棒性．     

基于连续消除的六边形自适应搜索算法

结合连续消除算法提出了一种新的运动估计算法——基于连续消除的六边形自适应搜索算法，该算法采用六边形和小菱形搜索模板，并利用连续消除算法对每个待匹配点进行判断，减少待匹配点的个数。试验结果表明，该算法的搜索速度优于现有的快速运动估计算法，搜索精度接近于全搜索算法。     

H．264中带有中途停止的多层逐次消元运动估计算法

H．264视频压缩标准采用多模式运动估计，可以有效减少块匹配预测误差，但随着模式选择的增多，算法计算量成倍增加。为此，提出一种带有中途停止的多层逐次消元运动估计算法(MSEHS)。该算法根据模式分布规律，使用多层逐次消元法加速大块模式的搜索过程，并且提出中途停止准则，判断是否继续进行小块模式的搜索。这样既保证了多模式运动估计的优点，又减少了冗余计算。实验结果表明，该算法比全搜索算法整体速度提高了近4倍，同时可以保持与全搜索算法非常接近的图像质量和比特率。     

自适应消除的高效UMHexagonS算法

针对当前H.264/AVC视频标准的非对称十字型交叉多六边形网格搜索（UMHexagonS）算法搜索点数多的问题,提出了一种快速搜索提前中止策略的UMHexagonS算法。采用渐进消除算法的自适应消除思想,对不满足快速匹配判别条件的子块提前结束搜索,仿真结果表明,与传统法相比,改进算法在不损失编码效率的情况下,运动估计时间速率提高了约30.52%~60.7%,有效提高了编码的实时性。     

基于连续消除的正方形-菱形运动估计算法

在基于搜索起点预测和正方形-菱形算法(SDS)的基础上,结合连续消除算法(SEA),提出了一种新的运动估计算法:基于连续消除的正方形.菱形运动估计算法(SEA-SDS).实验结果表明,该算法以比较小的代价取得了与全搜索算法(FS)相当的效果;在搜索次数和精度方面均优于菱形(DS)和正方形-菱形(SDS)快速运动估计算法.     

解无约束全局优化问题的一个新的进化算法及其收敛性

文章利用一维搜索与局部极小点的消去技术设计了一个新的进化算法。此算法在迭代过程中,可不断消除那些比目前已找到的最好点差的局部极小点,从而使局部极小点的数目随着迭代的进行大量地减少,使算法更易找出全局极小点。另外,将一维搜索巧妙地用于算法之中,加快了收敛速度。并且证明了算法的全局收敛性,最后的数值实验也表明新算法十分有效。     

多分辨逐步消除快速匹配算法

为了提高块匹配运动估计的速度和精度,提出了多分辨逐步消除快速匹配算法。在块匹配运动估计中,像素块通过抽取降样而构成四种分辨率,对某匹配点而言,若其在较低分辨率上不满足为最优的必要条件,即对应于一不等式成立,说明该匹配点与当前最优点的像素信息差别较大,因此,将其消除,而不必进行复杂的匹配运算;否则,再在较高分辨率上进行相同的操作过程。如此逐步精细求优过程,使得只需用少量的计算就可以消除相当一部分的匹配点。同时,结合NTSS快速算法进行多分辨逐步消除。实验结果显示,本文方法能有效减少运算量。     

消元法化简关系模式求所有候选关键字新方法

本文研究了通过消癣关系模式化民与之具有相同候选关键字的一组简单关系模式的理论和方法。     

基于流水线的运动估计算法FPGA设计

块匹配算法(BMA)在目前运动估计算法中占主导地位,多级顺序排出算法(MSEA)是一种耗尽型,并具有精度特性的块匹配运动估计搜索算法,但是单靠软件的方法实现其运算速度并不能完全满足实时性要求.力求通过FPGA设计思想,达到实时处理的目的,首先对算法进行基本的FPGA硬件设计,然后将流水线结构应用到算法当中.实验结果表明,基本的硬件设计其运算速度相比于优化的软件方法提高了14倍以上.当引入流水线结构后,算法速度得到了进一步提高,从而为实时监控运动目标提供了可能.     

Constructing a minimum height elimination tree of a tree in linear time

Given a graph, finding an optimal vertex ranking and constructing a minimum height elimination tree are two related problems. However, an optimal vertex ranking does not by itself provide enough information to construct an elimination tree of minimum height. On the other hand, an optimal vertex ranking can readily be found directly from an elimination tree of minimum height. On n-vertex trees, the optimal vertex ranking problem already has a linear-time algorithm in the literature. However, there is no linear-time algorithm for the problem of finding a minimum height elimination tree. A naive algorithm for this problem requires O(nlogn) time. In this paper, we propose a linear-time algorithm for constructing a minimum height elimination tree of a tree.