Research On Consistency Algorithm On Table Constraint Based On Reducing Traversal

Constraint programming is an important part of artificial intelligence,and it is a good and general framework.It provides efficient models and algorithms to solve many practical problems.It is widely used in many fields,such as resource allocation,biological information,plan scheduling,etc.It abstracts the problem into a constraint model,which consists of constraint set,variable set and domain set.It can solve constraint satisfaction problem by two main techniques,backtracking search and constraint propagation.Compatibility technology is the most widely used,efficient and successful technical method in constraint propagation.It is the core and key to solve constraint satisfaction problem.When local inconsistent values are removed in one constraint,the constraint is transferred with the common variables.By the method,compatibility technology removes the value that is not the solution and achieve global consistency.So the problem size is simplified and the solution efficiency is improved.Generalized arc consistency technique is considered as an effective method to solve the non-binary constraint satisfaction problem.Simple table reduction(STR)algorithm and its optimization algorithm STR2 show a good performance in practice.They are advanced filtering techniques for implementing generalized arc compatibility on positive table constraints.Recently,the dual table is presented as a new constraint representation.Consequently,the consistency algorithm STR3 based on the dual table is proposed.It utilizes a new solution optimization approach which can reduce retrieval by discarding unrelated tuples to reduce the number of traversals.It is a path-optimal algorithm.STR2 and STR3 have their own advantages in CSP with different structural characteristics.This method based on discarding irrelevant tuples can only be applied to positive table constraints.It can not be directly applied to the negative table.Therefore,this paper inspiredby the STR3 algorithm,a consistency algorithm technology STRN3 based on negative dual table is proposed.It is also optimized by giving up traversing irrelevant tuples.Saving the support tuple in the positive table,the valid tuple in the table is the support of value.Saving the conflict tuple in the negative table,the support of the value can not be traversed directly from the constraint table.Therefore,both the STRN algorithm and the STRN3 algorithm are relatively complex to find support of values.The biggest optimization for STRN3 is the way of finding support of values.STR-N needs to traverse all valid tuples in each constraint transfer before it can determine the presence or absence of support by calculating conflict tuples.The STRN3 algorithm does not have to traverse all valid tuples every time.Based on the tuples that are traversed by the last constraint transfer,it continues to search for the minimum effective support interval to determine whether the support of value exists.In this way,in the process of solving the entire constraint satisfaction problem,each dual table is only traversed at most once.As a result,the number of traversals is reduced,the algorithm is optimized,and the efficiency is improved.The experiments show that STRN3 is competitive with STR-N when the average size of tables is not reduced too drastically during search and STRN3 is competitive with STR3 when conflict tuples are less in constraint networks.