《2015AI课件lec4启发式搜索2013章节》由会员分享，可在线阅读，更多相关《2015AI课件lec4启发式搜索2013章节（81页珍藏版）》请在金锄头文库上搜索。
1、9 Heuristic Search 启发式搜索,付 岩 F 13101613075,Points,Basic idea of heuristic search. What is evaluation function & how to design it? Best-first Search. A* algorithm. What is the admissibility and information intensity of evaluation function?,学习要求,理解启发式搜索的含义 掌握评价函数及启发式函数的构造方法 掌握A*算法求解过程 熟悉A*算法的应用领域及应用思路
2、 了解启发式函数的可接纳性、信息强度,Heuristic Search,Heuristic一词 起源于希腊词根 eurisco “我发现了” 1957年，在Polya的 How to solve it一书中 首次作为技术术语使用,林昏天未曙 但向云边去 暗入无路山 心知有花处 唐卢纶,Heuristic Search,Start,Goal,What is heuristic searching?,Why heuristic search? Using the problem-specific reasoning information.,What is a heuristic?,A heuri
3、stic is any rule or method that provides guidance in decision making. A useful heuristic need not always improve decision making, but it should improve decision more often than not. Choosing to stand in the shortest checkout line at the supermarket does not always get you out of the store quickly, b
4、ut it is a useful heuristic if you have no other information to go on.,AI问题求解在两种情况采用启发：,问题陈述或现有数据存在固有模糊性，问题可能没有精确解。例如：医疗诊断、视觉幻像。 问题可能有精确解，但是找解的开销大得难以承受。例如：组合爆炸。,9,9.1 Using Evaluation Functions (Basic Idea of Heuristic Search),Heuristic Search,Using the problem-specific reasoning information.,Heuris
5、tic search: -Using evaluation function: f(n).,General Search,开始,把S放入OPEN表,OPEN表为空表？,把第一个节点(n)从OPEN表移至CLOSED表,n为目标节点吗？,把n的后继节点放入OPEN表,修改返回节点n的指针,失败,成功,是,是,否,否,重排OPEN表,How the following methods reorder the OPEN list? Breadth-first search Uniform-cost search Depth-first search,Using Evaluation Function
6、s,Breadth-first search: FIFO. Expanding the node whose depth is least. Uniform-cost search: Expanding the node whose cost is least. Depth-first search: FILO. Expanding the node whose depth is most.,Heuristic search: -Expanding the node whose f(n) is least.,蔡自兴：,一个节点的“希望”（promise）： 估算目标节点到此节点的距离。 计算经
7、过该节点的路径的长度或难度。 评估方法： 评估该节点的决定性特性。 比较该节点与目标节点的差别。,估算节点希望程度的度量； 评估函数 f(n),Basic idea of heuristic search,We assume that we have a heuristic function f to help decide which node is the best one to expand next. Expand the node n which has the smallest value of f(n). Terminate when the node to be expand
8、is a goal node.,Important! Designed by programmer!,The design of evaluation functions ： Eight-Puzzle,Start Goal,f(n)=number of tiles out of place (compared with goal),The design of evaluation functions ： Eight-Puzzle,f(n)=g(n)+h(n) g(n): depth of n; h(n): number of tiles out of place.,Exercise & que
9、stion,f1(n)= the sum of the distances of the tiles from their goal position.,f2(n)= (depth of n) +(f1(n),The design of evaluation functions,The design of good heuristic is an empirical problem; judgement and intuition help, but the final measure of a heuristic must be its actual performance on probl
10、em instances.,9,Best-first Search,Basic idea of best-first search,it works by sorting the list of nodes to be explored next according to their estimated distance from a goal.,Best-first Search,开始,把S放入OPEN表,OPEN表为空表？,把第一个节点(n)从OPEN表移至CLOSED表,n为目标节点吗？,把n的后继节点放入OPEN表,修改返回节点n的指针,失败,成功,是,是,否,否,重排OPEN表,Ac
11、cording to their estimated distance from a goal.,f(n)=estimated distance from n to a goal.,Eg1:,Eg1:Process of search,Eg1:,Eg2:罗马尼亚寻径,Eg2:罗马尼亚寻径,Eg2:罗马尼亚寻径,f(n)= estimated distance from a goal = the straight-line distance from n to Bucharest.,best-first search example,best-first search example,best-
12、first search example,best-first search example,Eg2:罗马尼亚寻径,Question,Can Best-first search get the optimal solution of the problem? (optimality) How the completeness of best-first search?,9,A* Algorithm,Thinking the following Evaluation Function !,f(n) = g(n) + h(n) Let g(n)= the cost of a minimal cos
13、t path from the start node n0 to node n. h(n)= the actual cost of the minimal cost path between n and a goal node.,f(n) = the cost of a minimal cost path from n0 to a goal node through node n.,Thinking the following Evaluation Function !,f(n) = g(n) + h(n) Let n=n0, Then, g(n)=g(n0)=0 h(n)=h(n0)=the
14、 actual cost of the minimal cost path between n0 and a goal node.,Best evaluation function,Difficult, almost impossible,Thinking the following Evaluation Function f(n) !,f(n) = g(n) + h(n) g(n) is estimation of g(n). h(n) is estimation of h(n). f(n) is estimation of f(n).,Thinking the following Eval
15、uation Function f(n) !,f(n) = g(n) + h(n),1 let g(n) = the cost of the lowest-cost path found (from n0 to n). h(n) 0 .,Then the process of search become :,Uniform-cost search/breadth-first search,Thinking the following Evaluation Function f(n) !,f(n) = g(n) + h(n),2 let g(n) 0 h(n) = the estimation of h(n).,Then the process of search become :,Best-first search,Thinking the following Evaluation Function f(n) !,f(n) = g(n) + h(n),3 let g(n) = the cost of the lowest-cost pat
