资源描述：
《人工智能 第三章 搜索策略ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、搜索是人工智能中的一个基本问题，并与推理密切相关，搜索策略的优劣，将直接影响到智能系统的性能与推理效率。3.1搜索概述3.1.1搜索的含义3.1.2状态空间问题求解方法3.1.3问题归约求解方法3.2搜索的盲目策略3.3状态空间的启发式搜索3.4与/或树的启发式搜索3.5博弈树的启发式搜索第3章搜索策略13.1.1搜索的含义概念：依靠经验，利用已有知识，根据问题的实际情况，不断寻找可利用知识，从而构造一条代价最小的推理路线，使问题得以解决的过程称为搜索适用情况：不良结构或非结构化问题；难以获得求解所需的全部信息；更没有现成的算法可供求解使用。搜索的类型按是否使用启发
2、式信息：盲目搜索：按预定的控制策略进行搜索，在搜索过程中获得的中间信息并不改变控制策略。启发式搜索：在搜索中加入了与问题有关的启发性信息，用于指导搜索朝着最有希望的方向前进，加速问题的求解过程并找到最优解。按问题的表示方式：状态空间搜索：用状态空间法来求解问题所进行的搜索与或树搜索：用问题归约法来求解问题时所进行的搜索23.1.2状态空间问题求解方法1.状态空间问题表示状态(State)是表示问题求解过程中每一步问题状况的数据结构，它可形式地表示为：Sk={Sk0,Sk1,…}当对每一个分量都给以确定的值时，就得到了一个具体的状态。操作(Operator)也称为算符
3、，它是把问题从一种状态变换为另一种状态的手段。它可理解为状态集合上的一个函数，它描述了状态之间的关系。状态空间(Statespace)用来描述一个问题的全部状态以及这些状态之间的相互关系。常用一个三元组表示为：(S,F,G)其中，S为问题的所有初始状态集合；F为操作的集合；G为目标状态的集合。状态空间也可用一个赋值的有向图来表示，该有向图称为状态空间图。在状态空间图中，节点表示问题的状态，有向边表示操作。3状态空间法求解问题的基本过程：首先，为问题选择适当的“状态”及“操作”的形式化描述方法；然后，从某个初始状态出发，每次使用一个“操作”，递增地建立起操作序列，直到
4、达到目标状态为止；最后，由初始状态到目标状态所使用的算符序列就是该问题的一个解。3.1.2状态空间问题求解方法2.状态空间问题求解4例3.1二阶梵塔问题设有三根钢针，它们的编号分别是1号、2号和3号。在初始情况下，1号钢针上穿有A、B两个金片，A比B小，A位于B的上面。要求把这两个金片全部移到另一根钢针上，而且规定每次只能移动一个金片，任何时刻都不能使大的位于小的上面。解：设用Sk=(SkA,SkB)表示问题的状态，其中，SkA表示金片A所在的钢针号，SkB表示金片B所在的钢针号。全部可能的问题状态共有以下9种：S0=(1,1)S1=(1,2)S2=(1,3)S3=
5、(2,1)S4=(2,2)S5=(2,3)S6=(3,1)S7=(3,2)S8=(3,3)3.1.2状态空间问题求解方法3.状态空间的例子(1/14)5ABABAB123123123图3.1二阶梵塔问题的初始状态和目标状态初始状态集合S={S0}目标状态集合G={S4,S8}初始状态S0和目标状态S4、S8如下图S0=(1,1)S4=(2,2)S8=(3,3)3.1.2状态空间问题求解方法3.状态空间的例子(2/14)6操作Aij表示把金片A从第i号钢针移到j号钢针上；Bij表示把金片B从第i号钢针一到第j号钢针上。共有12种操作，它们分别是：A12A13A21A2
6、3A31A32B12B13B21B23B31B32根据上述9种可能的状态和12种操作，可构成二阶梵塔问题的状态空间图，如下图所示。3.1.2状态空间问题求解方法3.状态空间的例子(3/14)7从初始节点(1,1)到目标节点(2,2)及(3,3)的任何一条路径都是问题的一个解。其中，最短的路径长度是3，它由3个操作组成。例如，从(1,1)开始，通过使用操作A13、B12及A32，可到达(3,3)。(1,1)B12A13(2,1)(3,2)(2,3)(3,3)(1,3)(3,1)(1,2)(2,2)A32A12B13A233.1.2状态空间问题求解方法3.状态空间的例子
7、(4/14)图3.2二阶梵塔的状态空间图8例3.2修道士(Missionaries)和野人(Cannibals)问题(简称M-C问题)。设在河的一岸有3个野人、3个修道士和1条船，修道士想用这条船把所有的人运到河对岸，但受以下条件的约束：第一，修道士和野人都会划船，但每次船上至多可载2个人；第二，在河的任一岸，如果野人数目超过修道士数，修道士会被野人吃掉。如果野人会服从任何一次过河安排，请规划一个确保修道士和野人都能过河，且没有修道士被野人吃掉的安全过河计划。解：先选取描述问题状态的方法。这里，需要考虑两岸的修道士人数和野人数，还需要考虑船在左岸还是在右岸，故可
