一种最大匹配问题DNA计算算法

DNA计算作为基于生化反应的一种新的计算模式,凭借其巨大的并行性和海量的存储能力已经成为解决NP难题的潜在解决方案之一.把传统计算机中的剪枝技术引入到DNA计算算法的设计中,提出一种基于Adleman模型生物操作与粘贴模型解空间的最大匹配问题DNA计算新算法.算法由图编排器、预解空间生成器、匹配生成器及最大匹配搜索器组成.与已有同类算法的对比分析表明:该算法在保持多项式操作时间的条件下,将求解最大匹配的解空间从O(2m)减少到O(1.618m),将DNA计算机在试管内可求解的最大匹配问题的规模从60(260≈1018)提高到86(1.61886≈1018).同时,与传统的穷举算法相比,该算法具有高效的空间利用率及容错技术的优点.     

哈密顿回路问题的DNA表面计算模型

基于生化反应原理的DNA计算具有强大的并行运算能力,DNA计算机在求解NP问题上存在着硅计算机无法比拟的先天的优越性。论文采用荧光标记的策略,给出了一种新的哈密顿回路问题的DNA表面计算模型。该模型首先将问题解空间的DNA分子固定在固体载体上,然后通过进行相应的生化反应来求得哈密顿回路问题的所有解。在新模型中,解空间的生成过程与边的排列顺序无关。     

最大匹配问题的粘贴DNA算法

最大匹配问题(MMP)是图论中经典的组合优化问题。针对此问题提出了基于DNA粘贴计算模型的求解算法,阐述了该算法如何利用DNA链构建最大匹配问题的初始编码,说明了应用粘贴计算模型寻求最终解的生物操作过程,同时分析了此DNA并行算法的计算复杂度,最后给出了该算法的计算机模拟仿真结果和应用实例,得到了所给问题的最大匹配解,并对算法的可行性进行了验证和总结。     

哈密尔顿回路问题的DNA表面计算模型

首次提出用DNA表面计算模型来解决无向图哈密尔顿回路问题。该模型基于哈密尔顿回路问题的解空间,将问题解空间的DNA分子固定在固体载体上,对其进行荧光标记,然后通过相应的生化反应筛选出哈密尔顿回路问题的所有解。与已有的哈密尔顿路径问题的其它模型相比,新模型具有错误率低,编码简易,读取方便等更好的性能。     

图的最小顶点覆盖问题的DNA表面计算模型

基于生化反应原理的DNA计算具有强大的并行运算能力,DNA计算机在求解NP问题上存在着硅计算机无法比拟的先天的优越性。采用荧光标记的策略,给出了一种新的图的最小顶点覆盖问题的DNA表面计算模型。该模型首先将问题解空间的DNA分子固定在固体载体上,然后通过进行相应的生化反应来求得图的最小顶点覆盖问题的所有解。新算法利用荧光猝灭技术,通过观察荧光来排除非解,具有编码、解读简单和错误率低的特点。     

文物碎块虚拟拼接中的表面特征优化

为了有效地度量空间曲面相似性,针对噪声敏感、部分匹配的受损文物碎块模型,提出一种基于空间曲面特征优化的匹配算法.首先计算模型表面点体积积分不变量形成匹配约束簇,提取匹配约束簇特征,并结合曲面凹凸互补性得到初始匹配簇对;然后定义3类空间几何一致性约束,并采用最大独立集方法对非正确匹配对进行消除,求解粗匹配最优化问题;最后在粗匹配实验基础上,采用不变特征迭代最近点进行精确对齐.实验结果表明,该算法能较好地实现高噪声影响下存在部分匹配关系的受损文物虚拟拼接.     

多边匹配决策模型及其帕累托有效解

由多层次、多阶段、多时期的复杂匹配引申出多主体之间的协调匹配问题,在给出不同类幂集、满意度汇集算子的基础上,从多边匹配映射角度对稳定的匹配组进行分析,论证稳定匹配方案的合理性、全面性和公平性,继而给出帕累托最优匹配方案和帕累托有效匹配方案,同时建立一个包括初步匹配、替换匹配、交换匹配三个过程的多边匹配算法,形成多边匹配问题的满意解。计算实例和应用分析表明,该方法能够获得帕累托有效匹配方案,并可应用到不同组成部分之间的多边匹配上,为此类问题提供了匹配模型和解决方案。     

