Search Strategies: The Setup

Source: Unit 1 §2

In a search problem you are given a graph and a goal, but not the path. At every moment there is a frontier of nodes you could expand next, and the only decision you ever make is which one to take. That decision is the strategy.

≡FactsDefinition

A search strategy is defined by the order in which nodes are expanded. Nothing else. Two algorithms that expand the same nodes in the same order are the same strategy, whatever data structure they use to get there.

The four criteria

Criterion	The question it answers
Completeness	Does it always find a solution if one exists?
Time complexity	Number of nodes generated.
Space complexity	Maximum number of nodes held in memory.
Optimality	Does it always find the least-cost solution?

Time and space are always quoted in terms of three quantities of the search tree, so learn the symbols before the formulas.

≡FactsThe three symbols

• b - the maximum branching factor, the most successors any node has.
• d - the depth of the shallowest (least-cost) solution.
• m - the maximum depth of the state space, which may be infinite.

The skeleton of any search

→StepsThe loop every strategy runs

1. Define the initial state.
2. Find all possible actions from that state.
3. Take a step, chosen by the algorithm.
4. Move to the new state.
5. Test whether the new state is the goal.
6. Repeat.

⚠GotchaDefining the state is the hard part

Steps 2 to 6 are mechanical. Step 1 is where real problems die: in the real world, writing down what counts as a state, exhaustively and finitely, can be absurdly complex. An exam question that hands you a clean state space has already done the difficult half of the work for you.

Formalising a search problem

Every search problem has five components, plus two bookkeeping structures.

Component	Symbol	Meaning
States	S / Q	A set of finite states, the whole state space. The notes use both letters; Q is the less overloaded one, since S is also the start state.
Start state	S	A non-empty subset of Q, the set of start states.
Goal state	G	A non-empty subset of Q, the set of goal states.
Action	-	A possible move, f(Sₜ₋₁, a) → Sₜ.
Cost	-	A function returning a positive number for moving from s to s', defined only if s' is a successor of s.

≡FactsThe supporting structures

• Frontier (Q) - the queue of nodes waiting to be expanded. It is a linear structure with a defined order, and that order is the whole strategy.
• Explored set - a record of the nodes already visited, so the search does not redo work or loop.
• Back pointer - each node's record of its predecessor, used to reconstruct the path once the goal is found.

Search finds the goal going forwards, but reports the path going backwards: every node remembers who generated it.

A worked framing: the woman and the shop

A woman needs to reach a shop from home on a 16-cell grid.

Component	Value
States	all 16 locations
Start state	home
Actions	up, left, down, right
End state	either of the shops
Cost	1 per move

The two families

The only difference between the two families is whether the strategy is allowed to know anything the problem definition did not state.