Tree search algorithms ree search example Bat by ge Tree search example Implementation:states vs.nodes ▣回□ 可▣可 ○g 回同 in the Tree search example Implementation:general tree searchTree search algorithms Basic idea: offline, simulated exploration of state space by generating successors of already-explored states (a.k.a. expanding states) function Tree-Search( problem,strategy) returns a solution, or failure initialize the search tree using the initial state of problem loop do if there are no candidates for expansion then return failure choose a leaf node for expansion according to strategy if the node contains a goal state then return the corresponding solution else expand the node and add the resulting nodes to the search tree end Chapter 3 25 Tree search example Rimnicu Vilcea Lugoj Sibiu Zerind Arad Fagaras Oradea Timisoara Arad Arad Oradea Arad Chapter 3 26 Tree search example Arad Fagaras Oradea Rimnicu Vilcea Arad Lugoj Arad Oradea Zerind Arad Sibiu Timisoara Chapter 3 27 Tree search example Rimnicu Vilcea Arad Lugoj Arad Oradea Zerind Arad Sibiu Arad Fagaras Oradea Timisoara Chapter 3 28 Implementation: states vs. nodes A state is a (representation of) a physical configuration A node is a data structure constituting part of a search tree includes parent, children, depth, path cost g(x) States do not have parents, children, depth, or path cost! 1 3 2 5 4 6 7 1 8 3 2 5 4 6 7 8 State Node depth = 6 g = 6 state parent, action The Expand function creates new nodes, filling in the various fields and using the SuccessorFn of the problem to create the corresponding states. Chapter 3 29 Implementation: general tree search function Tree-Search( problem, fringe) returns a solution, or failure fringe ← Insert(Make-Node(Initial-State[problem]),fringe) loop do if fringe is empty then return failure node ←Remove-Front(fringe) if Goal-Test(problem,State(node)) then return node fringe ← InsertAll(Expand(node, problem),fringe) function Expand( node, problem) returns a set of nodes successors ← the empty set for each action, result in Successor-Fn(problem,State[node]) do s ← a new Node Parent-Node[s] ← node; Action[s] ← action; State[s] ← result Path-Cost[s] ← Path-Cost[node] + Step-Cost(node, action,s) Depth[s] ← Depth[node] + 1 add s to successors return successors Chapter 3 30