Search strategies Breadth-first search Astrategy is defined by picking the order of node expansion Expand shallowest unexpanded node en successors go at end Time D© © um depth of the(my be) Uninformed search strategies Breadth-first search Expand shallowest unexpanded node Breadth-first search Unifom-cos s Depth-first search Depth-limited search bO Breadth-first search Breadth-first search Expand shallowest panded node unexpanded node Search strategies A strategy is defined by picking the order of node expansion Strategies are evaluated along the following dimensions: completeness—does it always find a solution if one exists? time complexity—number of nodes generated/expanded space complexity—maximum number of nodes in memory optimality—does it always find a least-cost solution? Time and space complexity are measured in terms of b—maximum branching factor of the search tree d—depth of the least-cost solution m—maximum depth of the state space (may be ∞) Chapter 3 31 Uninformed search strategies Uninformed strategies use only the information available in the problem definition Breadth-first search Uniform-cost search Depth-first search Depth-limited search Iterative deepening search Chapter 3 32 Breadth-first search Expand shallowest unexpanded node Implementation: fringe is a FIFO queue, i.e., new successors go at end A B C D E F G Chapter 3 33 Breadth-first search Expand shallowest unexpanded node Implementation: fringe is a FIFO queue, i.e., new successors go at end A B C D E F G Chapter 3 34 Breadth-first search Expand shallowest unexpanded node Implementation: fringe is a FIFO queue, i.e., new successors go at end A B C D E F G Chapter 3 35 Breadth-first search Expand shallowest unexpanded node Implementation: fringe is a FIFO queue, i.e., new successors go at end A B C D E F G Chapter 3 36