COMP9414 Chap.3 States, Trees and Frontiers
States, Trees and Frontiers
Search depends on a formulation before it depends on a data structure. This chapter defines the initial state, successor function, goal test and path cost, then separates the state-space graph from the search tree generated from a start. It shows why frontier entries carry path history, how repeated-state handling depends on the problem and cost rule, and how to debug a trace at the first illegal update.
What this chapter covers
- 01
Initial state, successors, goal test and path cost
- 02
State-space graphs with one node per world state
- 03
Search trees that unfold alternative plan histories
- 04
Frontier entries with parents, depth and cumulative cost
- 05
Discovery, expansion and returned-path events
- 06
Repeated-state handling under weighted and unweighted search
Worked example · free
Trace two FIFO expansions
- +1Remove S, fail the goal test and insert paths S-A then S-B.
- +1Remove S-A and insert S-A-C, producing frontier S-B then S-A-C.
- +1Remove S-B, suppress its already discovered C successor and insert S-B-G.
- +1Remove C before G under FIFO order, then return the parent chain S-B-G when G is removed.
Key terms
- Problem formulation
- A specification of state, legal successors, goal test and path cost.
- State-space graph
- A graph whose nodes are world states and whose edges represent legal successor transitions.
- Search tree
- A path-based unfolding from the start where one world state can appear under several histories.
- Frontier
- The generated partial paths that are waiting to be selected for expansion.
- Expansion order
- The sequence in which frontier entries are removed and their successors generated.
States, Trees and Frontiers FAQ
What is the difference between a graph and a search tree?
The graph represents each world state and its legal transitions. The search tree represents paths from the start, so the same world state can appear more than once under different parents. A tree node therefore carries plan history as well as a state label.
What should a frontier entry contain?
It needs enough information to reconstruct the candidate plan, usually a state plus parent or full path and depth. Cost-sensitive methods also store cumulative cost and priority. A bare state label cannot explain how the search reached the node.
When may a repeated state be ignored?
That depends on the algorithm and cost rule. Discovery-time suppression works for standard BFS graph search on an unweighted problem. UCS and A* must compare the new cumulative cost and retain a later route when it improves the best known value.
Exam move
For each practice graph, write the problem formulation before tracing. Label the state information, successor order, goal-test timing and cost definition. Draw the fixed state graph on one side and the evolving frontier table on the other. Every frontier row should show the path or parent, depth and cost where relevant.
After each expansion, check an invariant: FIFO depths should progress by layer, a stack should select the latest path, and a priority method should remove the lowest valid priority. Report expansion order, returned path and actual path cost as three different outputs. To practise state design, invent two histories that end with the same proposed state and ask whether every future choice is equivalent.
If not, add the missing variable; if yes, the abstraction may safely merge them. Repeat one trace with the goal test moved from generation to removal and record exactly which reported sequence changes. Then switch between tree search and graph search on a graph with a cycle, marking whether a repeated label denotes a duplicate world state or a distinct path node.
For weighted problems, keep a best-cost table beside the frontier and practise replacing a parent only on strict improvement. Reconstruct the returned plan by following parents backwards instead of reading the expansion order. Create one deliberately faulty trace by inserting a successor twice or using the wrong neighbour order, then locate the first step that violates the chosen convention.
Finally, defend the state representation by listing one omitted detail that is safely constant and one detail whose omission would merge nonequivalent futures. This debugging practice makes the data structure and its semantics visible together. Add a compression exercise: rewrite a path-carrying trace using only parent pointers and a frontier entry, then reconstruct the solution after the goal is removed.
Compare the memory obligations without confusing the storage scheme with the explored state space. On another copy, erase the explored set and follow a cycle for several steps to make repeated-state control concrete. Label each duplicate decision with the exact identity test used by the implementation.
Working through States, Trees and Frontiers in COMP9414? Sia is AskSia’s AI Computer Science tutor — ask any COMP9414 States, Trees and Frontiers question and get a clear, step-by-step explanation grounded in how COMP9414 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.
