CFL句子计数和分层词典序枚举

通过按推导树高度对句子分层,建立了句子集合中的分层词典序,进而发展出一种基于文法的,依分层词典序的,CFL句子计数和枚举方法,获得句子枚举的多个高效算法,对于无二义CFG,首先提出一个基础算法N2L,时间复杂度为O(n·lg(n)),n是被枚举句子的长度．对N2L进行改造,得到两个算法TD和BU,时间复杂度均为O(n)．对任意CFG,利用其推导树文法为工具后,文法无二义的限制被去除．对于一般的CFG,不论是否二义文法,也得到了依分层词典序的,时间复杂度为O(n)的枚举算法,同时枚举出句子及其推导树．该文的结果,从正面圆满回答了D(?)m(?)si提出的未决问题,即是否有按词典序,时间复杂度为O(n)的枚举算法?以及是否时间复杂度仅依赖于文法结构,及被枚举字之前同样长度的字的个数?本文给出的解答甚至比原问题所期望的更好．     

基于环形DNA分子的一种求解最大集团的计算模型

文中提出了一种基于环形DNA分子的新型计算模型.该模型的核心构成包括环形DNA分子,链霉亲和素包被的磁珠及环化酶.通过应用该模型解决了一个5个顶点的最大团问题,证明了该模型的可行性.在整个计算过程中,真解的搜索是借助于磁珠和环化酶,DNA分子结构在线性和环形之间相互转化.环形DNA分子的应用极大地减少了计算所需的时间和空间,算法的时间和空间复杂度均为O(n+m).对于解决一个n个节点的最大团问题,这种算法和枚举型算法相比,在搜索过程中所需试管数较少,只需n+1个试管,而利用枚举型算法则需要2n个试管.另外,文中构建的非枚举型初始解空间大大提高了DNA计算机的存储和计算能力.在将来,这种新型的DNA计算模型或许会成为一种解决某些NP完全问题的有效工具.     

多输入多输出系统中基于长方阻塞矩阵的酉多级Wiener降秩联合检测算法

针对传统均衡算法复杂度高、收敛速度慢的问题,提出了一种基于长方阻塞矩阵的多级Wiener降秩联合检测算法,其中的多级Wiener滤波器通过相关相减结构来实现,即酉多级Wiener滤波器.该算法选取酉多级Wiener滤波器阻塞矩阵中的一个长方子阵作为阻塞矩阵,使得酉多级Wiener滤波器前向递推分解中接收信号向量的维数逐级降低,从而在降低了均衡的迭代复杂度的同时,加快了算法的收敛速度.理论分析和仿真结果表明,基于长方阻塞矩阵的酉多级Wiener联合检测算法具有复杂度低、收敛速度快的优点.在具有4根发射天线、8根接收天线,并且采用BPSK调制的V-BLAST(vertical Bell labs layered space-time)系统中,采用本算法仅用基于酉多级Wiener滤波的均衡算法一半的计算复杂度在高信噪比处即可达到与其相同的误码性能.     

复杂模型三维点云自动配准技术研究

三维点云配准是逆向工程中的关键。针对经典ICP算法在配准过程中对初始位置要求较高可能产生局部最优解以及对大量点处理效率低的缺点,本文以经典的ICP算法为基础,结合主成分分析的初始配准方法,使用随机采样点云精简和k-d树查找对应点对减少运算的时间复杂度方面进行改进,提高了传统ICP算法的效率和精度。并利用配准后两簇点云中对应点对之间的误差完成了几何质量评估,用RGB色彩模式来直观显示。经实验对比,本算法能很好的弥补单纯的粗略配准和经典ICP配准的缺点,具有良好的匹配精度和速度。     

序列递推关系与一类代数几何码的有效译码——Ⅱ.一个达到Feng Rao界的有效译码算法

对于一类代数几何码 ,在其错误向量的伴随式序列上引进了一种递推关系 .运用广义Berlekamp Massey算法 ,结合大数表决方案 ,给出了一类代数几何码的一个达到Feng Rao界的有效译码算法 ,这个算法的复杂度为O(γo1n2 ) .对于不同的代数曲线 ,可通过适当选取基函数来降低算法的复杂度     

无线传感器网络最小中继节点布置问题的近似算法

