Transcription of CSEP 573 Chapters 3-5 Problem Solving using Search
{{id}} {{{paragraph}}}
Example: bachelor of science
CSEP 573 Chapters 3-5 Problem Solving using Search
1 Chapters 3-5 Problem Solving using SearchChapters 3-5 Problem Solving using SearchCSEP 573 CSE AI Faculty First, they do an on-line Search 2 Example: The 8-puzzleExample: The 8-puzzle123675841238754623 Example: Route PlanningExample: Route Planningstartend4 Example: N QueensExample: N Queens4 Queens35 Example: N QueensExample: N Queens4 Queens6 State-Space Search ProblemsState-Space Search ProblemsGeneral Problem :Given a start state, find a path to a goal state Can test if a state is a goal Given a state, can generate its successorstates Variants: Find any path least-cost path Goal is completely specified, task is just to find the path Route planning Path doesn t matter, only finding the goal state 8 puzzle, N queens47 Tree Representation of 8-Puzzle Problem SpaceTree Representation of 8-Puzzle Problem Space8fringe(= frontierin the textbook) is the
search Optimal? No, as our example illustrated 68 A* Search (Hart, Nilsson & Rafael 1968) • Best first search with f(n) = g(n) + h(n) g(n) = sum of edge costs from start to n h(n) = heuristic function = estimate of lowest cost path from n to goal • If h(n) is “admissible” then search will be optimal Und er stima co of a ny s lut iw hc
Loading..
Tags:
Information
Domain:
Source:
Link to this page:
Please notify us if you found a problem with this document: