精选优质文档-倾情为你奉上基于动态极大度的极小碰集求解方法基于动态极大度的极小碰集求解方法张立明欧阳丹彤曾海林(吉林大学计算机科学与技术学院长春)摘要在计算集合簇的碰集时,结合SE-Tree(setenumerationtree)形式化地表达计算过程,逐步生成所有的极小碰集.并在SE-Tree中添加了终止结点,避免了非极小碰集的产生,并且不会因剪枝而丢失正确的解.提出未扩展元素度的概念和结点度的概念,进而在扩展SE-Tree结点时按照未扩展元素度由大到小的顺序扩展,极早地生成集合簇的碰集,减少枚举树生成的结点个数,并且直接根据结点度得出结点对应的集合是否为集合簇的碰集,避免计算集合是否为集合簇的碰集.实验结果表明,该算法程序容易编制且效率较好.关键词基于模型的诊断;极小碰集;SE-Tree;动态极大度;向量交集中图法分类号;TP18现实和理论中的很多问题在某种程度上都可以转换成极小碰集问题.例如:基于模型诊断中极小诊断问题1、极小覆盖集问题、老师与课程(teacherandcourses)问题和规则
