DOC PREVIEW
NCSU CSC 411 - Uninformed Search

This preview shows page 1 out of 2 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 2 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 2 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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

NCSU CSC 411 - Uninformed Search

Download Uninformed Search
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Uninformed Search and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Uninformed Search 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?