具有间隙约束和一次性条件的最大模式匹配

具有间隙约束和一次性条件的最大模式匹配

武优西,吴信东,江贺,闵帆. 一种求解MPMGOOC问题的启发式算法. 计算机学报. 2011, 34(8): 1452- 1462 .  (PDF) (Source codes)

 

具有间隙约束和一次性条件的最大模式匹配(Maximum Pattern Matching with Gaps and One-Off Condition,MPMGOOC)是一种具有通配符长度约束的模式匹配问题,其任务是寻找彼此互不相关的最多出现。文中基于一种新的非线性数据结构——网树,提出了一种解决MPMGOOC 问题的启发式算法。与树结构不同之处在于,除根结点外,网树中任何结点可以多于1 个双亲结点。文中给出了网树的定义及其相关的概念和性质。基于这些概念和性质,提出了一种选择较优出现 (Selecting Better Occurrence,SBO)的启发式算法。该算法在搜索一个出现的循环中,采用了贪婪搜索双亲策略 (Strategy of Greedy-Search Parent,SGSP)和最右双亲策略 (Strategy of RightMost Parent,SRMP)寻找相同叶子的两个出现并选择其中较好的出现作为SBO 算法的结果。SGSP 策略的核心思想是每一步都寻找当前结点的一个近似最优双亲(Approximately Optimimal Parent, AOP);SRMP 策略的核心思想是每一步都寻找当前结点的最右双亲结点。实验结果表明,在多数情况下SBO 算法可以获得更好的解且解的质量较其它算法有显著的提高。本文不但提供了一个解决MPMGOOC 问题的启发式算法,更重要的是对于求解其它复杂问题具有一定参考价值。

点击这里阅读本文

2 评论

发表评论