Week 2 (Chapter 2) - Solving Problems & Searching

Question 1

How to evaluate a search strategy?

Answer 1

Evaluate along the following dimensions:

• Completeness
• Time complexity
• Space complexity
• Optimality

Question 2

In what way do we measure the time and space complexity of a strategy?

Answer 2

Time and space complexity are measured in terms of:
b - Maximum branching factor
d - Depth of least cost solution
m - Maximum depth of state space.

Question 3

Properties of Breadth-first search?

Answer 3

Complete - Yes (if maximum branching factor is finite)

Time - O(b^d) - i.e. exponential in d

Space - O(b^d) - keeps every node in memory

Optimal - Yes (if cost = 1 per step); HOWEVER, in general = not optimal

b - Maximum branching factor
d - Depth of least cost solution
m - Maximum depth of state space.

Question 4

What is the biggest problem for Breadth-first search?

Answer 4

Space complexity

Question 5

Properties of uniform-cost search?

Answer 5

Complete - Yes, if step cost >= e

Time - # of nodes with g <= cost of optimal solution

Space - # of nodes with g <= cost of optimal solution

Optimal - Yes

e - epsilon (A REALLY SMALL FUCKING NUMBER)
g - cost of path

Question 6

Properties of depth-first search?

Answer 6

Complete - No, fails in infinite-depth spaces, spaces with loops. If it is modified to avoid repeated states along path, can complete in finite spaces

Time - O(b^m), if m is lager than d, then time will be terrible, but dense, faster than bfs

Space - O(bm) i.e. linear

Optimal - No

b - Maximum branching factor
d - Depth of least cost solution
m - Maximum depth of state space.

Question 7

How to modify depth-first search so it’s complete?

Answer 7

Modify to avoid repeated states along path

-> completes in finite spaces

Question 8

What is iterative deepening search?

Answer 8

function Iterative-Deepening-Search( problem) returns a solution sequence
\_\_inputs: problem, a problem

__for depth ← 0 to ∞ do
____result ← Depth-Limited-Search( problem, depth)
____if result ̸= cutoff then return result
__end

Question 9

Properties of iterative deepening search?

Answer 9

Complete - Yes

Time - O(b^d)

Space - O(bd) - Linear

Optimal - Yes, if step cost = 1

Question 10

Can iterative deepening be used to explore uniform cost tree?

Answer 10

Yes if modified

Question 11

What is bidirectional search?

Answer 11

Search simultaneously forwards from the start point, and backwards from the goal, and stop when the two searches meet in the middle.

Question 12

What is the problem(s) with bidirectional search?

Answer 12

• generate predecessors
• many goal states
• efficient check for node already visited by other half of the search
• what kind of search

Question 13

Properties of bidirectional search

Answer 13

Complete - Yes

Time - O(b^(d/2))

Space - O(b^(d/2))

Optimal - Yes if done with correct strategy - e.g. breadth first