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 11
11 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
Classes of search Depth-First Systematic exploration of whole tree (uninformed) Breadth-First until the goal is found Iterative-Deepening Snas witha, Spring 03 Depth First SearchDFS Idea Explore descendants before siblings Explore siblings left to right Bran withams, Spring 03 12
12 Brian Williams, Spring 03 24 Classes of Search Blind Depth-First Systematic exploration of whole tree (uninformed) Breadth-First until the goal is found. Iterative-Deepening Brian Williams, Spring 03 25 Depth First Search (DFS) S D A B C G C G D C G Idea: •Explore descendants before siblings •Explore siblings left to right 1 2 3 4 5 6 7 8 9 10 11 S A D C G C B D C G G