Constraint satisfaction problem

Question 1

Describe the constraint satisfaction problem.

Answer 1

In the constraint satisfaction problem, we have some nodes 1 .. .n with domain D_1 .. .D_n.

The domain can be both discrete and continuous.

The problem has constraints, often written as the edges between nodes, eg.
C(1,3) = x_1+x_3> 10
C(2,3) = x_2 - x_3 = 10

Question 2

What are some applications of the constraint satisfaction problem?

Answer 2

• Timetabling
• Graph coloring problem
• N-queen problem

Question 3

Describe min-conflicts method in pseudo code.

Answer 3

Number_of_tries = 0;
while ( Number_of_constrained_violated > 0 AND Number_of_tries < MAX_Tries ) DO
__Select at a random a variable X that violates a constraint;
__For each value of X DO
____Determine the value of the selected variable that results in the
____highest gain ;
__End for
__Update the solution if it is beter than the previous one;
__Number_of_tries += 1;
End While

Question 4

Describe the GCSP (greedy CSP) in pseudo code.

Answer 4

Number_of_tries = 0;

while ( Number_of_constrained_violated > 0 AND Number_of_tries < MAX_Tries ) DO
__For each variable in the set of variables DO
____/* Selects the variable which will produce the higehst gain */
____Select at random a value ;
____Determine the gain;
____Keep the best gain sofar;
__End for
__Select the variable having the higest gain
__Update the solution ;
__Number_of_tries += 1;
End While

Question 5

Describe the multilevel CSP algorithm in pseudo code.

Answer 5

For ( level = Number_of_Levels ; level > 0 ; level–) /* Number of levels )
Start:
__Number_of_tries = 0;
__while ( Number_of_constrained_violated > 0 AND Number_of_tries < MAX_Tries )
__Start:
____Select at random a specified number of variables ;
__/* Number of variables = Number of Levels */
____Choose at random a value for each choosen variable;
____Calculate the gain;
____Update the solution if the current solution is better than the
____previous one;
____Number_of_tries += 1;
__End
END