优化简单表缩减算法求解因子分解编码实例

表约束在约束程序(constraint programming,简称CP)中被广泛研究.目前,求解表约束问题效率最高的算法是CT(compact-table)和STRbit(simple tabular reduction bit).它们在搜索过程中维持广义弧相容(generalized arc consistency,简称GAC).完全成对相容(full pairwise consistency,简称fPWC)是一种强于GAC的相容性关系,目前,实现fPWC效率最高的算法是PW-CT,但是它无法直接在通用的求解器上实现.因子分解编码(factor-decomposition encoding,简称FDE)是实现fPWC的一种编码方式,通常和简单表缩减(STR)算法一起来使用.当前效率最高的STR算法使用了bitset的数据结构,用这些算法来求解FDE实例可能会造成内存溢出.提出了STRFDE算法——一种使用bitset结构来求解FDE实例的方法.它结合了CT和STRbit的优势,在保证求解效率的同时,使占用的内存尽可能小.实验结果表明,在许多存在非平凡相交的实例上,该算法是有竞争力的.