Abstract:

In view of constraintbased configuration problems  solved by the classic algorithms which are used to solve constraint satisfaction problems, the authors proposed the notion of model correctness, then analysed the properties of acycle configuration, gave a backtrackfree search algorithm for solving configurations, used the arc consistency technologies to delete the redundant values from the domains of related variables so as to guide the users to configure products, and proved the correctness of the algorithm. Finally, the  two popular algorithms to compute the explanations were applied to acycle configurations.

Key words: constraint satisfaction problem, configuration problem, model correctness, arc consistency, explanation