资源描述：
《新人工智能5教程文件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、新人工智能55.1搜索策略的基本概念3.搜索类型：(1)根据是否使用启发信息分类：盲目搜索：按预定的控制策略进行，在搜索过程中获得的中间信息不改变控制策略。启发式搜索：在搜索过程中加入了与问题有关的启发性信息，用于指导搜索朝着最有希望的方向前进，加速问题的求解过程并找到最优解。25.1搜索策略的基本概念(2)根据问题的表示方式分类：状态空间搜索：用状态空间法来求解问题所进行的搜索。与/或树搜索：用问题归约法来求解问题时所进行的搜索。35.1搜索策略的基本概念5.1.2状态空间法1.状态空间表示法（1）状态(state):表示问题求解过程
2、中每一步问题状况的数据结构，形式的表示为：Sk={Sk0,Sk1,…)当对每一个分量都予以确定的值时，就得到了一个具体的状态。45.1搜索策略的基本概念（2）操作（operator)（算符）把问题从一种状态转换为另一种状态的手段。可以是一个机械步骤、一个运算、一条规则或一个过程。可理解为状态集合上的一个函数，描述了状态之间的关系。55.1搜索策略的基本概念（3）状态空间（statespace）描述一个问题的全部状态以及这些状态之间的相互关系。常用三元组表示:(S,F,G)S:为问题所有初始状态的集合。F:为操作的集合。G:为目标状态的集
3、合。65.1搜索策略的基本概念状态空间图：赋值的有向图。节点表示问题的状态，有向边表示操作.2.状态空间问题求解任何以状态和操作为基础的问题求解方法都称为状态空间问题求解。简称为状态空间法。状态空间法的基本过程为：（1）为问题选择适当的“状态”及“操作”的形式化描述方法。75.1搜索策略的基本概念（2）从某个初始状态出发，每次使用一个“操作”，递增地建立起操作序列，直到达到目标状态为止。（3）从初始状态到目标状态所使用的算符序列就是问题的一个解。85.1搜索策略的基本概念3.状态空间的例子例5.1:二阶梵塔问题：设有三根钢针，它们的编号
4、分别是1，2，3。在初始情况下，1号钢针上穿有A、B两个金片，A比B小，A位于B的上面。要求把这两个金片全部移到另一根钢针上，而且规定每次只能移动一个金片，任何时刻都不能使大片位于小片的上面。95.1搜索策略的基本概念解：设用Sk={Sk0,Sk1}表示问题的状态，其中，Sk0表示金片A所在的钢针号，Sk1表示金片B所在的钢针号。全部可能的问题状态共有以下9种：S0=(1,1)S1=(1,2)S2=(1,3)S3=(2,1)S4=(2,2)S5=(2,3)S6=(3,1)S7=(3,2)S8=(3,3)其中S0为初始状态，S4和S8为目
5、标状态。105.1搜索策略的基本概念任何以状态和操作为基础的问题求解方法都称为状态空间问题求解。简称为状态空间法。状态空间法的基本过程为：（1）为问题选择适当的“状态”及“操作”的形式化描述方法。（2）从某个初始状态出发，每次使用一个“操作”，递增地建立起操作序列，直到达到目标状态为止。（3）从初始状态到目标状态所使用的算符序列就是问题的一个解。115.1搜索策略的基本概念例5.2修道士和野人问题.首先选取描述问题状态的方法。用一个三元组表示状态：S=(m,c,b)其中：m表示左岸的修道士数；c表示左岸的野人数；b表示左岸的船数；125
6、.1搜索策略的基本概念右岸的状态由下式确定：右岸的修道士数m’=3-m；右岸的野人数c’=3-c；右岸的船数b’=1-b；m和c的取值分别为0，1，2，3之一；b的取值分别为0，1;共有4x4x2=32种状态。135.1搜索策略的基本概念3,32,12,31,21,3A(3,2)2,23,23,11,1B(1,2)A(1,3)二阶樊塔状态空间图145.1搜索策略的基本概念除去不合法的状态和修道士被野人吃掉的状态，余下的状态由16种：S0=(3,3,1),S1=(3,2,1),S2=(3,1,1),S3=(2,2,1),S4=(1,1,1
7、),S5=(0,3,1),S6=(0,2,1),S7=(0,1,1),S8=(3,2,0),S9=(3,1,0),S10=(3,0,0),S11=(2,2,0),S12=(1,1,0),S13=(0,2,0),S14=(0,1,0),S15=(0,0,0),155.1搜索策略的基本概念需要考虑的操作有：（1）船至少有一个人（m或c）操作，离开岸边的m和c的减少数目应该等于到达岸边的m和c的增加数目；（2）每次操作船上的人数不得超过2个；（3）操作应保证不产生非法状态。操作由两部分组成：条件部分和动作部分。165.1搜索策略的基本概念用Q
8、ij表示从右岸到左岸的运人操作，可供选择的操作由10种，操作集为：F={P01,P10,P11,P02,P20,Q01,Q10,Q11,Q02,Q20,}以P01和Q01为例说明操作的条件和动作：操作符号条
