Uninformed search: step through the frontier of paths

What the exam asks you to produce: Execute each of the following search algorithms until termination and write down their frontier at every step. Where appropriate employ the familiar left-to-right order or lexicographic order as tie-breaker. (2023 sample exercise exam, question 1). The graded artefact is the frontier, written as an ordered list of paths, one line per step.

Part 4 chapter: uninformed search Pack index

step 0 of 0
Mistake modes

State space graph

start goal on the path just expanded in the reached set

Frontier the ordered list of paths waiting to be expanded

Bookkeeping

Path just popped (current expansion)

Goal test events this step

Reached set

Result

start

Trace history: what a correct written answer looks like

Conventions this visualiser follows

A node in the search tree is a whole path. it's very important to realize that in this type of problem a note in this tree actually represents an entire path um you took from the starting node. (Lecturer, T2). That is why every frontier entry below is a path and never a single state.

The bracket-free notation is the deck's own shorthand. for simplicity of notation we uh omitted the brackets here. So the paths are shown as a sequence of letters while in principle this should be the notation because it's actually representing a path. (Lecturer, T2, on Part 4 PDF pp.37 to 42). So ABD means the path <A,B,D>.

TREE-SEARCH versus GENERIC-SEARCH. Loop breaking off runs TREE-SEARCH (Part 4 PDF p.9): no memory of visited states, so a graph with a cycle produces an infinite search tree. Loop breaking on runs GENERIC-SEARCH (Part 4 PDF p.27): a path whose last state is already in the reached set is popped but not expanded. in the project this is also referred to as graph search because it works on any graph while the algorithm that we saw previously uh only works on uh on trees. (Lecturer, T2). The deck's slide is blunt about which you should use: Loop breaking (= generic/graph search) standard and very important (otherwise can get lost in infinite paths) (Part 4 PDF p.42).

The reached set here is the deck's global set. The exercise session 2 solutions offer a second scope, per branch (a state may not repeat inside one path) and say The following slides employ approach 2. The two agree on all four problems here, but on the exam say in one line which scope you used.

Left to right, and children go in as a block. Convention: we go from left to right and Paths that extend AB are added to the front of the frontier (in front of AC) (Part 4 PDF p.42). The depth-limited pseudocode on Part 4 PDF p.66 adds each child to start of frontier one at a time, which read literally would reverse them; the deck's own trace on pp.38 to 41 keeps them left to right, so this visualiser inserts the children as an ordered block. Say which you did if you ever have to.

Goal check placement. The generic algorithms test the goal when a path is popped. The depth-limited and iterative deepening pseudocode on Part 4 PDF pp.66 and 67 tests it when a child is generated, so that is the default for iterative deepening here. The exercise session 2 solutions state the limit: the early goal check is only applicable to DFS and BFS, and not algorithms that involve costs (like UCS) or heuristics (like A*). Note also that with the goal test at generation the start node is never goal tested at all.

Tie-breaking in uniform cost search. The frontier is a priority queue on g, the cost from the root. Equal g is broken lexicographically on the path, which is what the exam stem asks for.

Breadth-first optimality. it will also find optimal solutions and this assumes that every step you take... costs the same amount. (Lecturer, T2). Watch problem 2: BFS returns a cost 12 solution where uniform cost search returns cost 10.

Term box

Frontier
The ordered list of paths available for expansion. Its order is the whole algorithm: LIFO (last in, first out) gives depth-first, FIFO (first in, first out) gives breadth-first, a priority queue on g gives uniform cost.
Expanding a path
Removing it from the frontier and generating one extension per neighbour of its last state.
Reached set
The set of states already expanded (the deck also calls these the explored nodes). Only GENERIC-SEARCH keeps one.
g(n)
Cost from the root of the search tree to the end of the path, that is, the sum of the arc costs along the path.
Depth limit k
A path of length k (k arcs) is expanded only while k is strictly below the limit, so a limit of 1 expands only the start node.
Meeting test (bidirectional)
A generated neighbour is checked against every path in the other direction's frontier; a hit ends the search and the two half paths are joined.