PPTOK :您身边最贴心好用的PPT站!

您当前所在位置:首页 > PPT课件 > 行业PPT → 人工智能chapter5heuristic ppt

人工智能chapter5heuristic ppt

  • 素材大小:1.17 MB
  • 素材授权:免费下载
  • 更新时间:2018-03-29
  • 素材类别:行业PPT
  • 素材格式:.ppt
  • 关键提要:人工智能chapter5heuristic,人工智能
  • 素材版本:PowerPoint2003及以上版本(.ppt)
网友评分:
PPT介绍优秀PPT相关PPT精品PPT

这是人工智能chapter5heuristic ppt,包括了启发式搜索和估价函数,状态空间的启发式搜索,A算法和A*算法,与或树的启发式搜索,博弈树搜索等内容,欢迎点击下载。

PPT预览

人工智能chapter5heuristic ppt

PPT内容

第五章 启发式搜索
启发式搜索
“启发” (heuristic) 是关于发现和发明规则及方法的研究。在状态空间搜索中,启发式被定义成一系列规则,它从状态空间中选择最有希望到达问题解的路径。
有信息的搜索策略——是一种在问题本身的定义之外还利用问题的特定知识的策略。
启发性信息
启发性信息的种类
    有效地帮助确定扩展节点的信息;
    有效的帮助决定哪些后继节点应被生成的信息;
    能决定在扩展一个节点时哪些节点应从搜索树上删除的信息。
  启发性信息的作用
  启发信息的启发能力越强,扩展的无用结点越少。
启发式搜索
在两种情况下运用启发式策略:
 一个问题由于在问题陈述和数据获取方面固有的模糊性可能使它没有一个确定的解。医疗诊断,视觉系统可运用启发式策策略选择最有可能解释。
一个问题(如国际象棋)可能有确定解,但是求解过程中的计算机代价令人难以接受。穷尽式搜索策略,在一个给定的时空内很可能得不到最终的解。启发式策略通过指导搜索向最有希望的方向前进降低了复杂性。消除组合爆炸,并得到令人能接受的解。然而,启发式策略也是极易出错的。
5.1 启发式搜索和估价函数
启发式策略及算法设计一直是人工智能的核心问题。
博弈和定理证明是两个最古老的应用,二者都需要启发式知识来剪枝以减少状态空间。
应用启发式减少搜索耗散。
启发式算法通常由两部分组成:方法和使用该方法搜索状态空间的算法。
5.2.2 最好优先搜索法
定义:
Best-first Search (Ordered Search)
在AI图解搜索中,结点扩展的顺序是根据待扩展结点的评价函数值 f(x)来决定,即将评价函数值最佳的结点最先扩展,搜索方法是靠 f 值指导搜索顺序的。
5.2.2 最好优先搜索法
估计函数 (评价函数) f(x):
估计函数的任务就是估计OPEN表 中各结点的重要程度并给它们排定次序,估计函数 f(x) 可以是任意一种函数:
有的定义它是结点X处于最佳路径上的概率。
或者是结点X和目标结点之间的距离。
或者是X格句的得分等等。
一般来说,估计一个结点的价值,必须考虑两方面因素:已经付出的代价和将要付出的代价。我们把估计函数f(n)定义为从初始结点经过n结点到达目标结点的最小代价估计值。
5.2.2 最好优先搜索法
一般形式为:f(n) = g(n) + h(n)
其中:g(n)是从初始结点到n的实际代价;h(n)是从n到目标结点的估计代价。
h(n)体现了搜索的启发信息。因为实际代价g(n)可以根据已生成的搜索树计算出来,而估计代h(n)有赖于某种经验估计,它来源于我们对问题的解的某些特性的认识,这些特性可以帮助我们更快的找到问题的解。
如果h(n)=0,g(n)=d(n) 时,就是广度优先搜索法。一般讲在 f(n) 中,g(n)的比重越大,越倾向于广度优先搜索;h(n)的比重越大,越倾向于深度优先搜索。
有了f(n),就可以对各个待扩展结点的价值进行估计,从OPEN表中选择出最有希望的结点扩展。
5.2.2 最好优先搜索法
搜索的过程:
有序搜索中的数据结构不同于广度优先搜索使用的队,也不同于深度优先搜索使用的栈,而是一个按结点的 f 值的大小为序排列的一个表,有时也称为“优先队”。进入优先队的结点不是简单地排在队末尾,而是根据其 f 值的大小插入队中合适的位置。每次从队中优先取出f 值最小的结点加以扩展。
例:一个结点有多条通道的搜索树的有序搜索过程:
5.2.2 最好优先搜索法
(c)
(d)
最好优先搜索法
最好优先搜索法
从上图可知,当搜索开始时,树根结点进入优先队中,因为队中只有一个结点,故无序可排。接着扩展树根,它有三个可能的通道,通向F、B、H三个结点。显然,这三个结点的g值皆为1。图中的h值虽标为精确值,实际上应为估算值。算出三个结点的 f 值分别为3、4和5。将这三个结点按 f 的大小送入优先队中。下一个要扩展的结点是队中 f 值最小的结点,即结点F。它只有一个后继结点D,其结点值 f 等于3,由于结点F已被充分扩展,故变为闭结点,而将 f 值最小的结点D插入队首,接着再扩展D,如此继续,直到出现目标结点E时为止。
有序搜索方法的流程图
最好优先搜索法算法描述
PROCEDURE  BEST-FIRST-SEARCH
INITIALIZE: OPEN=[START]; CLOSED=[  ];
WHILE  OPEN≠[  ]  DO
BEGIN
 REMOVE  THE  NEXT STATE  FROM OPEN, CALL IT  X;
 IF X  IS  A GOAL   THEN   RETURN  THE SOLUTION  PATH  THAT  LED TO X;
  PROCESS X,  GENERATING  ALL  ITS  CHILDREN;
  FOR EACH CHILD OF X
  DO CASE
   THE  CHILD  IS  NOT  ALREADY ON OPEN OR CLOSED:
   BEGIN
        ASSIGN A HEURISTIC VALUE TO THE CHILD STATE;
        ADD THE  CHILD  STATE  TO  OPEN;
   END;
   THE  CHILD  IS  ALREADY  ON  OPEN:
   IF  THE  CHILD  WAS  REACHED ALONG A SHORTER  PATH   THAN THE STATE CURRENLTY ON OPEN
   THEN  GIVE  THE STATE  ON  OPEN  THIS SHORTER   PATH VALUE
