资源描述：
《第2章 问题求解与搜索技术ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第2章问题求解与搜索技术2021/7/301《人工智能》人工智能问题广义地说，都可以看做是一个问题求解过程，因此问题求解是人工智能的核心问题，它通常是通过在某个可能的解空间中寻找一个解来实现。问题求解一般需要考虑两个基本问题：首先是使用合适的状态空间表示问题，其次是测试该状态空间中目标状态是否出现。在问题求解过程中，人们所面临的大多数实际问题往往没有确定性的算法，通常需要用搜索算法来解决。目标和达到目标的一组方法称为问题，搜索就是探究这些方法能够做什么的过程。2021/7/302《人工智能》2.1问题表示2.2图搜索策略2.3盲目搜索策略2.4启发
2、式搜索策略2.5与或树搜索策略本章主要内容：2021/7/303《人工智能》2.1问题表示人工智能所要解决的问题大多是结构不良或非结构化的问题，对这样的问题，智能系统的行为一般是找到能够达到所希望目标的动作序列，并使其所付出的代价最小，性能最好。基于给定的问题，问题求解的第一步是问题表示。问题表示就是描述该问题的一些基本信息，一般包括4部分：（1）初始状态集合：定义了初始的环境；（2）操作符集合：把一个问题从一个状态变成另一个状态的动作；（3）目标检测函数：用来确定一个状态是不是目标；（4）路径费用函数：对每一条路径赋予一定费用的函数。2021/7
3、/304《人工智能》2.1.1状态空间表示法1、问题状态描述状态（State）的基本概念状态(state)是为描述某类不同事物间的差别而引入的一组最少变量q0，q1，…，qn的有序集合，其矢量形式如下：Q=［q0,q1,…,qn］式中每个元素qi(i=0,1，…，n)为集合的分量，称为状态变量。给定每个分量的一组值就得到一个具体的状态，如Qk=［q０k,q1k,…，qnk］算符：使问题从一种状态变化为另一种状态的手段称为操作符或算符。操作符可为走步、过程、规则、数学算子、运算符号或逻辑符号等。2021/7/305《人工智能》问题的状态空间(stat
4、espace)是一个表示该问题全部可能状态及其关系的图，它包含三种说明的集合，即所有可能的问题初始状态集合S、操作符集合F以及目标状态集合G。因此，可把状态空间记为三元状态(S，F，G)。状态空间的表示法对一个问题的状态描述，必须确定3件事：(1)该状态描述方式，特别是初始状态描述；(2)操作符集合及其对状态描述的作用；(3)目标状态描述的特性。2021/7/306《人工智能》2.1.1状态空间表示法（2）2、状态图示法图的基本概念：图由节点(不一定是有限的节点)的集合构成。一对节点用弧线连接起来，从一个节点指向另一个节点。这种图叫做有向图。某个节
5、点序列(ni1,ni2,…,nik)当j=2，3，…，k时，如果对于每一个nij-1都有一个后继节点nij存在，那么就把这个节点序列叫做从节点ni1至节点nik的长度为k的路径。代价(cost)是给各弧线指定数值以表示加在相应算符上的代价。图的显式说明是指各节点及其具有代价的弧线由一张表明确给出。图的隐式说明是指各节点及其具有代价的弧线不能由一张表明确给出。2021/7/307《人工智能》2.1.1状态空间表示法（3）3、状态空间表示发举例二阶梵塔问题设用SK=(Sk0,Sk1)表示问题的状态，SK0表示金片A所在的柱号，Sk1表示金片B所在的柱号
6、，全部可能的状态有九种：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)问题的初始状态集合为S={S0},目标状态集合为G={S4,S8}。算符分别用A(i,j)及B(i,j)。A(i,j)表示把A金片从第i号柱移到第j号柱。B(i,j)与之同理。算符共有12个。2021/7/308《人工智能》1,12,12,33,11,33,22,21,23,3A(1,3)B(1,2)A(3,2)在状态空间图中，从初始节点(1,1)到目标节点(2,2)或(
7、3,3)的任何一条通路都是问题的一个解。其中最短的路径长度是3，它由3个算符组成。例如:A(1,3),B(1,2),A(3,2)2021/7/309《人工智能》猴子与香蕉问题acb箱子状态空间表示用四元组（W，x，y，z）。其中：W-猴子的水平位置；x－当猴子在箱子顶上时取x=1；否则取x=0；Y－箱子的水平位置；z-当猴子摘到香蕉时取z=1；否则取z=0。算符(1)goto(U)猴子走到水平位置U；(2)pushbox(V)猴子把箱子推到水平位置V；(3)climbbox猴子爬上箱顶；(4)grasp猴子摘到香蕉。2021/7/3010《人工智能
8、》猴子与香蕉问题求解过程令初始状态为(a,0,c,0)。这时，goto(U)是唯一适用的操作，并导致下一状态(U，0，c,
