[2021] COMPSCI 367 Artificial Intelligence - Final Exam - Question 17 Backtracking Algorithm
17 The following graph shows the adjacency of regions in Western Canada. You’d like to give a colour from {R,G,B} to each node so that no two adjacent nodes get the same colour.
We model this problem as a CSP with variables: YU, NT, BC, AL, NU, SA, MA, whose domains are all {R,G,B} and the constraints indicate that any adjacent nodes would be assigned different values.
- Starting from the partial assignment f(AL)=B, f(MA)=R, and assuming the initial domain of all other nodes is {R,G,B}, apply the arc consistency (AC3) algorithm. Write down the remaining values in the domain of each node after the algorithm is completed.
- Starting from the node YU with assignment f(YU)=R, apply the backtracking algorithm, where the Select-Unassigned-Var operation is implemented using two heuristics: First, apply MRV heuristic to choose a value, and then use the degree heuristic as a tie breaker. Write down, in the same order as done by the backtracking algorithm, the list of nodes and their assigned colours.
The answers to both questions are meant to go into the one textbox at the bottom of the question.
Fill in your answer here
Get the Solution to This Question
WeChat (微信)
WhatsApp