最好优先搜索法算法描述
THE CHILD IS ALREADY ON CLOSED:
IF  THE  CHILD  WAS  REACHED  ALONG A SHORTER PATH    THAN  THE  STATE  CURRENLTY ON CLOSED
   THEN
      BEGIN
           GIVE  THE STATE  ON CLOSED THIS SHORTER PATH   VALUE;
           MOVE THIS  STATE  FROM  CLOSED TO OPEN
       END
    END;
   PUT  X  ON  CLOSED;
   RE-ORDER  STATES  ON OPEN ACCORDING TO HEURISTIC MERIT(BEST  VALUES  FIRST)
   END;
   RETURN(FAILURE);  % OPEN IS EXHAUSTED
END.
5.2.3 启发估计函数的实现
例:
5.2.3 启发估计函数的实现
1
5.2.3 启发估计函数的实现
图 启发式搜索产生的状态空间
5.2.3 启发估计函数的实现
产生图的一系列过程如下:
 1.open=[a4];  closed=[ ]
  2.open=[c4,b6,d6];  closed=[a4]
  3.open=[e5,f5,g6,b6,d6];   closed=[a4,c4]
  4.open=[f5,h6,g6,b6,d6,i7];   closed=[a4,c4,e5]
  5.open=[j5,h6,g6,b6,d6,k7,i7];   closed=[a4,c4,e5,f5]
  6.open=[l5,h6,g6,b6,d6,k7,i7];   closed=[a4,c4,e5,f5,j5]
  7.open=[m5,h6,g6,b6,d6,n7,k7,i7];
          closed=[a4,c4,e5,f5,j5,l5]
 8.成功,m=目标状态!
