Uninformed SearchState Space SearchA Water Jug ProblemSchool Lunch PlanningCriminal Defense LawyerIncremental vs. Complete State FormulationSearchPerformance CriteriaThe Outline of a Basic Tree SearchBreadth-First SearchBreadth-First Search – When to Evaluate?Depth-First SearchThe British Museum AlgorithmIterative DeepeningIs Iterative Deepening a Win?Is ID a Win? The MathematicsSlide 17Which Direction Should We Search?Tree or Graph?Uninformed SearchR & N Chapter 3State Space SearchWe need:•Set of states•A start state•A set of operators (a successor function), possibly with costs attached.•A set of goal states (or a way to test for goal)A Water Jug ProblemYou are given two jugs, a 4-gallon one and a 3-gallon one. Neither has any measuring markers on it. There is a pump that can be used to fill the jugs with water. How can you get exactly 2 gallons of water into the 4-gallon jug?States:Start state:Operators:Goal state:School Lunch PlanningStates:Start state:Operators:Goal state:Criminal Defense LawyerStates:Start state:Operators:Goal state:Incremental vs. Complete State Formulation8-QueensStates:Start state:Operators:Goal state:SearchTwo key decisions:•Use a tree or a graph•How to choose which node to expand nextExample:Performance Criteria•Completeness•Optimality•How good is the solution? (R & N call this optimality)•How efficient is the search algorithm at finding the solution? (R & N call this Time and Space complexity)The Outline of a Basic Tree SearchBreadth-First SearchIs this a good idea?Breadth-First Search – When to Evaluate?Depth-First SearchThe British Museum AlgorithmA simple algorithm: Generate and testWhen done systematically, it is basic depth-first search.But suppose that each time we end a path, we start over at the top and choose the next path randomly. If we try this long enough, we may eventually hit a solution. We’ll call this The British Museum Algorithm or The Monkeys and Typewriters Algorithmhttp://www.arn.org/docs2/news/monkeysandtypewriters051103.htmIterative DeepeningIs Iterative Deepening a Win?N(BFS) = b + b2 + … + bd + (bd+1-b) This last term is because of how R&N define best-first search.N(IDS) = (d)b + (d-1)b2 + … + (1)bdExample: Let b = 10 and d = 5: N(IDS) = 50 + 400 + 3,000 + 20,000 + 100,000 = 123,450 N(BFS) = 10 + 100 + 1,000 + 10,000 + 100,000 + 999,990 = 1, 111, 100But there is a real saving in memory.Is ID a Win? The Mathematics1( 1)( )1hhd hdbbb bb=-= =O-�Breadth-first search:Iterative deepening:11 1h dkd kb h-= =� �+� �� ���Lower bound:Upper bound:( )2 221 1( 1)( )1hh dk hd kb h b hbb bb+= =- + +� �= =O� �-� ���Is Iterative Deepening a Win?Which Direction Should We Search?Our choices: Forward, backwards, or bidirectionalThe issues: How many start and goal states are there?Branching factors in each directionHow much work is it to compare states?Tree or Graph?Issues: How common are repeated states?How expensive is it to compare states?Examples: 8-puzzlechessschool lunch planningdefense lawyertheorem