Chapter 2 : Search

Question 1

What is uniformed search?

Answer 1

Has no idea what the environment entails

Question 2

What is informed search?

Answer 2

Uses information about environment to conduct a search efficiently

Question 3

What are the complete/optimal/complexities of breadth-first search

Answer 3

Complete: yes
Optimal: yes
Time complexity: O(b^d)
Space complexity: O(b^d)

where d is depth of solution

Question 4

What are the complete/optimal/complexities of uniform cost search?

Answer 4

Complete: yes
Optimal: yes
Time complexity: O(b^(c/epsilon)+1)
Space complexity: O(b^(c/epsilon)+1)

Question 5

What are the complete/optimal/complexities of depth-first search?

Answer 5

Complete: no
Optimal: no
Time complexity: O(b^M)
Space complexity: O(b^M)

where M is depth of tree

Question 6

What are the complete/optimal/complexities of depth-limited search?

Answer 6

Complete: if l >= d yes, if l < d no
Optimal: only optimal if l = d, otherwise no
Time complexity: O(b^L)
Space complexity: O(b^L)

where l is level and d is depth of solution

Question 7

What are the complete/optimal/complexities of iterative deepening tree?

Answer 7

Complete: yes
Optimal: yes
Time complexity: O(b^d)
Space complexity: O(b*d)

d is depth of solution

Question 8

What are the complete/optimal/complexities of bidirectional tree?

Answer 8

Complete: yes
Optimal: yes
Time complexity: O(b^(d/2))
Space complexity: O(b^(d/2))

d is depth of solution

Question 9

What are the complete/optimal/complexities of greedy best-first search?

Answer 9

Complete: yes, in finite spaces
Optimal: no, can make a bad decision
Time complexity: O(b^M)
Space complexity: O(b^M)

where M is depth of tree

Question 10

What are the complexities of A* Pathfinding?

Answer 10

Complete: yes
Optimal: yes

*Only if a good heuristic is used

Question 11

What is local search?

Answer 11

Only operate on single current node (rather then looking at entire state) and generally only moves to neighbors

Question 12

What are advantages of local search?

Answer 12

• Less memory

- Can find reasonable solutions in huge state spaces which would not be possible with informed/uninformed searches

Question 13

Where does hill climbing search get stuck?

Answer 13

plateaus, local maxima, ridges

Question 14

What are solutions to fixing hill climbing search?

Answer 14

• Random restart

- Problem reformulation

Question 15

Is hill climbing search guaranteed to find solution?

Answer 15

False, if probability of finding solution is p chance of finding a solution on each restart is 1/p

Question 16

What does simulated annealing search do?

Answer 16

Algorithm allows “smartly” to make bad decisions in hopes it will lead to an eventual smart decision at end.

f - heuristic function
T - temperate (if larger then accepts worse decisions)

Question 17

What is local beam search?

Answer 17

• Starts with k randomly generated states

- If goal found stop, otherwise pick best k’ states

Question 18

What is gradient/descent search?

Answer 18

Used for continuous environments to find minma/maxima

Question 19

What is adversarial search?

Answer 19

Used in multi-agent competitive environments where agents goals are in conflict

Question 20

What is Mini-max search?

Answer 20

Adversarial search algorithm that assumes

• 2 Players
• Game is zero-sum (one wins)
• Each player plays optimally
• One player tries to maximize utility function other tries to minimize it

Question 21

What is alpha beta pruning?

Answer 21

Used in Minimax state trees on terminal nodes that will have no impact on decisions