Question 1: Short answer
mediumAI-checkedSearch & PlanningUniform-cost search runs as a graph search from S to G on an undirected graph with these edge costs. The goal test is applied when a node is taken off the frontier, and ties are broken alphabetically.
| Edge | S–A | S–B | A–C | A–D | B–C | B–D | C–E | D–G | E–G |
|---|---|---|---|---|---|---|---|---|---|
| Cost | 2 | 3 | 4 | 7 | 2 | 5 | 3 | 3 | 4 |
How many nodes does UCS expand before it takes G off the frontier? Count S, but not G.