基于分割的超树分解方法

Separation-Based Hypertree Decomposition

基于det-k-decomp算法,通过引入同构的概念和对separator选择空间的进一步限制,提出一类新的超树分解:分割的超树分解,并提出一种具有较小超树宽度的超树分解方法:基于分割的超树分解———sht-k-decomp,该算法能有效提高约束满足问题的求解效率.实验结果表明,sht-k-decomp算法多数情况下效率高于det-k-decomp算法.

Based on det-k-decomp algorithm,along with the noting isomorphic component and reducing the search space for an appropriate separator,the authors presented a new class of hypertree decomposition：separated hypertree decomposition and presented a new tractable hypertree decomposition algorithm——sht-k-decomp,which can improve the efficiency of constrain satisfaction problem solving effectively.The experimental results on most instances show that our method outperforms det-k-decomp.