Outline Problem Formulation: State space search Model: Graphs and search trees Reasoning Algorithms: DFS and BFS A generic search algorithm Depth-first search example Handling cycles Breadth-first search example Bnas withams, Spring 03 Simple Search algorithm How do we maintain the search state? A set of partial paths explored thus far. An ordering on which partial path to expand next called a queue Q How do we search? Repeatedly Select next partial path Terminate when goal found Bran withams, Spring 03 1414 Brian Williams, Spring 03 28 Outline • Problem Formulation: State space search • Model: Graphs and search trees • Reasoning Algorithms: DFS and BFS – A generic search algorithm – Depth-first search example – Handling cycles – Breadth-first search example Brian Williams, Spring 03 29 Simple Search Algorithm How do we maintain the Search State? • A set of partial paths explored thus far. • An ordering on which partial path to expand next • called a queue Q. How do we search? • Repeatedly: • Select next partial path • Expand it. • Terminate when goal found. S D A B C G C G D C G