Week 2: From Simple Search to Informed Search

Question 1

Problem types

Answer 1

• Deterministic, fully observable → single-state problem
• Agent knows exactly which state it will be in; solution is a sequence
• Non-observable → conformant problem
• Agent may have no idea where it is; solution (if any) is a sequence
• Nondeterministic and/or partially observable → contingency problem
• percepts provide new information about current state
• solution is a contingent plan or a policy
• often interleave search, execution
• Unknown state space → exploration problem (“online”)

Question 2

Single-state problem formulation

Answer 2

A problem is defined by four items:
* initial state
* successor function
* goal test, can be
* path cost

Question 3

Implementation:
states vs. nodes

Answer 3

• A state is a (representation of) a physical configuration
• A node is a data structure constituting part of a search tree and includes parent,
  children, depth, path cost g(x)

Question 4

Measuring problem-solving
performance

Answer 4

Completeness: Is the algorithm guaranteed to find a solution when there is one?
* Optimality: Does the strategy find the optimal solution?
* Time complexity: How long does it take to find a solution?
* Space complexity: How much memory is needed to perform the search?

• Time and space complexity are measured in terms of
• b — maximum branching factor of the search tree
• d — depth of the least-cost solution
• m — maximum depth of the state space (may be ∞)

Question 5

Search Strategies

Answer 5

A strategy is defined by picking the order of node expansion

Uninformed strategies use only the information available in the problem definition

• Breadth-first search
• Uniform-cost search
• Depth-first search
• Depth-limited search
• Iterative deepening search

Question 6

Properties of breadth-first search

Answer 6

• Completeness - Yes (if b is finite)
• Time complexity - O(bd+1 ), i.e., exponential in d
• Space complexity - O(bd+1 ) (keeps every node in memory)
• Optimal - Yes (if cost = 1 per step); not optimal
  in general

Question 7

Uniform-cost search

Answer 7

• Complete - Yes, if step cost ≥ ε
• Time - g ≤ cost of optimal solution
• Space - of nodes with g ≤ cost of optimal solution
• Optimal - Yes—nodes expanded in increasing order of g(n)

Question 8

Depth-first
search

Answer 8

• Complete - No: fails in infinite-depth spaces
• Time - terrible if m is much larger than d, but if solutions
  are dense, may be much faster than breadth-first
• Space - linear space
• Optimal - No

Question 9

Iterative
deepening
search

Answer 9

• Complete - Yes
• Time- O(b^d)
• Space - O(bd)
• Optimal - Yes, if step cost = 1