{Red, Blue, Green} to each region of the map below, so that no two regions sharing a border have the same colour.
Figure (a) shows the uncoloured map with five regions A, B, C, D, E; Figure (b) shows one valid 3-colouring.
Specify the five components: State Space, Initial State, Actions / Transition Model, Goal Test, and Path Cost.
Adjacency (shared border): A–B, A–C, B–D, B–E, C–D, D–E. The pairs A–D and B–C touch only at a corner, so they are not adjacent.
The set of all assignments of colours to the five regions. A state is a tuple
(colour(A), colour(B), colour(C), colour(D), colour(E)), where each entry is in {R, B, G} or "uncoloured".
Counting partial colourings (each region R/B/G/uncoloured) gives 4⁵ = 1024 states; counting only fully-coloured maps gives 3⁵ = 243. Either is accepted, as is "the set of all colourings of the map".
All five regions are uncoloured: the empty assignment (–, –, –, –, –).
ACTIONS(s): choose an uncoloured region and assign it a colour from {R, B, G} that no already-coloured neighbour uses.
RESULT(s, a): the same state with that region now holding the chosen colour.
The relaxed version (assign any colour and let the goal test reject conflicts) is also accepted.
A state is a goal iff (i) all five regions are coloured and (ii) no two adjacent regions share a colour (adjacency: A–B, A–C, B–D, B–E, C–D, D–E).
1 per assignment (each colouring step costs 1), so a solution that colours all five regions has path cost 5. Map colouring is a CSP and we only care about reaching a goal state, so "uniform", "0", or "irrelevant for a CSP" are all accepted.
Edges (undirected): S–A 2, S–B 5, A–C 3, A–D 1, C–G 5, D–G 4, B–E 2, E–G 1.
S.Expanding from S, with children listed alphabetically (using a reached set so each state appears once):
The tree-search version (no reached set), in which G appears as a separate leaf on each of the three root-to-goal paths (via C, via D, via E), is equally accepted; it matches the "traversing a graph as a tree" figure in the lecture notes.
DFS uses a stack (LIFO) and expands children alphabetically. From S push A, B; expand A first; from A push C, D; expand C; C leads to G; goal found.
Order of expansion:
Path to goal:
DFS ignores edge weights, so it returns this path even though its cost (2+3+5 = 10) is not optimal. (The question asks only for the order and the path, not a cost.)
S, A, C, G (taking the B branch first, e.g. S-B-E-G, is the common error); 8 pts for the path S → A → C → G. Listing the full traversal is fine as long as the A-branch is taken first.UCS expands the frontier node with the least path cost g(n) first, breaking ties alphabetically, and applies the goal test when a node is removed for expansion (not when generated). Trace of the priority queue:
| Expand (g) | Frontier afterwards (node : g) |
|---|---|
| S (0) | A:2, B:5 |
| A (2) | D:3, B:5, C:5 |
| D (3) | B:5, C:5, G:7 |
| B (5) | C:5, E:7, G:7 |
| C (5) | E:7, G:7, G:10 (G via C = 10, not better) |
| E (7) | G:7, G:8, G:10 (G via E = 8, not better) |
| G (7) | goal test passes, path returned |
Order of expansion:
Path to goal:
Total path cost:
S, A, D, B, C, E, G. A tie handled in the wrong order (B/C at g=5, or E/G at g=7) loses only a little; 0 if UCS is stopped the moment G is first generated rather than expanded.S → A → D → G.7.