(b) Suppose that you are given the following map, corresponding to the CSP containing variables {A,...

 

Transcribed Image Text:

(b) Suppose that you are given the following map, corresponding to the CSP containing variables {A, B, C, D, E, F} such that the variables represent regions in the map, and regions should be coloured from the set {red, green, blue} with the constraint that adjacent regions must not be the same colour. FED CBA i. Draw a constraint graph for this problem. [3] ii. Use the backtracking algorithm with application of appropriate heuristics to find a solution to this problem. Show all the steps carried out by the algorithm. [6] (c) Explain how cutset conditioning could be used in the following constraint graph to make the search more efficient, and state the upper bound on the number of nodes expanded with and without cutset conditioning. Assume that each variable has the same domain, which is of size 3. [6] E A-B-C-D F G -HL- K (b) Suppose that you are given the following map, corresponding to the CSP containing variables {A, B, C, D, E, F} such that the variables represent regions in the map, and regions should be coloured from the set {red, green, blue} with the constraint that adjacent regions must not be the same colour. FED CBA i. Draw a constraint graph for this problem. [3] ii. Use the backtracking algorithm with application of appropriate heuristics to find a solution to this problem. Show all the steps carried out by the algorithm. [6] (c) Explain how cutset conditioning could be used in the following constraint graph to make the search more efficient, and state the upper bound on the number of nodes expanded with and without cutset conditioning. Assume that each variable has the same domain, which is of size 3. [6] E A-B-C-D F G -HL- K