search strategies (slides 3)

Question 1

how is a search strategy defined?

Answer 1

by picking the order of node expansion

Question 2

Strategy evaluation criterion

Answer 2

completeness-does it always find a solution?
time complexity-number of nodes generated
space complexity-max # of nodes in memory
optimality-does it always find a least cost soln?

Question 3

time and space complexity measurement

Answer 3

b: maximum branching factor of the search tree
d: dept of the least-cost solution
m: maximum depth of the state space

Question 4

uninformed search

Answer 4

use only the information available in the problem definition

• generate successors
• distinguish goals

Question 5

uninformed search strategies

Answer 5

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

Question 6

breadth first search

Answer 6

expand shallowest unexpanded node

fringe is a FIFO queue

Question 7

breadth-first search properties

Answer 7

completeness: yes
time: O(b^(d+1)) if goal test is performed at expansion time, O(b^d) otherwise
- d = depth
space: O(b^(d+1)) if goal test is performed at expansion time, O(b^d) otherwise
optimality: yes if cost = 1 per step

space is its biggest problem

Question 8

uniform-cost search

Answer 8

expand least-cost unexpanded node
implentation:
- fringe = priority queue ordered by path cost g(x)
- goal test performed at expansion time
equivalent to breadth-first if step costs all equal

Question 9

uniform-cost search properties

Answer 9

completeness: Yes, if step cost => e
- if there are some 0-cost edges it may get stuck on an infinite loop

time: # of nodes with g<= cost of optimal solution, O(b^(floor(C/e) + 1) where C is the cost of the optimal solution

space: same as time
optimality: yes, nodes are expanded in increasing order of g(n)

Question 10

depth-first search(problem)

Answer 10

expand deepest unexpanded node
implementation:
-fringe = LIFO queue

Question 11

depth-first search properties

Answer 11

completeness: no: fails in infinite depth spaces, spaces with loops
- Modify to avoid repeated states on path
- -> complete in finite spaces
time: O(b^m): terrible if m is much larger than d
- if solns are fast, may be much better than breadth first
space: O(bm) Linear!! (node along the path + unexpanded siblings)
optimal: no

Question 12

depth-limited search(problem,l)

Answer 12

depth first search with depth limit L.

implementation of depth first search in eclipse

Question 13

iterative deepening search(problem)

Answer 13

depth limited search with consecutively increasing depth limit

Question 14

iterative deepening search

Answer 14

completeness: yes
time: O(b^d)
space: O(bd)
optimal: Yes, if step cost = 1 (or generally non decreasing function of depth)

Question 15

Graph search

Answer 15

tree search with additional data structure containing visited nodes to prevent from revisiting them