基于自注意力网络的深度图匹配模型

现有深度图匹配模型在节点特征提取阶段常利用图卷积网络（GCN）学习节点的特征表示。然而，GCN对节点特征的学习能力有限，影响了节点特征的可区分性，造成节点的相似性度量不佳，最终导致模型的匹配精度受损。为解决这一问题，提出一种基于自注意力网络的深度图匹配模型。所提模型在节点特征提取阶段使用新的自注意力网络来学习节点特征，其原理是通过空间编码器和自注意力机制分别学习节点的空间结构以及所有节点之间的联系，从而改善节点的特征描述。此外，为了减小放松图匹配问题所带来的精度损失，将图匹配问题建模为整数线性规划问题，在图匹配问题的节点匹配基础上增加结构匹配约束，以及引入高效的组合优化求解器来计算图匹配问题的局部最优解。实验结果表明，在PASCALVOC数据集上，与PCA-GM相比，所提模型在20类图像上的匹配精度平均值提高了14.8个百分点；在Willow Object数据集上，所提模型在5类图像上的匹配精度平均值提高了7.3个百分点，并且在自行车、植物等目标匹配任务上达到了最佳的效果。     

具有形变的平面轮廓匹配问题

提出了一种线性弹性模型用以解决具有形变的平面轮廓匹配问题.这种匹配方法克服了 弹性匹配方法存在的计算复杂或内部相互制约力不强的缺陷,表现出非常强的鲁棒性.整个 匹配过程是一个由粗至精的动态迭代过程.在所有弹簧结点上都进行外力计算.在外力的 作用下,匹配过程能以很快的速度进行收敛.     

三维形状部分相似性匹配的逐点配对方法

为了计算2个三维模型可能存在的部分对应表面的形状相似问题,提出一种基于2个三维模型表面之间所有的点与点配对的三维形状匹配方法.在2个不同的部分中独立确定匹配的旋转参数与平移和尺度缩放参数,从而避免了形状匹配中计算量巨大的问题.其中,形状匹配的旋转参数通过匹配2个三维表面法线获得;平移和尺度缩放参数由2个三维表面对应点处切平面的结构关系确定.实验结果表明了该方法的可行性.     

一种带有通配符和长度约束模式匹配问题的动态剪枝算法

近年来,随着生物信息学、信息检索等领域的发展,串模式匹配问题被不断扩展.其中,具有代表性的是在模式中引入可变长度的通配符而形成带有通配符的模式匹配(PMWL).该问题定义的灵活性给用户提供了方便,却也造成了求解上的困难.因此,如何在多项式时间内得到更好的匹配解成为研究的焦点.提出了一种启发式的小兵算法.小兵算法通过将PMWL问题转化为路径搜索问题,并借鉴动态剪枝思想,在算法搜索的过程中动态地将不可能的匹配位置剪枝,从而提高解的质量.实验在真实DNA序列上进行,并人工生成了196个模式.结果表明,相比于目前最有效的SAIL算法,小兵算法在绝大多数的尾部有重复字符的模式中可以获得更好的匹配解.     

一种基于球面调和描述子的3维模型相似性比较算法

提出了一种基于球面调和描述子的3维模型相似性比较算法。首先,对3维模型进行一分为二的递归分解,然后对每次递归分解得到的3维模型顶点集合进行球面映射得到其球面图像,最后计算所有球面图像的球面调和描述子得到3维模型的特征二叉树。通过对3维模型特征二叉树进行相似性比较可以得到3维模型的相似性。实验结果表明,该算法不仅能较好地比较3维模型相似性,而且对坐标系旋转变换、模型噪声、网格简化和细分具有较好的鲁棒性。     

基于三视图的自适应加权迭代匹配筛选算法

