| << Prev | - Up - | Next >> |
Where constraint programming really shines is in solving constraint satisfaction problems where constraint propagation very effectively helps pruning the search space. In this chapter, we explain how constraint satisfaction problems (henceforth CSPs) are solved by means of constraint programming.
Much more is possible with constraint programming; in particular, using the record constraints (aka open feature structures) traditionally favored by computational linguists. However, record constraints do not lead to formulations with especially strong constraint propagation. For 2 reasons: (1) record constraints cannot represent negative information, (2) they only take effect when record structure appears (i.e. they are passive). We entirely shun them in this course and emphasize instead encodings using integers and sets of integers that provide very strong and efficient constraint propagation.
| << Prev | - Up - | Next >> |