Properties of breadth-first search Properties of breadth-first search Comolete??Yes (if bis finite) Tmc1+b+++…++w-)=O04.ieep.nd Space7?O()(keeps every node in memory) Properties of breadth-first search Properties of breadth-first search Complete Yes () 工m221+b+2+2+…++6(-1）-O6+,ieep.nd Sace??)(keeps every node in memory) Properties of breadth-first search Uniform-cost search Complete??Yes (if b is finite) Ime771+b+2++,.+b+M-1)=O+.ie,p.ind Equvaentto breathfirst if stepsallq Complete??Yes,if step cost >e Time Space??of modes with cost of optimal solution.)Properties of breadth-first search Complete?? Chapter 3 37 Properties of breadth-first search Complete?? Yes (if b is finite) Time?? Chapter 3 38 Properties of breadth-first search Complete?? Yes (if b is finite) Time?? 1 + b + b 2 + b 3 + . . . + b d + b(b d − 1) = O(b d+1), i.e., exp. in d Space?? Chapter 3 39 Properties of breadth-first search Complete?? Yes (if b is finite) Time?? 1 + b + b 2 + b 3 + . . . + b d + b(b d − 1) = O(b d+1), i.e., exp. in d Space?? O(b d+1) (keeps every node in memory) Optimal?? Chapter 3 40 Properties of breadth-first search Complete?? Yes (if b is finite) Time?? 1 + b + b 2 + b 3 + . . . + b d + b(b d − 1) = O(b d+1), i.e., exp. in d Space?? O(b d+1) (keeps every node in memory) Optimal?? Yes (if cost = 1 per step); not optimal in general Space is the big problem; can easily generate nodes at 100MB/sec so 24hrs = 8640GB. Chapter 3 41 Uniform-cost search Expand least-cost unexpanded node Implementation: fringe = queue ordered by path cost, lowest first Equivalent to breadth-first if step costs all equal Complete?? Yes, if step cost ≥  Time?? # of nodes with g ≤ cost of optimal solution, O(b dC ∗/e ) where C ∗ is the cost of the optimal solution Space?? # of nodes with g ≤ cost of optimal solution, O(b dC ∗/e ) Optimal?? Yes—nodes expanded in increasing order of g(n) Chapter 3 42