CSC 411 1st Edition Lecture 6 Outline of Last Lecture I. Problem Solving by Searchinga. Searchb. What is a problem?c. Goal testingOutline of Current Lecture I. Uninformed Search Methodsa. Properties of search methodsb. Measuring Complexityc. Breadth-First Searchd. Depth-First SearchCurrent LectureUninformed Search Methods- Search techniques that rely on the information available in the problem definitiono Breadth first searcho Depth first searcho Iterative deepeningo Bi-directional search- For the minim cost path problemo Uniform cost searchSearch Methods- Properties of search methodso Completeness: Does the method find the solution if it exists?o Optimality: Is the solution returned by the algorithm optimal? Does it give a minimum length path?o Space and time complexity: How much time it takes to find the solution/How much memory is needed to do thisThese notes represent a detailed interpretation of the professor’s lecture. GradeBuddy is best used as a supplement to your own notes, not as a substitute.Parameters to measure complexities- Space and time complexityo b – maximum branching factor branching factor: the number of applicable operatorso d – depth of the optimal solutiono m – maximum depth of the state spaceBreadth-First Search (BFS)- The shallowest node is expanded first- Implementation: put successors to the end of the queue (FIFO)Properties of Breadth-First Search- Completeness: Yes, the solution is reached if it exists- Optimality: Yes, for the shortest path- Time complexity: exponential in the depth of the solution do 1+b+b2+…+bd = O(bd)- Memory (space) complexity: O(bd) nodes kept in memoryo Count nodes kept in the tree structure or queueDepth-First Search (DFS)- The deepest node is expanded first- Backtrack when the path cannot be further expanded (stack structure)Properties of Depth-First Search- Completeness: No. Infinite loops can occur- Optimality: No, solution found first may not be the shortest possible- Time complexity: exponential in the maximum depth of the search tree m o Assume a finite maximum tree depth mo O(bm)- Memory (space) complexity: linear in the maximum depth of the search tree mo
View Full Document