tailieunhanh - Concepts, Techniques, and Models of Computer Programming - Chapter 12

Constraint Programming Hạn chế các chương trình bao gồm một tập hợp các kỹ thuật để giải quyết sự hài lòng hạn chế Một vấn đề hạn chế sự hài lòng, hoặc CSP, bao gồm một tập hợp các hạn chế trên một tập hợp các biến. Hạn chế, thiết lập này, chỉ đơn giản là một mối quan hệ hợp lý, chẳng hạn như "X là ít hơn so với Y" hoặc "X là một bội số của 3". Vấn đề đầu tiên là tìm xem có tồn tại một giải pháp, mà không nhất thiết phải. | Chapter 12 Constraint Programming Plans within plans within plans within plans. - Dune Frank Herbert 1920-1986 Constraint programming consists of a set of techniques for solving constraint satisfaction A constraint satisfaction problem or CSP consists of a set of constraints on a set of variables. A constraint in this setting is simply a logical relation such as X is less than Y or X is a multiple of 3 . The first problem is to find whether there exists a solution without necessarily constructing it. The second problem is to find one or more solutions. A CSP can always be solved with brute force search. All possible values of all variables are enumerated and each is checked to see whether it is a solution. Except in very small problems the number of candidates is usually too large to enumerate them all. Constraint programming has developed smart ways to solve CSPs which greatly reduce the amount of search needed. This is sufficient to solve many practical problems. For many problems though search cannot be entirely eliminated. Solving CSPs is related to deep questions of intractability. Problems that are known to be intractable will always need some search. The hope of constraint programming is that for the problems that interest us the search component can be reduced to an acceptable level. Constraint programming is qualitatively different from the other programming paradigms that we have seen such as declarative object-oriented and concurrent programming. Compared to these paradigms constraint programming is much closer to the ideal of declarative programming to say what we want without saying how to achieve it. Structure of the chapter This chapter introduces a quite general approach for tackling CSPs called propagate-and-search or propagate-and-distribute. The chapter is structured as follows 1This chapter was co-authored with Raphael Collet. Copyright 2001-3 by P. Van Roy and S. Haridi. All rights reserved. 756 Constraint Programming Section .