为了消除传感器节点路由负载的不平衡,可在无线传感器网络中布置少量功能较强的中继节点作为路由节点,最小化中继节点数是其主要优化目标.文中证明了有界平面区域上的中继节点布置问题是P问题,但一般情况下的计算复杂度相当巨大.从中继节点布置问题的几何覆盖特征出发,提出了一种O(n~2 log n)时间的贪心近似算法,其中n为传感器节点数目.在该算法迭代过程的每一阶段,先从未被覆盖的传感器节点中选出一个关键节点,为了阻止孤立节点的产生,再按照"优先覆盖与关键节点距离较近的传感器节点"的原则来确定中继节点的位置.实验结果表明该算法可在很短的时间内生成一个接近最优的可行中继节点布置,且在中继节点布置的尺寸以及执行时间方面都要优于现有算法.     

多天线放大转发中继系统基于MMSE的重传预编码设计

针对多天线放大转发中继系统,本文提出了一种基于MMSE的新的重传预编码方案,把重传预编码设计问题分解成两个子问题:离散的信道配对和连续的联合源、中继功率分配问题.最优的信道配对需要遍历所有信道配对方式,对于每一种配对方式,联合源、中继功率分配问题是一个多参数非凸的优化问题,本文提出了一种获得该问题最优解的算法和一种次优迭代功率分配算法,此种通过遍历信道配对获得最优重传预编码的方案计算复杂度较高.本文证明了在一跳信道信噪比趋于无穷时,最优的信道配对是使之前的子信道增益和当前另一跳信道奇异值大小排列顺序相反,进而提出了一种简化的信道配对方法.仿真结果表明,简化的信道配对和迭代功率分配算法性能均接近最优.本文所提出的重传预编码与已有的预编码相比,能获得明显性能提升.     

基于总空闲时间增量的无等待流水作业计划优化算法

将NP难的最小化最长完工时间无等待流水作业计划问题等价转化为最小化总空闲时间的问题.分析任务之间的独立性,给出算法基本算子的目标增量性质,通过计算目标增量而不是整个目标函数值来判断新作业计划的优劣,可将算法的时间复杂度降低1阶.提出生成初始作业计划算法,实验分析出迭代构造解和再改进解的有效方法;构造出有效的快速迭代启发式算法FCH(fast composite heuristic).FCH和目前求解该问题的有效算法比较,实验结果表明,FCH接近目前的最好性能,需要最少的计算时间.FCH可为大规模无等待作业计划、实时调度和重调度等问题提供有效方法.     

一种基于自体集层次聚类的否定选择算法

否定选择算法是用于产生人工免疫检测器的重要算法,然而传统的否定选择过程需要将随机生成的候选检测器与全部自体数据进行匹配以排除识别了自体的无效检测器,该匹配过程导致检测器的生成效率过低,极大地限制了免疫算法的应用.为此,文中提出了一种基于自体集层次聚类的否定选择算法CB-RNSA.算法首先对自体数据进行层次聚类预处理,然后用聚类中心取代自体数据点与候选检测器进行匹配,以减少距离计算代价.在生成检测器的过程中,候选检测器被限定在非自体空间的低覆盖率区域内,以降低检测器冗余.对检测器的非自体空间覆盖率进行了概率分析,给出了中止生成检测器的条件,该条件较传统的预设检测器数量的中止条件更为合理.理论分析表明CB-RNSA的时间复杂度与自体集规模无关,从而解决了经典的否定选择算法的时间复杂度随自体数量呈指数增长这一难题,极大地提高了大自体样本空间下的检测器生成效率.对比实验结果表明:在相同的实验数据集与期望覆盖率下,CB-RNSA的检测率比经典的RNSA与V-detector算法分别提高了12.3%与7.4%,误警率分别降低了8.5%与4.9%,产生检测器的时间代价分别降低了67.6%和75.7%.     

ROV水动力性能及推力控制分配研究与仿真

良好的推力控制分配策略是缆控水下机器人(remotely operated vehicle, ROV)机动性和作业安全性的保障,也是ROV运动控制技术得以实现的必要条件.但现有的推力控制分配策略存在推力输出饱和或计算时间过长等问题,导致ROV机动性欠佳.针对现存问题,提出了一种混合优化目标推力控制分配策略.首先,建立ROV驱动系统数学模型,设计了一种混合优化目标推力控制分配函数;再使用Fluent软件分析不同工况下导管螺旋桨的水动力性能,得到推进器的推力模型,从而确定混合优化目标推力控制分配函数的约束条件;最后采用光滑牛顿法求解混合优化目标推力控制分配函数,并与传统伪逆推力分配策略进行仿真对比.仿真结果表明,混合优化目标推力控制分配策略能满足各推进器对推力的约束要求,并能有效地利用约束范围内的推力集合,且通过光滑牛顿法求解的总体误差小于0.0007 N m,单步迭代次数在10步以内,单步计算时间小于2 ms,其具有精度高、实时性好、无推力输出饱和等优点.     

