结合SE-Tree结构特征的极小碰集求解算法

作     者：刘思光 欧阳丹彤 王艺源 贾凤雨 张立明 Liu Siguang;Ouyang Dantong;Wang Yiyuan;Jia Fengyu;Zhang Liming

作者机构：吉林大学计算机科学与技术学院长春130012 符号计算与知识工程教育部重点实验室(吉林大学)长春130012 

出 版 物：《计算机研究与发展》 (Journal of Computer Research and Development)

年 卷 期：2016年第53卷第11期

页      面：2556-2566页

核心收录：

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 081104[工学-模式识别与智能系统] 08[工学] 0835[工学-软件工程] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：国家自然科学基金项目(61133011 61402196 61272208 61003101 61170092) 中国博士后科学基金项目(2013M541302) 吉林省科技发展计划基金项目(20140520067JH) 浙江师范大学计算机软件与理论省级重中之重学科开放基金项目(ZSDZZZZXK12) 

主　　题：基于模型诊断 极小碰集 集合枚举树 辅助剪枝树 无解空间剪枝 

摘      要：在结合SE-Tree计算集合簇极小碰集的过程中,现有算法会对大量不会产生碰集的冗余节点进行访问.这无疑将影响算法的效率,冗余节点比例越高,影响越大.通过对SE-Tree中叶节点的特殊性质的分析,并结合现有碰集算法有解空间中冗余节点的特征,提出非解冗余节点概念.在对SE-Tree的结构特征进行深入分析基础上,根据非碰集的子集也不是碰集的特点,提出辅助剪枝的概念,通过在剪枝树上设置剪枝判定节点,减少对极小碰集求解过程中无解空间的访问;针对较大规模问题,还提出结合多级辅助剪枝树的极小碰集求解算法,进而较大程度地减少对非解冗余节点的访问;根据多级辅助剪枝树及SE-Tree的结构特征,给出提前终止算法的判定条件,并证明了此算法的正确性.实验结果表明:与效率较高的Boolean算法相比,该算法高效且易于实现,尤其是对规模较大的问题,效率能提升1个数量级.