Thursday Jan 24 2013 - Lecture 6

7 Pages
Unlock Document

Computing and Information Science
CIS 3700
Yang Xiang

Thursday, January 24 2013 CIS 3700 Lecture 6 Review  Described the algorithm for the data structure used in tree search  Moving on to uninformed search strategies When Does the Agent Test for a Goal State  Test-Before-Expansion ◦ Generates all children k and adds it into the fringe ◦ All children are generated before the goal is tested for ◦ Generate all children and then test for the goal state  Test-At-Expansion ◦ Generates only children that do not match the goal state up until the goal state is found ◦ Not all children are generated and added to the fringe ◦ Test for the goal state as the children are generated  Test-at-expansion is slightly better for time, but the difference is insignificant because if the goal state is the final state, there is NO difference between the two methods ◦ Most AI text books will use TBE ◦ For consistency, we will use TBE, not TAE  Usage of phrases relative to tree nodes ◦ Visit ▪ Perform goal test ▪ Expand the node if the goal test was unsuccessful ▪ Verb: visit ◦ Expansion ▪ Generate its children based on the successor function ▪ Verb: expand ◦ Generation ▪ Generation is NOT visitting ▪ Generation is creating a node without visitting it Measure Problem Solving Performance  Completeness: A search algorithm is complete if it guarantees to find a solution if one exists ◦ A tree that cannot have any more leaves added to the fringe is a fully expanded search tree ◦ Some fully expanded search trees are finite, others are infinite ◦ If you fully expand the search tree and somewhere in that tree there is a goal node, then the solution is considered to be existant ◦ If you fully expand the search tree and the goal node is not in the tree, then no solution exists ◦ An agent must be able to find the solution if it exists in order to be complete  Optimality: A search algorithm is optimal if it guarantees to find the optimal solution ◦ An optimal solution has the lowest path cost among all solutions ◦ Implies the agent is complete because an agent must be able to identify all the solutions in order to select the best one  Time Complexity: Time taken to find a solution ◦ Measured by max # of nodes generated ◦ In order to measure the time complexity of the search algorithm we analyze how many nodes you generate, doesn't matter how long the computation time is per node ▪ Doesn't matter if it varies to generate each individual node ◦ A numerical value  Space Complexity: Memory needed to perform search ◦ Measured by max number of nodes stored ▪ There are times when you don't have to store the entire search tree, and there are situations when you do have to store the entire search tree ◦ A numerical value  Efficiency of solution vs. Efficiency of search ◦ Completeness and optimality have to do with the quality of the search algorithm ◦ Time complexity and space complexity have to do with the efficiency of the search algorithm ◦ Time complexity discusses the efficiency of virtually solving the problem (How quickly can the agent think?) ◦ Optimality discusses the efficiency of physically solving the problem (How quickly can the agent act?) Measure Size of Problem  Why do we measure the size of a problem?  Size of a search problem can be measured by the folowing parameters of the fully expanded search tree.  Example of measuring the size of the problem:  Branching factor: b ◦ Max number of succ
More Less

Related notes for CIS 3700

Log In


Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.