14th IEEE International Conference on Tools with Artificial Intelligence (ICTAI'02) A Lazy Divide and Conquer Approach to Constraint Solving Washington, DC November 04-November 06 ISBN: 0-7695-1849-4
Divide and conquer strategy enables a problem to be divided into subproblems, which are solved independently and later combined to form the solutions of the original problem. In solving constraint satisfaction problems, however, divide and conquer technique has not been shown to be effective. Because, it is not possible to cleanly divide a problem into independent subproblems in the presence of constraints that involve variables belonging to different sub-problems. Consequently, solutions of one subproblem may prune some solutions of another subproblem, making those solutions of the latter subproblem redundant. In this paper, we propose a divide and conquer approach to constraint solving in a lazy evaluation framework. In this framework, a subproblem is solved on demand, which eliminates redundant consistency checks. Moreover, once solved, the solutions of a subproblem can be reused in the satisfaction of various global constraints connecting this subproblem with others, thus reducing the search space. We also demonstrate the effectiveness of our algorithm in solving a practical problem: finding all instances of a user-defined pattern in stock market price charts.
Citation:
Saswat Anand, Wei-Ngan Chin, Siau-Cheng Khoo, "A Lazy Divide and Conquer Approach to Constraint Solving," ictai, pp.91, 14th IEEE International Conference on Tools with Artificial Intelligence (ICTAI'02), 2002 Usage of this product signifies your acceptance of the Terms of Use. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||