Uninformed Search Methods

Question 1

Give some examples of problems formulated as a state space search.

Answer 1

8-puzzle 
Route finding problem 
8-queens problem
Making a timetable 
Production scheduling 
Grammatical parsing 
Interpretation of sensory data 
Modelling from measured data 
Finding scientific theories that account for experimental data

Question 2

What is an uninformed search? Give some examples.

Answer 2

Systematically searching a complete graph, unguided, e.g. depth-first, breadth-first, iterative deepening, bi-directional search.

Question 3

How do you evaluate a search strategy?

Answer 3

Completeness: does it always find a solution if one exists?

Time complexity: number of nodes generated.

Space complexity: maximum number of nodes in memory.

Optimality: does it always find a least-cost solution?

Question 4

What is depth-first search?

Describe its properties in terms of completeness, time complexity, space complexity, and optimality.

Answer 4

Start at the root. Explore each branch as far as possible before backtracking or finding the solution.

Completeness: no, susceptible to infinite loops
Time complexity: high as in the worst case visits all states
Space complexity: low as it remembers only one path at a time
Optimality: no, not guaranteed to find shortest solution first

Question 5

What is breadth-first search?

Describe its properties in terms of completeness, time complexity, space complexity, and optimality.

Answer 5

Completes one level before moving on to the next level. Guaranteed to find shortest solution first.

Completeness: yes
Time complexity: high as in the worst case visits all states
Space complexity: high as it remembers all paths
Optimality: yes

Question 6

What is iterative deepening?

Describe its properties in terms of completeness, time complexity, space complexity, and optimality.

Answer 6

Start with a small MaxDepth and increase MaxDepth until a solution is found, with depth-first search.

Completeness: yes
Time complexity: high as in the worst case visits all states
Space complexity: low as it remembers only one path each time
Optimality: yes as it finds the shortest solution first

Question 7

What is a bidirectional search?

Answer 7

Search progress from both start and goal states. using standard search techniques.

Question 8

What is a backward search?

Answer 8

Search from goal state to start state. New goal condition satisfied by start node. Only applicable if goal node(s) known.