摘要:表约束在约束程序（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的优势，在保证求解效率的同时，使占用的内存尽可能小.实验结果表明，在许多存在非平凡相交的实例上，该算法是有竞争力的.



Abstract:Table constraints are widely studied in constraint programming (CP). At present, the most efficient algorithms for solving table constraint problems are compact-table (CT) and simple tabular reduction bit (STRbit), which maintain generalized arc consistency (GAC) during the search process. Full pairwise consistency (fPWC) is a consistency that is stronger than GAC. The most efficient algorithm for maintaining fPWC is PW-CT which is difficult to implement in general solver. Factor-decomposition encoding (FDE) is an encoding method that implements fPWC and is usually used together with STR. The current STR algorithms that use bitset may cause memory overflow issues to solve FDE instances. This study proposes STRFDE, a new algorithm using bitset for solving FDE instances. It combines the advantages of CT and STRbit that makes the memory as little as possible while ensuring the efficiency of solving. Experimental results show that the proposed algorithm is competitive over a variety of instances with non-trivial intersections.



PDF全文下载地址:

http://jos.org.cn/jos/article/pdf/6094