Search Introduction

Question 1

What are the different states that a problem can be in?

Answer 1

Start / Initial State
Goal State

Question 2

What does the state space cover?

Answer 2

All possible outcomes at each state

Question 3

What are operators for?

Answer 3

They allow movement between states. i.e. a legal move on a chess board

Question 4

Do search algorithms store the whole tree?

Answer 4

Some do, some don’t.

Question 5

What are the main steps of finding a solution to a problem?

Answer 5

Get current state
Check if that is the goal state
Use operators to expand to all next nodes
Pick which node to go to using search techniques

Question 6

What is a no information search called?

Answer 6

Blind or uninformed searches

Question 7

What is a search with information called?

Answer 7

Heuristic or informed search

Question 8

What are the methods we use to evaluate search methods?

Answer 8

Time complexity
Space complexity
Optimality
Completeness

Question 9

What is optimality?

Answer 9

Can it guarantee that the optimal solution will be found

Question 10

What is completeness?

Answer 10

Will a solution be found (if there is one)