Simple Ruby Constraint Satisfaction Problem Library August 13th, 2007

Constraint Satisfaction Problem (CSP) is a interesting topic. This was my thesis topic. CSP is something like this. Let’s say you have three variables, a, b, and c. Variable a has domain from 1 to 10 (integer). That means you can only give one of these values (1, 2, 3, 4, 5, 6, 7, 8, 9, 10) to variable a. Variable b has domain from 5 to 15 (integer). Variable c has domain from 9 to 12 (integer). Domain is something like valid values for its variable. Then you have constraint. Let’s say we have two constraint. The first is a > c. The second is b is same as c. So we need to find the solution which need to satisfy these two constraints. Solution is described as process to give values to these three variables in one time. Giving a 2, b 7, and c 11 value is one of solution. But this is not a valid solution because it does not satisfy the first constraint. The a value (2) is lower than c value (11). The valid solution is giving a 10, b, 9, and c 9.

Read the rest of this entry

0 comments »