CSC 242 Lecture Notes - Lecture 2: Branching Factor, Longest Path Problem, Tree Traversal
21 Feb 2017
School
Department
Course
Professor
Document Summary
Type of search strategies: uninformed no additional information about states, informed (heuristic) can identify promising" states. All you can do is generate successors, and compare if we"re at goal state . State-space search if used if we don"t have any existing method that"s better, but it"s not the most efficient method. Expand all nodes in a level before expanding any children. We look at: completeness bfs explorer the whole tree systematically, optimality somewhat, could be better, but it is a non-decreasing function of the depth of the space, so it"s acceptable. It finds the shallowest solution: time o(bd, space o(bd) Does it work? let b: branching factor (number of actions possible in a state) let d: depth of shallowest goal let m: length of longest path. Preferred uninformed search method when search space is large and depth of solution is not known. for d = 1, 2, 3.
