Searching for Solutions: Uninformed Search Algorithms, Lecture 3, 7/2

PseudoCode and how to write it

Tree style for homework

DFS and BFS Excercise with Tree:

DFS: goes through each node from grandparent, to parent to child, then back up again

BFS: goes from left to right

• each parent

• then each child

• then each grandchild, etc

Summary•Search algorithm ‣systematically builds the search tree ‣chooses an ordering of the frontier (unexplored nodes) ‣optimal – finds least-cost plans according to its strategy •Tree search can cause redundancies and infinite loops •Graph search avoids repetition of states already seen ∴ more efficient than tree search •Uninformed search strategies are blind in that they only use the information available in the problem definition •BFS, UCS, DFS, DLS, IDS –traversals on a search tree •IDS uses only linear space and not much more time than other uninformed searches

Search II Informed Search Algorithms