A constraint satisfaction problem (CSP) consists of
A finite CSP has a finite set of variables and a finite domain for each variable. Many of the methods considered in this chapter only work for finite CSPs, although some are designed for infinite, even continuous, domains.
The multidimensional aspect of these problems, where each variable can be seen as a separate dimension, makes them difficult to solve but also provides structure that can be exploited.
Given a CSP, there are a number of tasks that can be performed:
CSPs are very common, so it is worth trying to find relatively efficient ways to solve them. Determining whether there is a model for a CSP with finite domains is NP-hard (see box) and no known algorithms exist to solve such problems that do not use exponential time in the worst case. However, just because a problem is NP-hard does not mean that all instances are difficult to solve. Many instances have structure that can be exploited.
Consider the following cryptarithmetic problem as an example,
1) SEND + MORE = MONEY
5 4 3 2 1
S E N D
+ M O R E
c3 c2 c1
----------------------
M O N E Y
SOLUTION:
9 5 6 7
+ 1 0 8 5
-----------------
1 0 6 5 2
VALUES:
S=9
E=5
N=6
D=7
M=1
O=0
R=8
Y=2
- a set of variables,
- a domain for each variable, and
- a set of constraints.
A finite CSP has a finite set of variables and a finite domain for each variable. Many of the methods considered in this chapter only work for finite CSPs, although some are designed for infinite, even continuous, domains.
The multidimensional aspect of these problems, where each variable can be seen as a separate dimension, makes them difficult to solve but also provides structure that can be exploited.
Given a CSP, there are a number of tasks that can be performed:
- Determine whether or not there is a model.
- Find a model.
- Find all of the models or enumerate the models.
- Count the number of models.
- Find the best model, given a measure of how good models are
- Determine whether some statement holds in all models.
CSPs are very common, so it is worth trying to find relatively efficient ways to solve them. Determining whether there is a model for a CSP with finite domains is NP-hard (see box) and no known algorithms exist to solve such problems that do not use exponential time in the worst case. However, just because a problem is NP-hard does not mean that all instances are difficult to solve. Many instances have structure that can be exploited.
Consider the following cryptarithmetic problem as an example,
SEND+MORE=MONEY
5 4 3 2 1
S E N D
+ M O R E
c3 c2 c1
----------------------
M O N E Y
1. From Column 5, M=1, since it is only carry-over possible from sum of 2
single digit number in column 4.
2. To produce a carry from column 4 to column 5 'S + M' is atleast 9 so
'S=8or9' so 'S+M=9or10' & so 'O = 0 or 1'. But 'M=1', so 'O = 0'.
3. If there is carry from Column 3 to 4 then 'E=9' & so 'N=0'. But
'O = 0' so there is no carry & 'S=9' & 'c3=0'.
4. If there is no carry from column 2 to 3 then 'E=N' which is
impossible, therefore there is carry & 'N=E+1' & 'c2=1'.
5. If there is carry from column 1 to 2 then 'N+R=E mod 10' & 'N=E+1'
so 'E+1+R=E mod 10', so 'R=9' but 'S=9', so there must be carry
from column 1 to 2. Therefore 'c1=1' & 'R=8'.
6. To produce carry 'c1=1' from column 1 to 2, we must have 'D+E=10+Y'
as Y cannot be 0/1 so D+E is atleast 12. As D is atmost 7 & E is
atleast 5 (D cannot be 8 or 9 as it is already assigned). N is atmost 7
& 'N=E+1' so 'E=5or6'.
7. If E were 6 & D+E atleast 12 then D would be 7, but 'N=E+1' & N would
also be 7 which is impossible. Therefore 'E=5' & 'N=6'.
8. D+E is atleast 12 for that we get 'D=7' & 'Y=2'.
SOLUTION:
9 5 6 7
+ 1 0 8 5
-----------------
1 0 6 5 2
VALUES:
S=9
E=5
N=6
D=7
M=1
O=0
R=8
Y=2
No comments:
Post a Comment