求解网络风险传播问题的近似算法及其性能分析

在充分阐明风险传播研究意义的基础上,给出了网络风险传播问题的定义,证明了该问题是NP难题,并提出了一个基于邻近传播和最小入度的近似算法——APMI算法,该算法最坏时间复杂度为O（n^3）,最差近似比为D（n）．最后通过模拟实验分析了网络规模、网络密度和风险源密度等3方面因素对APMI算法和现有精确算法RH的性能或准确性的影响．实验结果表明：RH算法的性能受网络密度影响很大（呈指数增长）,受网络规模和风险源密度的影响较小;APMI算法将RH算法在网络较稠密时的指数时间复杂度降低为多项式时间,而其准确性指标Coefficient仍保持在0．995以上．     

基于图论的多尺度特征点匹配

文中针对在视觉测量系统中双目立体视觉特征点同名点匹配问题,提出基于图论的稀疏特征点全局匹配算法.首先,提出多尺度特征点提取算法来获得特征点的准确位置.算法引入多尺度小波变换,利用变换后的系数构建自相关矩阵从而进一步确定特征点的位置.然后,根据图理论将提取的稀疏特征点构建一个图,从而使特征点匹配问题转化为可用能量最小化方法解决的图的标记问题.此多尺度特征点全局匹配算法利用多尺度分析来提高匹配精度,并且利用特征点构建图降低了图的规模,同时根据极线约束选择潜在视差值进行计算,降低了计算量.实验结果表明此算法可获得精确的匹配结果.     

基于特征识别的增强现实跟踪定位算法

文中提出一种在场景自然特征识别基础上采用关键帧匹配的增强现实跟踪注册算法,实现了基于计算机视觉的户外大场景范围内的实时跟踪定位.算法针对关键帧匹配中的宽基线特征匹配问题,提出采用随机树的模式分类方法实现场景自然特征的离线训练和在线实时精确匹配.同时采用Kalman滤波器对参数估计结果进行平滑解决视觉跟踪定位中的抖动问题.以该算法为核心构建出基于视频透视式头盔显示器的移动增强现实系统,并将其成功应用于圆明园大水法景观的数字重现.真实场景实验验证表明,该方法具有实时、鲁棒的优点,适用于户外跟踪定位.     

基于自适应尺度的遥感影像渐进配准

图像配准是遥感图像处理中的基本问题.本文针对多源多时相遥感影像的特点,提出了一种基于自适应尺度的渐进配准方法,在从粗到细的迭代配准过程中,可以通过上一次配准结果的几何定位误差来确定本次匹配的尺度,并按该尺度提取特征角点和特征邻域进行匹配,与常规金字塔渐进配准方法相比,减少了匹配次数,提高了配准效率.另外,特征提取和匹配过程中提出一种基于Harris-Laplace算法和相位相关算法的遥感影像配准算法,利用Harris-Laplace角点代替原始图像,能够综合区域和特征的优点,对亚像元偏移、旋转、尺度变化具有不变性,同时对对比度和灰度的变化不敏感,具有很强的抗噪性.在特征检测和匹配的过程中采用限定搜索区域、抽稀角点等多种优化策略来提高算法的性能.实验证明,算法具有很好的精度,对几何攻击具有很好的鲁棒性,该算法已经应用于CBERS-02B星3级数据的批量自动化生产,具有很好的应用效果.     

基于复杂网络挖掘的用户行为感知机制

用户行为感知是进行网络管理、安全检测以及应用趋势分析的基础.针对基于流量统计特征检测方法具有计算复杂度高和"概念漂移"的缺陷,提出了一种基于用户复杂网络图的用户行为感知机制算法(UBP-CN).算法将用户标识{IP,Port}和用户交互分别抽象为一个点和一条边,构建了用户复杂网络图;应用社团挖掘算法将复杂网络图划分为互不相交的行为子簇,使得用户之间的通信抽象为一种"社会团体";通过定义基于相对熵的"用户行为模式"(UBM),表征了各个子簇背后表现出的行为特性,并使用"UBM+Port"对各个子簇进行标签映射,实现了用户行为的有效感知.仿真结果表明:在不牺牲用户行为分类准确率的前提下,算法不仅能克服"概念漂移"问题,还能有效降低算法的计算复杂度.     

再分配伪逆算法分配效率研究

