Outline · Problem formulation Problem solving as state space search · Mathematical model Graphs and search trees Reasoning algorithms Depth and breadth-first search Snas witha, Spring 03 Classes of search Blind Depth-First Systematic exploration of whole tree (uninformed) Breadth-First until the goal is found Iterative-Deepening Heuristic Hill-Climbing Uses heuristic measure of goodness Best-First of a node, e.g. estimated distance to Branch&Bound Uses path "length"measure Finds (informed A shortest path. a" also uses heuristic Bran withams, Spring 03 1111 Brian Williams, Spring 03 22 Outline • Problem Formulation – Problem solving as state space search • Mathematical Model – Graphs and search trees • Reasoning Algorithms – Depth and breadth-first search Brian Williams, Spring 03 23 Classes of Search Blind Depth-First Systematic exploration of whole tree (uninformed) Breadth-First until the goal is found. Iterative-Deepening Heuristic Hill-Climbing Uses heuristic measure of goodness (informed) Best-First of a node,e.g. estimated distance to. Beam goal. Optimal Branch&Bound Uses path “length” measure. Finds (informed) A* “shortest” path. A* also uses heuristic