基于分解的正向相容算法研究

作     者：韩文成 

作者单位：吉林大学 

学位级别：硕士

导师姓名：李占山

授予年度：2010年

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

主      题：约束满足问题 正向检查 分解 约束求解 

摘      要：约束满足问题是人工智能领域一个非常重要的研究领域。正向相容算法是约束满足问题求解的一个重要求解分支。本文的主要研究内容是基于对正向相容算法的研究,利用分解的相关理论知识,在结点赋值后不考虑已经赋值结点和当前结点将剩余的约束图进行分解成若干个连通子图,分别对这些连通子图进行求解,最后将连通子图解和变量赋值组合成一组解,进而求出约束满足问题的全部解。基于此思想,本文提出了SBT-FC算法,并证明了算法的正确性、完备性、最坏情况下的时间复杂度和最坏情况下的空间复杂度。然后本文根据对SBT-FC算法的研究,提出了将约束分解从求解过程中提取出来独立运算并存储在特定的数据结构中,求解时直接访问这些数据结构直接得到分解的信息的思想即SBT-FC的扩展算法ESBT-FC算法。最后我们设计并实现了这些算法,并与经典的正向相容算法和主流的求解算法相比较。实验结果表明在大多数情况下ESBT-FC算法优于SBT-FC算法,SBT-FC算法优于BT-FC和BDH-FC算法。