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

武优西,吴信东,江贺,闵帆. 一种求解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 问题的启发式算法,更重要的是对于求解其它复杂问题具有一定参考价值。

点击这里阅读本文

IMG_1560

武优西:男,1974年6月生于黑龙江省齐齐哈尔市,博士,教授,博士生导师,中国计算机学会高级会员,IEEE CS和ACM 会员,美国佛蒙特大学和莱特州立大学访问学者(2009.8-2010.8, UVM; 2015.10-2016.10, WSU)、国家自然基金同行评议函评专家、教育部学位与研究生教育发展中心学位论文评审专家、天津市科委项目评审专家、北京市科委项目评审专家、校学术委员会委员&院学术委员会副主任

目前主持国家自然基金项目1项,第二研究人合作承担国家自然科学基金项目2项,其中1项为校内合作,另外1项与大连理工大学合作。此外,先后主持河北省自然科学基金项目、河北省科学技术研究与发展指导计划项目、河北省教育厅重点项目等项目,主要研究兴趣为数据挖掘、智能计算(模式匹配或串匹配)和机器学习。第一作者或通信作者或合作作者在SCI一区、二区或知名SCI期刊以及一级学报发表论文及ICTAI等国际会议发表论文20余篇,这些期刊包括:IEEE Transactions on Cybernetics、Science China Information Sciences、Journal of Computer Science and Technology、Neurocomputing、Applied Intelligence、Journal of Information Sciences、计算机学报、软件学报、通信学报;普通高等教育“十一五”国家级规划教材主编1本。

先后主持获得天津市科技进步三等奖(2008年),参与获得河北省科技进步三等奖(1999年和2002年)和河北省教学成果二等奖(2000年);河北省优秀硕士论文指导教师(2014年和2015年)。指导多名硕士研究生,其中2名硕士研究生分别在2014年和2015年度获评河北省优秀硕士学位论文(2014年-该年全省共106篇;2015年-该年全省共118篇);2016年有4名硕士研究生获得我校优秀硕士学位论文(该年全校共有50名同学获得)。先后指导3名研究生承担河北省在读研究生创新资助项目。

 

为如下期刊和会议审稿论文30余篇:国外期刊:Knowledge and Information Systems(KAIS)、Knowledge-Based Systems(KBS)、Journal of Information Science(JIS)、IEEE Access、Advances in Artificial Neural Systems;国内期刊:计算机学报、自动化学报、通信学报、电子与信息学报、天津大学学报、计算机科学等和国际会议Electromagnetic Field Computation (IEEE CEFC)、a Program Committee member of IEEE ICDM 2015 PhD forum、International Joint Conference on Neural Networks (IJCNN)2016。

所在部门: 计算机基础教学部
授课对象:全校所有非计算机专业
教学职责:非计算机专业的计算机普及
讲授课程:《计算机文化基础》、《软件技术基础(C++/VB)》、《计算机技术及应用基础(研究生)》

 

Email:  wuc567  at  163  dot com

Tel: 022 – 60435882