人工智能入门课件第2章 用搜索实现求解问题.ppt
《人工智能入门课件第2章 用搜索实现求解问题.ppt》由会员分享,可在线阅读,更多相关《人工智能入门课件第2章 用搜索实现求解问题.ppt(66页珍藏版)》请在文库网上搜索。
1、第2章 用搜索实现求解问题2.1 搜索求解问题的基本思路搜索求解问题的基本思路lAI早期的目的是想通过计算技术来求解这样一些问题:它们不存在现成的求解算法或求解方法非常复杂,而人使用其自身的智能都能较好地求解。为模拟这些问题的求解过程而发展的一种技术叫搜索。l搜索的过程可理解为根据初始条件和约束条件及关联关系构造一个解答空间,并在这个空间中寻找符合目标状态的过程。2.2实现搜索过程的三大要素实现搜索过程的三大要素l搜索过程的三大要素:搜搜索索对对象象、搜索的扩扩展展规规则则和搜索的目标测试目标测试。l搜搜索索对对象象是指在什么样的对象(即状态,这些状态就是可能解的表示)之上进行搜索;搜索的扩扩
2、展展规规则则是指如何控制从一种状态变化为另一种状态,使得搜索得以前进;搜索的目目标标测测试试是指搜索在什么条件下到达问题求解的要求。搜索终止时,搜索成功表示问题有解,否则表示问题无解。2.2.1 搜索搜索对象对象l 利用搜索来求解问题是在某个可能的解空间内寻找一个解,这就首先要有一种恰当的解空间的表示方法。一般把这种可能的解都表示为一个状态。这个过程必须做到把所有和解决问题相关的信息(特征)全部抽象出来,存储这些特征的数据结构被叫做状状态态,它表示问题的一个可可能能解解,这个数据结构下形成的各种有意义的状态,称为状态空间状态空间。l状态(state)是为描述某些不同事物间的差别而引入的一组最少
3、变量q0,q1,q2,qn的有序集合,并表示为:Q=(q0,q1,qn)其中,每个元素q称为状态变量。给定每个分量的一组值,就得到一个具体的状态。2.2.2 扩展规则l扩扩展展规规则则由两部分组成:状态转转移移算算子子和状态扩扩展展策略策略。l状态转移算子状态转移算子使问题从一种状态变化为另一种状态的手段称为操作符或转移算子(operator)。操作符可以是一个动作(如下棋走步)、过程、规则、数学算子、运算符号或逻辑运算符等。2.2.2 扩展规则状态扩展策略状态扩展策略 l宏观地看,以怎样的次序对问题对应的搜索图进行搜索,是搜索的技巧,也是智能的体现。没有目的随机的选一个扩展的话很容易实现,但
4、一般很难得到一个解或不能保证解的质量,即得不到一个满意解。而好的策略可以比一般的方法搜索更少的节点,更快地找到解。也就是说,根据问题的不同设计更合理的扩展策略可以提高搜索的效率。2.2.3目标测试 目标目标测试测试是在搜索过程中,对可能的解是否达到满意解的判断。它包含两种情况:l一种是,解是否满足所有限制条件(宽条件,成立的前提);l另一种是,解是否就是既定的目标(紧条件,目标状态已知)。l宽条件宽条件一般是指在目标状态未知,而求解只需要接近目标状态就行了的情况下设定的条件,比如说下棋,把对方将死的方式有很多种,满足一条就够了。l紧条件紧条件是在目标状态已知的条件下,直接判定是否已经达到这些状
5、态,比如说,玩魔方,成功的条件是六个面都是同色。2.3 实现搜索的基本步骤实现搜索的基本步骤l一般在搜索时要定义状态空间Q,它包含三种类型的集合:l l初始状态集合S,l l操作符集合F(把每个完成的动作表达出来)l l目标状态集合G。l因此,可把状态空间记为三元组(S,F,G)。问题状态空间法的基本思想是:l(1)将问题中的已知条件看成状态空间中初始状态;将问题中要求的目标看成状态空间中目标状态;将问题中其他可能的情况看成状态空间的任一状态。l(2)设法在状态空间中寻找一条路径,由初始状态出发,能够沿着这条路径达到目标状态。问题状态空间法的基本步骤:(1)根据问题,定义出相应的状态空间,确定
6、出状态的一般表示,它含有相关对象的各种可能的排列。这里仅仅是定义这个空间的状态,而不必枚举该状态空间的所有状态,但由此可以得出问题的初始状态、目标状态,并能够表示出所有其他状态。问题状态空间法的基本步骤:(2)规定一组操作(算子),能够使状态从一个状态变为另一个状态。(3)决定一种搜索策略,使得能够从初始状态出发,沿某个路径达到目标状态。水壶精确度量水量问题l播放电影视频给定两个水壶,一个可装5加仑水,一个能装3加仑水。水壶上没有任何度量标记。有一水龙头可用来往壶中灌水。问题是怎样在能装5加仑的水壶里,恰好只装4加仑水 l?(1)定义状态空间l该问题只关心水壶所装水的多少,可将问题进行抽象,用
7、数偶(x,y)来表示状态空间的任一状态。l x表示5加仑水壶中所装的水量,x=0到5;l y表示3加仑水壶中所装的水量,y=0到3;初始状态为(0,0),目标状态为(4,?),?表示水量不限,因为问题中未规定在3加仑水壶里装多少水。l初始状态为 (0,0)l目标状态为 (2,?)l?表示水量不限,因为问题中未规定在3加仑水壶里装多少水。(2)确定一组操作)确定一组操作l用来求解该问题的算子可用如下10条规则来描述。lr1:(X,Y|X5)(5,Y)5加仑水壶不满时,将其装满;lr2:(X,Y|Y0)(X-D,Y)从5加仑水壶里倒出一些水;lr4:(X,Y|Y0)(X,Y-D)从3加仑水壶里倒出
8、一些水;lr5:(X,Y|X0)(0,Y)把5加仑水壶中的水全部倒出;r6:(X,Y|Y0)(X,0)把3加仑水壶中的水全部倒出;r7:(X,Y|X+Y5Y0(5,Y-(5-X)把3加仑水壶中的水往5加仑水壶里倒,直至5加仑水壶装满为止;r8:(X,Y|X+Y3X0)(X-(3-Y),3)把5加仑水壶中的水往3加仑水壶里倒,直至3加仑水壶装满为止;r9:(X,Y|X+Y5Y0)(X+Y,0)把3加仑水壶中的水全部倒进5加仑水壶里;r10:(X,Y|X+Y3X0)(0,X+Y)把5加仑水壶中的水全部倒进3加仑水壶里 l这些算子就是模拟倒水的动作,也就是求解问题的过程。算子中的“”表示“如果则”;
9、“”表示并且。比如说,第8个算子r8表示的意思是:l如果两个水壶当前的水量为(x,y),两个水壶的水量加起来(即x+y)可以把3加仑水壶灌满(3)并且5加仑水壶里有水(X0),则把3加仑水壶加满(y=3),而5加仑水壶的水量变为X-(3-Y),即已经导入3加仑水壶3-y的水量了,要从5加仑水壶里减去。(3)选择一种搜索策略)选择一种搜索策略为求解水壶问题,除上面给出的问题描述和算子外,还应该选择一种策略控制搜索。该问题的策略为一个简单的循环控制结构:选择其左部匹配当前状态的某条规则,并按照该规则右部的描述,对此状态作适当改变,然后检查改变后的状态是否为某一目标状态,若不是,则继续该循环。该循环
10、结构如图2.3所示。l这样搜索下去,直到出现(4,?)状态为止,从(0,0)到(4,?)的路径上所用的操作序列就为所求的解。图2.4是求解问题的搜索图。l图2.4中有多个算子序列可以求解水壶问题,也就是有多条路径到达目标,下面就是求解问题的搜索路径之一:l5加仑水壶中含水量 3加仑水壶中含水量 所应用的规则l0 0 初始状态l5 0 r1l2 3 r3 l2 0 r6l0 2 r10 l5 2 r1 l4 3 r8 (动画实现)2.4 搜索的几种基本策略搜索的几种基本策略搜索的基本策略根据扩展的利用问题的特征信息的方搜索的基本策略根据扩展的利用问题的特征信息的方式可分为式可分为盲目搜索盲目搜索
11、、启发式搜索启发式搜索方法方法。盲目搜索方法盲目搜索方法又叫非启发式搜索,是一种无信息搜索又叫非启发式搜索,是一种无信息搜索(Uninformed Search),一般只适用于求解比较简),一般只适用于求解比较简单的问题。单的问题。启发式搜索启发式搜索就是要利用问题的特征信息(或一些线索)就是要利用问题的特征信息(或一些线索)来帮助(启发)自己选择搜索方向来帮助(启发)自己选择搜索方向。2.4.1 盲目的搜索方法盲目的搜索方法l当当我们在慌乱之中寻找东西的时候,毫无目标到处乱翻我们在慌乱之中寻找东西的时候,毫无目标到处乱翻,就是就是随机查找。随机查找。l当我们清醒时有条理地寻找东西的方法又大致
12、可以分成两当我们清醒时有条理地寻找东西的方法又大致可以分成两类:类:一种是找眼镜模式。它指的是眼镜掉了的时候总是从最近一种是找眼镜模式。它指的是眼镜掉了的时候总是从最近的地方开始寻找慢慢的扩大搜索范围的搜索方法。的地方开始寻找慢慢的扩大搜索范围的搜索方法。一种是走迷宫的方式。它指的是在走迷宫的时候由于无法一种是走迷宫的方式。它指的是在走迷宫的时候由于无法获得其他信息,只有一条路走到底,碰壁后再回溯寻找其获得其他信息,只有一条路走到底,碰壁后再回溯寻找其他途径的这种走法。他途径的这种走法。这三种方法分别对应的就是随机搜索、广度优先搜索和深度这三种方法分别对应的就是随机搜索、广度优先搜索和深度优先
13、搜索。优先搜索。1.宽度优先搜索宽度优先搜索l现在讨论的盲目的搜索算法中存放节点都采用一种简单的数据结构表,表是将节点按一定的顺序用逗号隔开放在一对括号中的一种数据结构,在表的首部和尾部的都可以加入和删除节点。l如果搜索是以同层邻近节点依次扩展节点的,那么这种搜索就叫宽度优先搜索,这种搜索是逐层进行的,在对下一层的任一节点进行搜索之前,必须搜索完本层的所有节点。宽度优先搜索宽度优先搜索算法如下:1.令N为一个由初始状态构成的表;2.若N为空退出,标志失败;3.令n为N中第一个点,将n从N中删除;4.若n是目标,则退出,标态成功;5.若n不是目标,将n的后继点加入到N表的尾部,转2。l宽度优先搜
14、索的优点是:若问题有解,则可找出最优解;l宽度优先搜索的缺点是:效率低,组合爆炸问题难以解决。2.深度优先搜索深度优先搜索在深度优先搜索中,我们首先扩展最新产生的(即最深的)节点。深度相等的节点可以任意排列。2.深度优先搜索深度优先搜索深度优先搜索算法如下:1.令N为一个由初始状态构成的表;2.若N为空退出,标态失败;3.令n为N中第一个点,将n从N中删除;4.若n是目标,则退出,标态成功;5.若n不是目标,将n的后继加入到N表的首部转2。2.深度优先搜索深度优先搜索l 深度优先搜索的优点:节省大量时间和空间;l 深度优先搜索的缺点:不一定能找到解。因为在无限搜索树的情况下,最坏的情况可能是不
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 人工智能入门课件第2章 用搜索实现求解问题 人工智能 入门 课件 搜索 实现 求解 问题