Properties of depth-first search Properties of depth-first search Complete?7 complete in finite spoces SpaceO(m).ielinear space! Properties of depth-first search Properties of depth-first search Space77O(m)ie linear spacel Optimal?No Properties of depth-first search Depth-limited search Recursive implementation: function Rcuv-DLS(o/fall/cutoff if GOAL-TESTST Properties of depth-first search Complete?? Chapter 3 55 Properties of depth-first search Complete?? No: fails in infinite-depth spaces, spaces with loops Modify to avoid repeated states along path ⇒ complete in finite spaces Time?? Chapter 3 56 Properties of depth-first search Complete?? No: fails in infinite-depth spaces, spaces with loops Modify to avoid repeated states along path ⇒ complete in finite spaces Time?? O(b m): terrible if m is much larger than d but if solutions are dense, may be much faster than breadth-first Space?? Chapter 3 57 Properties of depth-first search Complete?? No: fails in infinite-depth spaces, spaces with loops Modify to avoid repeated states along path ⇒ complete in finite spaces Time?? O(b m): terrible if m is much larger than d but if solutions are dense, may be much faster than breadth-first Space?? O(bm), i.e., linear space! Optimal?? Chapter 3 58 Properties of depth-first search Complete?? No: fails in infinite-depth spaces, spaces with loops Modify to avoid repeated states along path ⇒ complete in finite spaces Time?? O(b m): terrible if m is much larger than d but if solutions are dense, may be much faster than breadth-first Space?? O(bm), i.e., linear space! Optimal?? No Chapter 3 59 Depth-limited search = depth-first search with depth limit l, i.e., nodes at depth l have no successors Recursive implementation: function Depth-Limited-Search( problem, limit) returns soln/fail/cutoff Recursive-DLS(Make-Node(Initial-State[problem]), problem, limit) function Recursive-DLS(node, problem, limit) returns soln/fail/cutoff cutoff-occurred? ←false if Goal-Test(problem,State[node]) then return node else if Depth[node] = limit then return cutoff else for each successor in Expand(node, problem) do result ← Recursive-DLS(successor, problem, limit) if result = cutoff then cutoff-occurred? ←true else if result 6= failure then return result if cutoff-occurred? then return cutoff else return failure Chapter 3 60