5.2.3 启发估计函数的实现
启发式搜索的一般规则如下:
1.根据规则生成当前结点的子状态。
2.检查每个状态是否已在open表或closed表中, 以防止循环。
3.每个状态n都赋以f(n)值。其中f=g+h,h值使搜索具有较好启发值; g值防止搜索在无效路径上无限继续下去。
4.Open表中的状态按f值排序。通过保存这些状态,能从一无效路径上返回。
5.通过设计Open表和Closed表的存储方式,可提高算法的效率。
另外:随机搜索
搜索问题是计算机科学和人工智能的中心研究兴趣之一。
“无穷猴子定理”——Arthur Eddington
(如果有非常多只猴子,每一只都在连续敲打自己的一台打字机,总有一天,将有一只猴子可以碰巧“打出”《哈姆雷特》剧本)
最优解存在和搜索最优解所付出的努力的多少
 搜索朝着预期最优解的区域前进,同时允许一定程度的随机扰动,以利于发现好的解
5.5.1  博弈树
5.5.2 博弈树搜索
博弈树中的结点表示一种 棋局,表示各种棋子分布在棋盘上的局势,不同的棋局标以不同的代号。
假设主方先走,此时的棋局为开局,它用结点A表示,设主方有三种 走法,分别形成棋局B,C,D。由于主方可以随意选择,称或扩展,A为或结点。现轮对方走,对方必须选择最不利于主方的一着。这种 扩展称为与扩展,B,C,D均为与结点。
如果我们能为一盘棋从开局到终局画出一棵完整的与/或树,那么就可以从中找出一条走向标注“胜”的树叶的道路,遗憾的是即使对于一种很简单的棋,这样的一棵树也是非常庞大的
5.5.2 策略
5.5.2 策略
5.4.3 极大极小法过程
对简单的博弈问题,可生成整个博弈树,找到必胜的策略。
 对于复杂的博弈问题,不可能生成整个搜索树,如国际象棋,大约有10120个节点。
 一种可行的方法是用当前正在考察的节点生成一棵部分博弈树,并利用估价函数f(n)对叶节点进行静态估值。
5.4.3 极大极小法
用极大极小法标注博弈树的结点值:倒推
MIN
5.4.3 极大极小法
下棋策略及常用术语 : 
从极大极小法分析,下棋的策略现在变为抢最大值与最小值的策略。即主方力图走向结点值最大的结点,而对方则力图走向结点值最小的结点。
即使是一种简单的棋,一棵完整的博弈树也是非常庞大的,所以由于计算机容量与速度的限制,不可能一直扩展到出现终局为止,我们只能到某个时间就停止扩展。因此,这棵部分博弈树的树叶不再与棋局的终局相对应,这种棋局称为截止局。
5.4.3 极大极小法
截止局----它必须是可以确切地计算其结点值的棋局。当然,棋的终局必须是截止局,此时胜负分明。或可以根据棋局(双方棋子的种类及其分布等)的优劣确定结点值的那些棋局。
活局----下一步会导致双方力量发生显著变化的棋局。
死局----找不到任何一步会导致双方力量发生显著变化的棋局,称为“死局”,截止局是“死局”。
5.4.3 极大极小法
在下棋过程中,静态估价函数计算结点的值。因为它是根据棋子在棋盘上的静态分布,而不考虑棋子的可能移动来计算结点值的,所以称它为静态估值函数。
考虑以下因素:
  (1)力量:反映棋子的数量与质量,例如:一车和一马可以用3与2分别表示质量的优劣。
  (2)活力:表示一个棋子可以活动的范围,例如:不被对方吃掉的地方可计入。
  (3)对关键区域的控制,例如:象棋中的将帅活动区等。
  (4)特定棋局:长期的经验证明,某些棋局具有很重要的地位,如果出现这些棋局,可给以一定的分数来表达一定的优势。
5.4.4 纵向极大极小法
假设轮到主方走,怎样才能取胜呢?以当前的棋局作为部分博弈树的树根,分析各种可能的走法,每一种可能的走步引出一个后继结点,对它应用上述的规则查看是否截止局,若是,则停止向深处扩展,否则根据对方可能的应着再引出下一级的后继结点,如此继续,逐步扩展成一棵部分博弈树。
然后根据估价函数计算所有截止局结点的值,再应用极大极小法,由下往上逐级标注各结点的值。
启发式搜索示例:
规定MAX为Ⅹ方,MIN为〇方, Ⅹ方先走,试用极小极大化分析法求双方的最佳策略。
利用上述定义,可以计算各种棋局的Ⅹ方的静态估值函数h1(n):
如果要改用〇方的观点来分析同一个棋局的静态估值h1’,只需将上述h1反号即可。也就是说
    h1’(n)=- h1(n)
