State Space Search

Question 1

Evaluating Breadth-First Search

Answer 1

• Completeness: Yes
• Time Complexity: O(b^d)
• Space Complexity: O(b^d)
• Optimality/Admissibility: Yes

Question 2

Evaluating Depth-First Search

Answer 2

• Completeness: No
• Time Complexity: O(b^m)
• Space Complexity: O(bm)
• Optimality/Admissibility: No

Question 3

Evaluating Depth-First Search with depth limit (l)

Answer 3

• Completeness: Yes ( if l > solution’s depth)
• Time Complexity: O(b^l)
• Space Complexity: O(bl)
• Optimality/Admissibility: No

Question 4

Evaluating Depth-First Search with iterative deepening (IDS)

Answer 4

• Completeness: Yes
• Time Complexity: O(b^d)
• Space Complexity: O(bd)
• Optimality/Admissibility: Yes

Question 5

What is an uninformed search?

Answer 5

A search that has no way of determining whether one state is better than other

Question 6

What is an admissible search?

Answer 6

An admissible search is a search that always guarantees to find an optimal solution

Question 7

What is informedness?

Answer 7

A search is more informed than the other when it examines fewer states before it found the solution

Question 8

What is a heuristic that leads to admissible search?

Answer 8

A heuristic that always underestimates the distance from the current state to the goal

Question 9

How to evaluate the heuristic for each state?

Answer 9

Using:

f(n) = g(n) + h(n)
where:
g(n) is the evaluation from start state to n state
h(n) is the heuristic estimate the distance from the current n state to the goal