正在生成预览...
CS361(Artificial Intelligence) Lecture4 Problem Solving as Search (Blind/Uninformedvs.Heuristic/InformedStrategies) Dr. Hala Abdel-Galil & Dr. Amr S. Ghoneim (Computer Science Dept.) Helwan University Fall 2019 Lecture is based on its counterparts in the following courses: o Artificial Intelligence, University of Illinois at Urbana-Champaign
Resourcesforthislecture o This lecture covers the following chapters/sections: o Chapter 3 (Structures & Strategies for State Space Search; sections 3.2, and 3.3) and Chapter 4 (Heuristic Search) from George F. Luger, "Artificial Intelligence: Structures and strategies for complex problem solving, " Sixth edition (2009), Pearson Education Limited.
Outline o Search: Basic idea o Search tree o Tree Search Algorithm Outline o Heuristic Function o Handling repeated states o Robot Navigation o Backtracking Search o Examples of Evaluation function o Backtracking Algorithm o 8-Puzzle Data Structure o Reasoning Representation o Backtracking Algorithm o Propositional Calculus: Example (1) o Blind vs. Heuristic Strategies o And/ Or Graph o Blind Strategies o Propositional Calculus: Example (2) o Depth-First Strategy o Predicate Calculus Example o Depth-Limited Strategy o Comparison of Blind o More on Heuristic Search & Functions Search Strategies o Symmetry Reduction o Repeated States o Heuristic Reduction o Avoiding Repeated States o Hill Climbing Strategy o Uniform-Cost Strategy o Best-First Search o Best-First Search o 8-Puzzle Heuristics
Recap:Search Given: Initial state Actions Transition model Goal state Path cost How do we find the optimal solution?
Recap:Search:Basicidea o Let’s begin at the start state and expand it by making a list of all possible successor states. o Maintain a frontier or a list of unexpanded states. o At each step, pick a state from the frontier to expand. o Keep going until you reach a goal state. o Try to expand as few states as possible.
Recap:Searchtree Starting state “What if” tree of sequences of actions and outcomes ❖ When we are searching, we are not acting in the Action world, merely “thinking” about the possibilities Successor The root node corresponds to the starting state state The children of a node correspond to the successor states of that node’s state A path through the tree corresponds to a sequence of … actions ❖ A solution is a path ending in the goal state Nodes vs. states Frontier A state is a representation of the world, Goal while a node is a data structure that is state part of the search tree Node has to keep pointer to parent, path cost, possibly other info
Recap:TreeSearchAlgorithmOutline Initialize the frontier using the starting state. While the frontier is not empty: • Choose a frontier node according to search strategy and take it off the frontier. • If the node contains the goal state, return solution. • Else expand the node and add its children to the frontier.
显示前 19 页。下载资料查看完整内容。
暂无评论。快来抢沙发吧！
评论 (0)
暂无评论。快来抢沙发吧！