%0 Journal Article
%T 模式特征对带有通配符和长度约束的模式匹配问题的影响
%A 王海平
%A 胡学钢
%A 谢飞
%A 郭丹
%A 吴信东
%J 模式识别与人工智能
%P 1013-1021
%D 2012
%X 带有通配符的模式匹配问题(PMWL)模式定义的灵活性给用户提供方便，却也造成求解上的困难。目前没有任何多项式算法能得到该问题的完备解，同时也缺少足够的完备性分析。文中认为模式特征是影响PMWL完备性的关键因素，并提出模式重复度的概念，记为rep。证明在rep=0的限定条件下PMWL的完备性，同时分析rep>0时PMWL不完备的原因。实验以近似比为指标，说明rep对PMWL完备性的影响。
%K 模式特征
%K 完备性
%K 通配符
%K 模式匹配
%U http://manu12.magtech.com.cn/Jweb_prai/CN/abstract/abstract9518.shtml