Section 5.1. Constraint Satisfaction Problems 139 It is fairly easy to see that a CSP can be given an incremental formulation as a standard search problem as follows Initial state:the empty assignment in which all variables are unassigned. Successor function:a value can be assigned to any unassigned variable,provided that it does not conflict with previously assigned variables Goal test:the curent assignment is complete. Path cost:a constant cost (e.g..1)for every step. earch algor thaplete assignment and therelore appears at depth n if therear nds are popu CSP 2)t that which eve a night the co forhSth 53 riables that are 1 ems are o f this n Chapt te-domain CS where each queen in c cach v ne do 2,6 .8 th main size of an then hat is,exponential in the Ite-a BOOLEAN CSPS include Boolean CSPs, whos can be e or fals Boolean CSP as special ca NP-complete probler ms,such as 3s (See Chapter 7.)Int cas ,therefore we cannot expect to solve finite-domain CSPs in less than exponentia In most practical applications,however,general-purpose CSP algorithms can solve problems orders ofmagnitde larger than those solvable via the general-purpose search algorithms that we saw in Chapter NFINTE DOMAINS Discrete variables can also have infinite domains-for example,the set of integers o the set of strings.For example,when scheduling construction jobs onto a calendar,each job's start date is a variable and the possible values are integer numbers of days from the current date.With infinite domains.it is no longer possible to describe constraints by enumerating aR all allowed combinations of values.Instead,a constraint language must be used.For ex- ample,if Job.which takes five days,must precede Jobs.then we would need a constraint language of algebraic inequalities such as StartJob+5<StartJob3.It is also no longer possible to solve such constraints by enumerating all possible assignments,because there are nfinitely many of them.Special solution algorithms(which we will not discuss here)exist ONSTPAINTS for linear constraints on integer variables-that is,constraints,such as the one just given, in which each variable appears only in linear form.It can be shown that no algorithm exists &8棉S for solving general nonlinear constraints on integer variables.In some cases.we can reduce integer constraint problems to finite-domain problems simply by bounding the values of all the variables.For example,in a scheduling problem,we can set an upper bound equal to the total length of all the jobs to be scheduled. CONANSOUS Constraint satisfaction problems with continuous domains are very common in the real world and are widely studied in the field of operations research.For example,the scheduling Section 5.1. Constraint Satisfaction Problems 139 It is fairly easy to see that a CSP can be given an incremental formulation as a standard search problem as follows: ♦ Initial state: the empty assignment {}, in which all variables are unassigned. ♦ Successor function: a value can be assigned to any unassigned variable, provided that it does not conflict with previously assigned variables. ♦ Goal test: the current assignment is complete. ♦ Path cost: a constant cost (e.g., 1) for every step. Every solution must be a complete assignment and therefore appears at depth n if there are n variables. Furthermore, the search tree extends only to depth n. For these reasons, depth- first search algorithms are popular for CSPs. (See Section 5.2.) It is also the case that the path by which a solution is reached is irrelevant. Hence, we can also use a complete-state formulation, in which every state is a complete assignment that might or might not satisfy the constraints. Local search methods work well for this formulation. (See Section 5.3.) FINITE DOMAINS The simplest kind of CSP involves variables that are discrete and have finite domains. Map-coloring problems are of this kind. The 8-queens problem described in Chapter 3 can also be viewed as a finite-domain CSP, where the variables Q1, . . . , Q8 are the positions of each queen in columns 1, . . . , 8 and each variable has the domain {1, 2, 3, 4, 5, 6, 7, 8}. If the maximum domain size of any variable in a CSP is d, then the number of possible complete assignments is O(d n )—that is, exponential in the number of variables. Finite-domain CSPs BOOLEAN CSPS include Boolean CSPs, whose variables can be either true or false. Boolean CSPs include as special cases some NP-complete problems, such as 3SAT. (See Chapter 7.) In the worst case, therefore, we cannot expect to solve finite-domain CSPs in less than exponential time. In most practical applications, however, general-purpose CSP algorithms can solve problems orders of magnitude larger than those solvable via the general-purpose search algorithms that we saw in Chapter 3. INFINITE DOMAINS Discrete variables can also have infinite domains—for example, the set of integers or the set of strings. For example, when scheduling construction jobs onto a calendar, each job’s start date is a variable and the possible values are integer numbers of days from the current date. With infinite domains, it is no longer possible to describe constraints by enumerating all allowed combinations of values. Instead, a constraint language must be used. For ex- CONSTRAINT LANGUAGE ample, if Job1, which takes five days, must precede Job3, then we would need a constraint language of algebraic inequalities such as StartJob1 + 5 ≤ StartJob3. It is also no longer possible to solve such constraints by enumerating all possible assignments, because there are infinitely many of them. Special solution algorithms (which we will not discuss here) exist for linear constraints on integer variables—that is, constraints, such as the one just given, LINEAR CONSTRAINTS in which each variable appears only in linear form. It can be shown that no algorithm exists for solving general nonlinear constraints on integer variables. In some cases, we can reduce NONLINEAR CONSTRAINTS integer constraint problems to finite-domain problems simply by bounding the values of all the variables. For example, in a scheduling problem, we can set an upper bound equal to the total length of all the jobs to be scheduled. Constraintsatisfaction problems with continuous domains are very common in the real CONTINUOUS DOMAINS world and are widely studied in the field of operations research. For example, the scheduling