7 人工智能与专家系统(GIS).ppt
《7 人工智能与专家系统(GIS).ppt》由会员分享,可在线阅读,更多相关《7 人工智能与专家系统(GIS).ppt(59页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、第五章第五章 问题求解策略问题求解策略5.1 5.1 搜索基本原理搜索基本原理5.2 5.2 图搜索策略图搜索策略5.3 5.3 盲目搜索盲目搜索5.4 5.4 启发式搜索启发式搜索1搜索与问题求解l问题求解过程是搜索答案问题求解过程是搜索答案(目标目标)的过程的过程/所以所以问题求解技术也叫搜索技术问题求解技术也叫搜索技术通过对状态空间通过对状态空间的搜索而求解问题的技术的搜索而求解问题的技术问题求解智能体是一种基于目标的智能体在寻找到达目标的过程中,当智能体面对多个未知的选项时,首先检验各个不同的导致已知评价的状态的可能行动序列,然后选择最佳序列这个过程就是搜索2问题与问题的解l问题可以形
2、式化地定义为4个组成部分智能体的初始状态(即搜索的开始)后继函数智能体采取的可能行动的描述,通常为/初始状态和后继函数隐含地定义了问题的状态空间/状态空间中的一条路径是通过行动序列连接起来的一个状态序列目标测试检查给定的状态是不是目标路径耗散函数每条路径都有一个数值化的耗散值,反映了性能度量/求解问题的代价3问题的解l问题的解就是初始状态到目标状态的路径解的优劣由路径耗散函数量度(代价)最优解就是路径耗散函数值最小的路径l上述解题过程把解决一个问题的过程描述出来,称之为解题知识的过程性表示过程性知识与陈述性知识相对l搜索过程解题的特点没有直接的方法(公式)可以求解,而是一步一步的探索4状态空间
3、状态空间l数数据据基基:代代表表了了所所要要解解决决的的问问题题,有有初初始始状状态态,可能有目标状态也可能没有可能有目标状态也可能没有l状状态态空空间间:在在解解题题过过程程中中的的每每一一时时刻刻,数数据据基基都都处处于于一一定定的的状状态态,数数据据基基所所有有可可能能状状态态的的集集合称为状态空间合称为状态空间l有有向向图图:若若把把每每个个状状态态看看成成一一个个节节点点,则则整整个个状状态态空空间间是是一一个个有有向向图图/该该图图不不一一定定全全连连通通,即从某些状态不一定能到达另外一些状态即从某些状态不一定能到达另外一些状态5问题的可解性l可解的:在每个连通部分,每个弧代表一个
4、运算符,将状态改变/如果从代表初始状态的节点出发,有一条路径通向目标状态,则称此目标状态所代表的问题在当前初始状态下是可解的l搜索空间:在解题过程中达到过的所有状态的集合,称为搜索空间不同于状态空间,搜索空间只是其中一部分状态空间和搜索空间都属于过程性知识表示6问题实例l玩具问题八数码游戏(九宫图)河内塔八皇后问题真空吸尘器世界l现实问题旅行商问题超大规模集成电路的布局自动装配排序/蛋白质设计互联网搜索7八数码游戏l八数码游戏:八数码游戏:1-8数字数字(棋子棋子)/9个方格个方格(棋盘格棋盘格)/1个空格个空格l可用如下形式的规则来表示数字通过空格进行移动:可用如下形式的规则来表示数字通过空
5、格进行移动:l共共24条规则条规则=4角角*2+4边边*3+1中间中间*4l搜索顺序举例:搜索顺序举例:(1)优先移动行数小的棋子优先移动行数小的棋子(数字数字)(2)同一行中优先移动列数大的棋子同一行中优先移动列数大的棋子l约束规则:不使离开既定位置的数字数增加约束规则:不使离开既定位置的数字数增加8八数码游戏的搜索树既定位置=终态9八数码问题形式化l初始状态初始状态向量规定向量中各分量对应的位置,各位置上的初始数字l后继函数移动规则按照某条规则移动数字,将得到的新向量l目标测试新向量是否是目标状态(也是向量形式)l路径耗散函数每次移动代价为1105.1 搜索基本原理 问题求解的基本方法有:
6、搜索法、归约问题求解的基本方法有:搜索法、归约法、归结法、推理法和产生式等。法、归结法、推理法和产生式等。搜索技术是人工智能的核心技术之一。搜索技术是人工智能的核心技术之一。对于无成熟方法可用的问题求解,对于无成熟方法可用的问题求解,只能只能利用已有的知识利用已有的知识一步步地摸索求解,这种一步步地摸索求解,这种问题求解过程就是搜索。问题求解过程就是搜索。11 搜索过程是否一定能找到解;搜索过程是否一定能找到解;搜索过程是否终止运行或是否会陷入死循环;搜索过程是否终止运行或是否会陷入死循环;当搜索过程找到一个解时,是否为最佳解;当搜索过程找到一个解时,是否为最佳解;搜索过程的时间与空间复杂性如
7、何。搜索过程的时间与空间复杂性如何。搜索的基本问题搜索的基本问题12 搜索的主要过程搜索的主要过程(1)从初始或目的状态出发,并将它作为当前状态;)从初始或目的状态出发,并将它作为当前状态;(2)扫描操作算子集,运用操作算子得到新的状态,)扫描操作算子集,运用操作算子得到新的状态,并建立指向其父节点的指针;并建立指向其父节点的指针;(3)检查新状态是否满足结束状态,如果满足,则得)检查新状态是否满足结束状态,如果满足,则得到解,给出解答路径;否则将新状态作为当前状态,到解,给出解答路径;否则将新状态作为当前状态,返回第(返回第(2)步再进行搜索。)步再进行搜索。13 搜索方向搜索方向 从初始状
8、态出发的正向搜索,也称为数据驱动;从初始状态出发的正向搜索,也称为数据驱动;从目的状态出发的逆向搜索,也称为目的驱动;从目的状态出发的逆向搜索,也称为目的驱动;从初始状态出发作正向搜索,同时又从目的状态出从初始状态出发作正向搜索,同时又从目的状态出发作逆向搜索,直到两条路径在中间的某处汇合发作逆向搜索,直到两条路径在中间的某处汇合为止,这称为双向搜索;为止,这称为双向搜索;在不具有对特定问题的任何有关信息的条件下,按在不具有对特定问题的任何有关信息的条件下,按固定的步骤进行搜索,这是盲目搜索。固定的步骤进行搜索,这是盲目搜索。14l有限搜索还是无限搜索?有限搜索还是无限搜索?若搜索空间有限,则
9、任何一种穷举算法均能完若搜索空间有限,则任何一种穷举算法均能完成任务。成任务。l搜索空间是静态的还是动态生成的?搜索空间是静态的还是动态生成的?在人工智能中,搜索的对象在人工智能中,搜索的对象(常称状态常称状态)是在搜是在搜索过程中逐步生成的,需将搜索对象的生成和索过程中逐步生成的,需将搜索对象的生成和评估的代价计算在内。对于一般搜索,搜索空评估的代价计算在内。对于一般搜索,搜索空间基本是静态的,或表或数组或数据库。间基本是静态的,或表或数组或数据库。l已知目标还是未知目标?已知目标还是未知目标?l只要目标还是也要路径?路径是解题过程中应只要目标还是也要路径?路径是解题过程中应用的操作序列。用
10、的操作序列。研究和选用搜索算法的原则研究和选用搜索算法的原则15l状态空间搜索还是问题空间搜索?状态空间搜索还是问题空间搜索?在解题过程中的每一时刻,所要解决的问题均在解题过程中的每一时刻,所要解决的问题均处于一定的状态,搜索过程只是将一个状态变处于一定的状态,搜索过程只是将一个状态变成另一个状态成另一个状态(如,一盘棋局变成另一盘棋局如,一盘棋局变成另一盘棋局),则称为状态空间搜索。,则称为状态空间搜索。若搜索的对象是问题,搜索的原则是把一个复若搜索的对象是问题,搜索的原则是把一个复杂的问题化为一组比较简单的子问题杂的问题化为一组比较简单的子问题(如把一个如把一个复杂的下棋策略分为几个子策略
11、复杂的下棋策略分为几个子策略),则称为问题,则称为问题空间搜索。空间搜索。注:问题空间搜索常常比状态空间搜索有效,但注:问题空间搜索常常比状态空间搜索有效,但算法要复杂些。算法要复杂些。研究和选用搜索算法的原则研究和选用搜索算法的原则16l有约束还是无约束?有约束还是无约束?问题空间搜索时,若子问题间互相无约束关系,问题空间搜索时,若子问题间互相无约束关系,则比较简单,否则需要回溯,即放弃已解决的子则比较简单,否则需要回溯,即放弃已解决的子问题,走回头路,寻找新的解法。问题,走回头路,寻找新的解法。l数据驱动还是目标驱动?数据驱动还是目标驱动?数据驱动是向前搜索,目标驱动是向后搜索。数据驱动是
12、向前搜索,目标驱动是向后搜索。l单向搜索还是双向搜索?单向搜索还是双向搜索?l盲目搜索还是启发式搜索?盲目搜索还是启发式搜索?按照预定的控制策略实行搜索,在搜索过程中按照预定的控制策略实行搜索,在搜索过程中获取的中间信息不用来改进控制策略,称为盲目获取的中间信息不用来改进控制策略,称为盲目搜索,反之,称为启发式搜索。搜索,反之,称为启发式搜索。研究和选用搜索算法的原则研究和选用搜索算法的原则17一般搜索方法分类一般搜索方法分类盲盲目目搜搜索索是是按按预预定定的的控控制制策策略略进进行行,在在搜搜索索的的过过程程中中所所获获得得的的信信息息不不用用来来改改进进控控制制策略的一种搜索。策略的一种搜
13、索。启启发发式式搜搜索索是是在在搜搜索索中中加加入入了了与与问问题题有有关关的的启启发发式式信信息息,用用来来指指导导搜搜索索朝朝着着最最有有希希望望的的方方向向前前进进,加加速速问问题题的的求求解解过过程程,并并找到最优解。找到最优解。18一般搜索方法分类一般搜索方法分类 盲目搜索盲目搜索 1)无变量的盲目搜索无变量的盲目搜索l 状态空间、问题空间的盲目搜索状态空间、问题空间的盲目搜索l 深度优先、广度优先、代价优先、混合深度优先、广度优先、代价优先、混合l 向前、向后、双向向前、向后、双向 2)有变量的盲目搜索有变量的盲目搜索 通代通代 启发式搜索启发式搜索 195.2 5.2 图搜索策略
14、图搜索策略l图搜索策略可以看成是一种在图中寻找图搜索策略可以看成是一种在图中寻找路径的方法。初始结点和目标结点分别路径的方法。初始结点和目标结点分别代表初始数据库和满足终止条件的数据代表初始数据库和满足终止条件的数据库。求得把一个数据库变换为另一个数库。求得把一个数据库变换为另一个数据库规则序列问题就等于求得图中的一据库规则序列问题就等于求得图中的一条路径问题。条路径问题。20图图搜搜索索过过程程框框图图 21l一般图搜索算法中,提高搜索效率的关键一般图搜索算法中,提高搜索效率的关键在于优化在于优化OPEN表中节点的排序方式,若表中节点的排序方式,若每次排在表首的节点都在最终搜索到的解每次排在
15、表首的节点都在最终搜索到的解答路径上,则算法不会扩展任何多余的节答路径上,则算法不会扩展任何多余的节点就可快速结束搜索。所以排序方式成为点就可快速结束搜索。所以排序方式成为研究搜索算法的焦点,并由此形成了多种研究搜索算法的焦点,并由此形成了多种搜索策略。搜索策略。22l盲目搜索又叫做无信息搜索,一般只适用于求解比盲目搜索又叫做无信息搜索,一般只适用于求解比较简单的问题。较简单的问题。l宽度优先搜索和深度优先搜索,均属于盲目搜索方宽度优先搜索和深度优先搜索,均属于盲目搜索方法。法。l其共同缺点是节点排序的盲目性,由于不采用领域其共同缺点是节点排序的盲目性,由于不采用领域专门知识去指导排序,往往会
16、搜索了大量无关的状专门知识去指导排序,往往会搜索了大量无关的状态节点后才碰到解答,所以称为盲目搜索。态节点后才碰到解答,所以称为盲目搜索。5.3 5.3 盲目搜索盲目搜索23 宽度优先搜索宽度优先搜索 l宽度优先搜索(宽度优先搜索(breadth-first search)的)的定义:如果搜索是以接近起始节点的程度定义:如果搜索是以接近起始节点的程度依次扩展节点的,那么这种搜索就叫做宽依次扩展节点的,那么这种搜索就叫做宽度优先搜索(度优先搜索(breadth-first search)。)。l特点:这种搜索是逐层进行的;在对下一特点:这种搜索是逐层进行的;在对下一层的任一节点进行搜索之前,必须
17、搜索完层的任一节点进行搜索之前,必须搜索完本层的所有节点。本层的所有节点。24宽度优先搜索示意图宽度优先搜索示意图 25宽度优先搜索算法宽度优先搜索算法(1)把起始节点放到把起始节点放到OPEN表中(如果该起始节点为一表中(如果该起始节点为一目标节点,则求得一个解答)。目标节点,则求得一个解答)。(2)如果如果OPEN是个空表,则没有解,失败退出;否则是个空表,则没有解,失败退出;否则继续。继续。(3)把第一个节点(节点)把第一个节点(节点 n)从)从OPEN表移出,并把它表移出,并把它放入放入CLOSED扩展节点表中。扩展节点表中。(4)扩展节点)扩展节点n。若没有后继节点,则转向上述第(。
18、若没有后继节点,则转向上述第(2)步。步。(5)把把n 的所有后继节点放到的所有后继节点放到OPEN表的末端,并提供表的末端,并提供从这些后继节点回到从这些后继节点回到n的指针。的指针。(6)如果如果n 的任一个后继节点是个目标节点,则找到一的任一个后继节点是个目标节点,则找到一个解答,成功退出;否则转向第(个解答,成功退出;否则转向第(2)步。)步。26宽宽度度优优先先算算法法框框图图27宽度优先搜索方法分析宽度优先搜索方法分析 l宽度优先搜索方法能够保证在搜索树中找到一条宽度优先搜索方法能够保证在搜索树中找到一条通向目标节点的最短途径;这棵搜索树提供了所通向目标节点的最短途径;这棵搜索树提
19、供了所有存在的路径(如果没有路径存在,那么对有限有存在的路径(如果没有路径存在,那么对有限图来说,我们图来说,我们 就说该法就说该法 失败失败 退出;对于退出;对于 无限无限图来说,则永远不会终止)。图来说,则永远不会终止)。l例:把宽度优先搜索应用于八数码难题时所生成例:把宽度优先搜索应用于八数码难题时所生成的搜索树,这个问题就是要把初始棋局变为如图的搜索树,这个问题就是要把初始棋局变为如图所示的目标棋局问题。所示的目标棋局问题。28八数码难题的宽度八数码难题的宽度优先搜索树优先搜索树 29宽度优先搜索宽度优先搜索l搜索树上的所有节点都标记它们所对应的搜索树上的所有节点都标记它们所对应的状态
20、描述,每个节点旁边的数字表示节点状态描述,每个节点旁边的数字表示节点扩展的顺序(按顺时针方向移动空格)。扩展的顺序(按顺时针方向移动空格)。图中最后一个节点是目标节点。图中最后一个节点是目标节点。30 深度优先搜索深度优先搜索(depth-first search)31 深度优先搜索深度优先搜索l分析深度优先搜索示意图可看出,在深度优先搜分析深度优先搜索示意图可看出,在深度优先搜索中,我们首先扩展最新产生的(即最深的)节索中,我们首先扩展最新产生的(即最深的)节点。深度相等的节点可以任意排列。点。深度相等的节点可以任意排列。l定义节点的深度如下:定义节点的深度如下:(1)起始节点(即根节点)的
21、深度为起始节点(即根节点)的深度为0。(2)任何其它节点的深度等于其父辈节点深度加任何其它节点的深度等于其父辈节点深度加上上1。32l首先,扩展最深的节点的结果使得搜索沿着状态首先,扩展最深的节点的结果使得搜索沿着状态空间某条单一的路径从起始节点向下进行下去;空间某条单一的路径从起始节点向下进行下去;只有当搜索到达一个没有后裔的状态时,它才考只有当搜索到达一个没有后裔的状态时,它才考虑另一条替代的路径。替代路径与前面已经试过虑另一条替代的路径。替代路径与前面已经试过的路径不同之处仅仅在于改变最后的路径不同之处仅仅在于改变最后n步,而且保步,而且保持持n尽可能小。尽可能小。33深度界限深度界限l
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 人工智能与专家系统GIS 人工智能 专家系统 GIS
限制150内