Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/40380
Title: A lazy divide & conquer approach to constraint solving
Authors: Anand, S.
Chin, W.-N. 
Khoo, S.-C. 
Issue Date: 2002
Source: Anand, S.,Chin, W.-N.,Khoo, S.-C. (2002). A lazy divide & conquer approach to constraint solving. Proceedings of the International Conference on Tools with Artificial Intelligence : 91-100. ScholarBank@NUS Repository.
Abstract: 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 subproblems. 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.
Source Title: Proceedings of the International Conference on Tools with Artificial Intelligence
URI: http://scholarbank.nus.edu.sg/handle/10635/40380
ISSN: 10636730
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

52
checked on Dec 16, 2017

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.