论文部分内容阅读
讨论带有限长空位和one—off约束条件的模式匹配问题，其中限长空位改变单个匹配解结构，one-off条件约束匹配解之间的关系，从而形成规模较大且稀疏的解空间．借鉴约束可满足性问题框架，将PMGO问题转化为图结构下的路径搜索问题，并证明转化的等价性．然后提出图结构下的剪枝和匹配算法（GPM），根据one-off约束得到节点之间的约束关系，再迭代交互地进行剪枝与搜索．实验中使用匹配解丢失率度量已有启发式算法和GPM的完备性，证明GPM可与已有启发式算法形成互补，有效降低匹配解丢失率．