资源描述：
《人工智能课件-搜索技术》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、搜索策略搜索是人工智能中的一个基本问题，并与推理密切相关，搜索策略的优劣，将直接影响到智能系统的性能与推理效率。主要内容状态空间的表示搜索的基本概念状态空间的搜索状态空间的一般搜索过程盲目搜索启发式搜索概述问题求解AI中每个研究领域都有其各自的特点和规律,但就求解问题的过程看,都可抽象为一个问题求解过程.问题求解过程实际上是一个搜索,广义地说,它包含了全部计算机科学1974年，Nilsson归纳出的AI研究的基本问题知识的模型化和表示常识性推理、演绎和问题解决启发式搜索人工智能系统和语言本章讨论的表示主要包
2、括:状态空间表示问题空间表示搜索的基本概念搜索的含义状态空间法适用情况：不良结构或非结构化问题；难以获得求解所需的全部信息；更没有现成的算法可供求解使用。概念：依靠经验，利用已有知识，根据问题的实际情况，不断寻找可利用知识，从而构造一条代价最小的推理路线，使问题得以解决的过程称为搜索搜索的类型按是否使用启发式信息：盲目搜索：按预定的控制策略进行搜索，在搜索过程中获得的中间信息并不改变控制策略。启发式搜索：在搜索中加入了与问题有关的启发性信息，用于指导搜索朝着最有希望的方向前进，加速问题的求解过程并找到最优解
3、。按问题的表示方式：状态空间搜索：用状态空间法来求解问题所进行的搜索与或树搜索：用问题归约法来求解问题时所进行的搜索什么是搜索根据问题的实际情况不断寻找可利用的知识,构造出一条代价较少的推理路线,使问题得到圆满解决的过程称为搜索包括两个方面：---找到从初始事实到问题最终答案的一条推理路径---找到的这条路径在时间和空间上复杂度最小搜索分两大类:盲目搜索:也称为无信息搜索，即只按预定的控制策略进行搜索,在搜索过程中获得的中间信息不用来改进控制策略启发式搜索:在搜索中加入了与问题有关的启发性信息,用于指导搜索
4、朝着最有希望的方向进行,加速问题的求解过程并找到最优解状态空间法状态(State)：是表示问题求解过程中每一步问题状况的数据结构，它可形式地表示为：Sk={Sk0,Sk1,…}当对每一个分量都给以确定的值时，就得到了一个具体的状态。操作(Operator)也称为算符，它是把问题从一种状态变换为另一种状态的手段。操作可以是一个机械步骤，一个运算，一条规则或一个过程。操作可理解为状态集合上的一个函数，它描述了状态之间的关系。状态空间(Statespace)用来描述一个问题的全部状态以及这些状态之间的相互关系。常
5、用一个三元组表示为：(S,F,G)其中，S为问题的所有初始状态的集合；F为操作的集合；G为目标状态的集合。状态空间也可用一个赋值的有向图来表示，该有向图称为状态空间图。在状态空间图中，节点表示问题的状态，有向边表示操作。状态空间表示法状态空间表示法是用来表示问题及其搜索过程的一种方法状态状态是描述问题求解过程中任一时刻状况的数据结构.23751486{A，B，C，D}（2,3,7,0,5,2,4,8,6）状态空间表示法一般一个搜索问题由四个部分组成：初始状态集合：定义了agent所处的环境；操作符集合：把一
6、个问题从一个状态变换为另一个状态的动作；目标检测函数：agent用来确定一个状态是不是目标；路径费用函数：对每条路径赋予一定费用的函数。初始状态集合和操作符集合定义了问题的搜索空间状态空间法求解问题的基本过程：首先为问题选择适当的“状态”及“操作”的形式化描述方法；然后从某个初始状态出发，每次使用一个“操作”，递增地建立起操作序列，直到达到目标状态为止；此时，由初始状态到目标状态所使用的算符序列就是该问题的一个解。八数码问题states数字的位置，共有9！/2=181440actions空格的上下左右移动g
7、oaltest给定的目标状态pathcost每一步消耗为1二阶梵塔问题二阶梵塔问题。设有三根钢针，它们的编号分别是1号、2号和3号。在初始情况下，1号钢针上穿有A、B两个金片，A比B小，A位于B的上面。要求把这两个金片全部移到另一根钢针上，而且规定每次只能移动一个金片，任何时刻都不能使大的位于小的上面。解：设用Sk=(Sk0,Sk1)表示问题的状态，其中，Sk0表示金片A所在的钢针号，Sk1表示金片B所在的钢针号。全部可能的问题状态共有以下9种：S0=(1,1)S1=(1,2)S2=(1,3)S3=(2,1
8、)S4=(2,2)S5=(2,3)S6=(3,1)S7=(3,2)S8=(3,3)ABABAB123123123二阶梵塔问题的初始状态和目标状态问题的初始状态集合为S={S0}目标状态集合为G={S4,S5}初始状态S0和目标状态S4、S8如图所示S0=(1,1)S4=(2,2)S8=(3,3)操作分别用A(i,j)和B(i,j)表示A(i,j)表示把金片A从第i号钢针移到j号钢针上；B(i,j)表示把金片B从第
