CAJ | 학술논문

具有间隙约束和一次性条件的最大模式匹配(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问题的启发式算法,更重要的是对于求解其它复杂问题具有一定的参考价值.
구유간극약속화일차성조건적최대모식필배(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문제적계발식산법,경중요적시대우구해기타복잡문제구유일정적삼고개치.