针对基于三视图的传统三维重建时特征点匹配后保留正确匹配点对数量过少、由图像噪声、拍摄照片时遮挡和震动等因素引起的匹配误差较大等问题,文章提出了一种自适应加权迭代算法,该算法通过给匹配点对加权进行迭代筛选来实现,可以稳定的获得数量较多、结果较准确的匹配点对,从而精确求解三视图空间约束矩阵三焦点张量.实验证明,文章提出自适...     

斜面参数优化全局立体匹配算法研究

针对现有立体匹配算法在非平行平面区域匹配中出现“阶梯效应”的问题,提出一种斜面参数优化的全局立体匹配算法。该算法用斜面参数替代视差值作为全局匹配算法的优化变量,并结合粒子滤波思想实现斜面参数的（近似）连续取值及能量函数的连续域全局优化,理论上可以同时消除传统匹配算法中视差离散取值及视差一致性约束带来的影响,从根本上消除“阶梯效应”。针对典型非平行平面测试图像对的实验结果表明,该算法在有效消除“阶梯效应”的同时降低了误匹配率。     

一种有效的字符串有序跳跃模式近似匹配算法

字符串的模式匹配问题是计算机科学的基本问题之一,而近似模式匹配更是近期的研究热点。本文分析了文本分析领域中出现的一种特殊的近似模式匹配问题,即字符串有序跳跃模式近似匹配问题,提出了一种基于有限自动机的组件组合分析算法。算法的特点在于将组件匹配过程与组配过程进行分离,这样既降低了问题的复杂度,又可以实现按策略组配的灵活性。组件匹配过程中利用有限自动机对跳跃模式的组件进行匹配查找;组件的组配过程中先对查找到的组件进行组合分析,然后再对各种组合进行初步筛选和基于策略的优选。初步筛选工作是依据顺序性、唯一性和最大数三条原则进行;而优选工作是根据四个设计的评价参数选择其中最佳组合。实验结果表明,该算法的确能解决字符串有序跳跃模式匹配问题,完全可以适用于句型匹配与主题词跳词匹配。     

行列双动态规划的改进自适应立体匹配算法

在各种立体匹配算法中,利用动态规划算法求解可有效地提高立体匹配的速度和精确度,同时具有实时性好、易于实现的优点。利用动态规划算法的优点,提出一种基于行列动态规划的自适应立体匹配算法,采用改进的自适应代价函数和能量最小化模型,对最优化问题进行求解。在求解的过程中,基于行动态规划得到的列方向视差值的变化给予对应数据项不同的奖励值,以减少行动态规划产生的明显条纹,最后使用列动态规划得出最终结果。实验结果表明,该算法能够减少总体的匹配错误率,减少明显的条纹瑕疵,取得较理想的立体匹配效果。     

基于采样数据稳定度的在线手写签名认证方法

介绍了一种基于采样数据稳定度的在线手写签名认证方法．该方法首先根据签名样本数据获得特征序列的采样点稳定度以及特征稳定度，然后利用这两种稳定度作为权值，采用基于加权动态匹配比较方法得到最终匹配结果，实验结果证明了本文提出的方法的有效性．     

打字比赛系统中字符串匹配算法

打字比赛程序,是学校为了加强学生对计算机基本技能的掌握,而开发的一款用于检验打字速度、准确率等多项指标的比赛程序．传统的字符串匹配算法是基于关键词的匹配算法,只能得到位置信息,而比赛程序是两个大文本之间进行匹配,需要获得更加详细的匹配信息,这时传统算法就无法满足要求．通过对实际问题的探索和研究,在传统算法的基础上,设计出一种新的匹配算法．这种算法可以进行两个文本之间的匹配,得到正确的内容、错误的内容等信息．应用这一算法编写软件,验证了算法的可行性和实用性．     

基于边映射表连接的匹配算法

针对面向语义网络图匹配的特殊性, 在基于状态回溯搜索算法的基础上提出一种新的称为基于边映射表连接的匹配算法, 利用语义网络图的有向性, 将图匹配问题转换为对搜索路径的规划, 并采用深度优先算法形成搜索步, 同时对目标图的所有边建立索引, 加快以边匹配为中心形成边映射表的过程, 最后对边映射表进行连接形成结果集。在真实数据集上的实验结果表明, 该算法具有较高的执行效率。