Simple Search algorithm s denotes the start node g denotes the goal node A partial path is a path from S to some node D ·eg,(DAS) The head of a partial path is the most recent node of the path The Q is a list of partial paths, e.g.(DAS(CAS). Simple search algorithm Let Q be a list of partial paths, Let s be the start node and Letg be the goal node 1. Initialize Q with partial path (s) 2. IfQ is empty, fail. Else, pick a partial path N from Q 3. If head(N)=G, return N (goal reached Else a) Remove N from Q b Find all children of head(N)and create all the one-step extensions of n to each child c)Add all extended paths to Q d)Go to step 2. Bran withams, Spring 03 1515 Brian Williams, Spring 03 30 Simple Search Algorithm • S denotes the start node • G denotes the goal node. • A partial path is a path from S to some node D, • e.g., (D A S) • The head of a partial path is the most recent node of the path, • e.g., D. • The Q is a list of partial paths, • e.g. ((D A S) (C A S) …). S D A B C G C G D C G Brian Williams, Spring 03 31 Simple Search Algorithm Let Q be a list of partial paths, Let S be the start node and Let G be the Goal node. 1. Initialize Q with partial path (S) 2. If Q is empty, fail. Else, pick a partial path N from Q 3. If head(N) = G, return N (goal reached!) 4. Else: a) Remove N from Q b) Find all children of head(N) and create all the one-step extensions of N to each child. c) Add all extended paths to Q d) Go to step 2