论文摘要
一个约束满足问题是否易于求解是与它的结构密切相关的。研究表明有着限制结构的约束满足问题是易于处理的,对于结构为无环的约束满足问题可以在多项式时间内求解。因此对于约束分解方法的研究也就成了约束满足问题领域的一个热门话题之一。约束分解方法有多种,它们的基本原理都是将一个有环约束满足问题P通过分解转化成一个等价的无环约束满足问题P’。本文的主要研究内容是基于约束满足问题的超树分解方法的研究,提出了一种新的超树分解方法：分割的超树分解（Separated HyperTree Decomposition--SHTD）,它对超树分解的结构作了更严格的控制,是一类特殊的超树分解,因此它也是易于处理的。基于分割的超树分解所具有的结构特征和现有超树分解算法的不足,我们还提出了一种新的超树分解算法—基于分割的超树分解算法（Separate-Based Hypertree decomposition）sht-k-decomp,它是基于Gottlob等人的det-k-decomp算法的,它通过进一步限制separator的选择空间和引入同构的概念来加速分解过程的执行,但应该注意到由sht-k-decomp算法构造的超树分解并不是分割的超树分解。实验结果表明,分割的超树分解是一类分解效率较高的超树分解,且基于分割的超树分解算法sht-k-decomp算法是优于det-k-decomp算法的。