The Research Of Consistency Algorithms For Table Constraint

One of the most efficient complement algorithms for solving constraint satisfaction problem is that using consistencies to reduce the search space during backtrack search. For non-binary constraint, generalized arc consistency(GAC) is the most common consistency, and simple tabular reduction(STR) algorithm and its optimized version STR2 are the state-of-the-art algorithms to maintain GAC on table constraint. Recently, A new constraint representation,called dual table, is proposed, and a path-optimal algorithm STR3 is given to maintain GAC on dual table, STR3 is a complementary algorithm to STR2. In this paper, we propose a new constraint representation by using bit vectors to represent the dual table, called bit table, and a new GAC algorithm STRbit is proposed to maintain GAC on bit table. In addition, we give the bit c-table by combining bit table with c-table, on many instances, bit c-table can get a large compression ratio, even the compression ratio can be greater than 1000. Then A efficient algorithm STRbit-C is proposed to maintain GAC on bit c-table. On many instance series, our new GAC algorithms(STRbit and STRbit-C) can be faster than the state-of-the-art algorithms(in some case, by an order magnitude), where the STR2, STR3, MDDc and their c-table versions STR2-C and STR3-C are the state-of-the-art algorithms.Recently, Many algorithms are proposed to maintain the full pair-wise consistency(FPWC) during search, and e STR algorithm using of the STR algorithm frame is one of the most efficient algorithm, the time complexity of PW checking in e STR algorithm is only O(1)by maintaining ctr counter. There are many redundant checking in e STR algorithm. The tuple in constraint table only need to check the PW support on some neighborhood constraints, as such, we propose a data structure PWsup to record the neighborhood constraints which need to be checked. In addition, the validity of some variables in constraint scope needn’t to be checked, correspondingly, we give the minimal constraint scope to record the variables which need to be checked. After using the two data structures to optimize the e STR algorithm, the time and space cost of optimized algorithm are less than that of original e STR algorithm on many instance series.