用这个静态估值函数h1(n) 可得极大极小化分析,其中的扩展深度是2。
第一步:极大极小化分析图
第二步分析:例如Ⅹ方的最佳走步按h1(n)估计是:
则〇方有4 种“最佳选择”(估值1)。而实际上除了选择
第二步:极小极大分析图
5.5 启发式搜索示例 (P185)
“与”取最小值
纵向极大极小法
当前的棋局(主方走)
取最大值
5.4.4 纵向极大极小法
纵向极大极小法从树根开始,沿着一条纵向树杆不断往深处扩展结点,直到出现截止局为止。然后按原路返回直到找到一个还未充分扩展完毕的结点,再从它开始,往深处不断扩展直到再次出现截止局为止。
每当扩展一个新的结点,首先判断是否截止局,不是则继续向深处扩展,直到出现截止局,立即计算该结点的值,算完后,返回其前辈结点,由于该结点的全部后继结点不一定全部扩展出来,因此,无法确定其返回值。但可以根据已有的后继结点确定一个局部返回值。
5.4.4 纵向极大极小法
用纵向极大极小法计算结点值
5.4.4 纵向极大极小法
5.4.5  α–β剪枝法
5.4.5  α–β剪枝法
5.4.5  α–β剪枝法
令或结点的α值等于其当前子结点中的最大倒推值
令与结点的β值等于其当前子结点中的最小倒推值
5.4.5  α–β剪枝法
用α–β剪枝法求根节点N的最佳走步
用α–β截枝法求根节点N的最佳走步
 

相关PPT

人工智能基础03--搜索技术ppt:这是人工智能基础03--搜索技术ppt,包括了盲目搜索,启发式搜索,博弈树搜索,遗传算法,模拟退火算法,免疫算法等内容,欢迎点击下载。
人工智能基础07--自动规划系统ppt:这是人工智能基础07--自动规划系统ppt,包括了自动规划概述,基于谓词逻辑的规划,STRIPS规划系统,分层规划,基于专家系统的机器人规划,轨迹规划简介等内容,欢迎点击下载。
人工智能第二章人工智能的数学基础ppt:这是人工智能第二章人工智能的数学基础ppt,包括了命题,谓词,谓词公式,概率论,随机现象,样本空间与随机事件,事件的概率,全概率公式与Bayes公式,模糊理论,模糊性,模糊集与隶属函数,模糊集的表示方法,模糊集的运算,模糊度,模糊关系及其合成,模糊变换,模糊集的水平截集,模糊数等内容,欢迎点击下载。
《人工智能chapter5heuristic ppt》是由用户slang于2018-03-29上传,属于行业PPT。

精品推荐 人工智能ppt

更多 ( 380 个) >> 人工智能ppt PPTOK为广大PPT爱好者展示用户上传的《人工智能》PPT集合大全,欢迎点击下载哦。人工智能(Artificial Intelligence),英文缩写为AI。它是研究、开发用于模拟、延伸和扩展......
  • 优秀PPT

    缩略图

    • 人工智能chapter5heuristic ppt

    下载地址

    • 人工智能chapter5heuristic ppt

    相关PPT

    推荐

    颜色分类黑色PPT模板橙色PPT模板紫色PPT模板蓝色PPT模板黄色PPT模板红色PPT模板绿色PPT模板彩色PPT模板黑白PPT模板

    行业分类科技PPT模板医学PPT模板教育PPT模板工业PPT模板金融PPT模板音乐PPT模板汽车房地产互联网培训手机

    实用必备个人简历自我介绍年终总结职业规划述职报告工作汇报工作总结岗位竞聘公司简介发布会年会论文答辩

    PPT推荐语文课件数学课件英语课件美术课件物理课件科学课件化学课件地理课件生物课件主题班会家长会绘本故事

    节日PPT新年元旦节农历春节情人节元宵节三八妇女节愚人节清明节五一劳动节母亲节六一儿童节端午节

    节日PPT 父亲节七夕情人节教师节中秋节国庆节重阳节万圣节光棍节感恩节平安夜圣诞节纪念日