多操纵面先进战斗机在进行舵面分配设计时,分配效率是衡量分配算法优劣的一个重要指标.再分配伪逆算法(RPI)的分配效率取决于伪逆阵的选择,其可达转矩集是一个复杂的非凸多面体.本文利用"微元"的求解思路,对二维及三维RPI算法的分配效率进行了研究,给出一种近似求解RPI可达转矩集的方法.将RPI分配效率作为适应度函数,通过遗传算法来选择具有最优分配效率的广义逆阵,从而提高RPI算法的分配效率.以某飞机的数据进行基于RPI的分配器设计,结果显示此方法显著提高了算法的分配效率.     

基于DAG和AHP-TOPSIS算法的多乘员协同任务分配方法研究

提出了一种基于有向无环图(direct acyclic graph, DAG)以及层次分析法结合逼近理想解排序法(analytic hierarchy process-technique for order preference by similarity to an ideal solution, AHP-TOPSIS)的多乘员协同任务动态分配方法.基于列表调度算法的思想,对乘员任务进行分解,并以任务划分层级,通过广度遍历,对每层任务进行排序,再逐个分配.综合考虑乘员脑力负荷、个人能力、时间成本和任务相关度.对单个任务采用AHP-TOPSIS算法确定最佳分配对象,并实时更新乘员状态,进行下一个任务的分配,直至所有任务分配完成.本方法实现了随战场态势、作战任务、乘员状态等实时变化时乘员协同任务的合理分配与动态调整,可有效解决非预期事件下协同作战效率不高、乘员负荷不均衡以及任务分配不合理等问题.     

基于Smith-Waterman算法的并行分而治之生物序列比对算法

生物序列比对是生物信息学中最常见的问题之一, 基于动态规划思想的Smith-Waterman算法是序列比对中最基本的算法. 然而现有的并行Smith-Waterman算法都需要庞大的内存, 且无法处理大规模的数据串, 随着生物数据的急剧增长, 这些并行算法对内存空间的需求已成为需要迫切解决的问题. 由此提出一种并行生物序列比对算法, PSW-DC算法, 该算法采用分而治之的方法把query序列划分为若干片段, 并分配给相应的各个处理器, 而后并行地按Smith-Waterman算法与目标(subject)序列进行比对, 再通过按一定规则的扩展过程求取序列的优化匹配. 与其他并行算法相比, 该算法有效地降低了内存空间的需求, 并实现了对大规模数据串的并行处理. 为实现该算法, 给出了一种称作C&;E的拓展规则及实现方法. 且该方法已经在实际系统中得到实现.     

基于单形体几何的高光谱遥感图像解混算法

提出一种新的基于单形体几何的高光谱遥感图像混合像元丰度估计算法.该算法的目标是在已知端元矩阵的基础之上,估计高光谱图像中各个观测像素点中每个端元的丰度.根据凸几何理论,基于线性混合模型的高光谱解混问题可以看成一个凸几何问题,其中端元位于包含整个高光谱数据集的单形体的顶点,而它们对应的重心坐标则可以看作各个观测像素的丰度.提出的方法由3部分组成,分别为基于单形体体积的重心坐标计算方法、距离几何约束问题和基于内点的单形体子空间定位算法.与其他基于单形体几何的算法相比,该方法具有诸多优点.Cayley-Menger矩阵的引入使得欧式空间上的运算转化为距离空间上的运算,在降低运算复杂度的同时很好地兼顾到数据集的几何结构.而且,单形体重心的使用确立了一种快速而精确的判断方法来确定观测像素所属的子空间,进而利用递归的思想得到丰度值.此外,算法核心仅仅涉及观测点与端元之间的距离,而与波段数无关.因此,该算法无须对数据执行降维处理,从而可以避免因数据降维而造成的有用信息的丢失.仿真和实际高光谱数据的实验结果表明,所提出的算法与同类其他优秀的算法如FCLS和SPU相比,具有更高的运算精度,同时在端元数目较小时具有较快的运算速度.     

基于信道统计特性的中继选择与功率分配算法

针对放大前传多源协同通信网络,在保证系统满足一定中断概率的前提下,以最小化系统总发射功率为目标,提出一种基于信道统计特性的中继选择与功率分配算法.由目的节点根据源节点的优先级因子,依次确定是需要直传还是选择中继进行协同前传,以及相应的源节点和中继节点的最优发射功率.该算法运算复杂度低,且无需在传输中实时更新,能节省系统开销.仿真结果表明,与直接传输和AF策略相比,该算法能有效节省传输所需要的总发射功率,且性能优于凸松弛算法,与最优穷举搜索算法相近.