人工智能3(1)搜索推理技术147

第3章确定性推理3.1图搜索策略3.2盲目搜索3.3启发式搜索2012-9-2113.3启发式搜索3.4消解原理3.5规则演绎系统3.6产生式系统3.7非单调推理概述(1)问题求解§AI中每个研究领域都有其各自的特点和规律,但就求解问题的过程看,都可抽象为一个问题求解过程。§问题求解过程实际上是一个搜索,广义地说,它包含了全部§问题求解过程实际上是一个搜索,广义地说,它包含了全部计算机科学。§任何问题求解技术都包括两个重要的方面:表示和搜索§表示是基本的,搜索必须要在表示的基础上进行。表示关系到搜索的效率。§本章讨论的表示主要包括:§状态空间表示§问题空间表示概述(2)q1974年，Nilsson归纳出的AI研究的基本问题知识的模型化和表示常识性推理、演绎和问题解决启发式搜索启发式搜索人工智能系统和语言q搜索是人工智能中的一个基本问题,是推理不可分割的一部分,直接关系到智能系统的性能和运行效率qAI为什么要研究search?问题没有直接的解法;需要探索地求解;搜索(3)什么是搜索§根据问题的实际情况不断寻找可利用的知识,构造出一条代价较少的推理路线,使问题得到圆满解决的过程称为搜索解决的过程称为搜索包括两个方面：---找到从初始事实到问题最终答案的一条推理路径---找到的这条路径在时间和空间上复杂度最小搜索(4)§盲目搜索:也称为无信息搜索，即只按预定的控制策略进行搜索,在搜索过程中获得的中间信息不用来改进控制策略§启发式搜索:在搜索中加入了与问题有关的启发性§启发式搜索:在搜索中加入了与问题有关的启发性信息,用于指导搜索朝着最有希望的方向进行,加速问题的求解过程并找到最优解要考虑的因素u完备性：当问题有解时，这个算法是否能保证找到一个解？u最优性：这个搜索策略是否能找到最优解？u时间复杂度：找到一个解需要花费多长时间？u空间复杂度：在执行搜索过程中需要有多少内存？2012-9-216无信息的搜索策略•广度优先搜索(Breadth-firstsearch)•代价一致搜索(Uniform-costsearch)2012-9-217•深度优先搜索(Depth-firstsearch)•深度有限搜索(Depth-limitedsearch)•双向搜索(Bidirectionalsearch)•迭代深度优先搜索(Iterativedeepeningdepth-firstsearch)有信息的搜索策略贪婪最佳优先搜索(Greedybest-firstsearch)A*搜索(A*search:Minimizingthetotalestimatedsolutioncost)递归最佳优先搜索(Recursivebest-firstsearch)2012-9-218递归最佳优先搜索(Recursivebest-firstsearch)爬山法搜索(Hill-climbingsearch)模拟退火搜索(Simulatedannealingsearch)局部剪枝搜索(Localbeamsearch)遗传算法(Geneticalgorithm)联机搜索(Onlinesearch)HeuristicsearchBeyondClassicalSearch状态空间表示法(1)q状态空间表示法：用来表示问题及其搜索过程的一种方法q状态：状态是描述问题求解过程中任一时刻状况的数据结构.23751486（2,3,7,0,5,1,4,8,6）状态空间表示法(2)q状态空间:由问题的全部状态及一切可用算符所构成的集合称为问题的状态空间.一般表示为:(S,F,G)S:问题所有的初始状态集合;F:算符集合;G:目标状态S:问题所有的初始状态集合;F:算符集合;G:目标状态集合q算符:引起状态中某些分量发生变化,从而使问题由一个状态变为另一个状态的操作称为算符.q状态空间表示法是用“状态”和“算符”表示问题的一种方法q状态空间图:状态空间的图式表示,称为状态空间图.其中节点表示状态,有向边(弧)表示算符.状态空间表示法(3)路径状态序列搜索寻找从初始状态到目标状态的路径;寻找从初始状态到目标状态的路径;S0Sg状态空间表示法（4）例1:二阶梵塔问题§设有三个钢针,在一号钢针上穿有A,B两个金片,A小于B,A位于B的上面.要求把这两个金片全部移到另一个钢针上,而且规定每次只能移动一片,任何时刻都不能使B位于A的上面§设用Sk=(Sk0,Sk1)表示问题的状态,SK0表示金片A所在的钢针号,SK1表示金片B所在的钢针号,全部可能的状态为:S0=(1,1),S1=(1,2),S3=(1,3)S4=(2,1),S5=(2,2),S6=(2,3)S7=(3,1),S8=(3,2),S9=(3,3)§问题初始状态集合S={S0},§目标状态集合G={S4,S8}.§算符:A(i,j):表示把金片A从第i号针移到第j号针上B(i,j):表示把B从第i号针移到第j号针上§共12个算符:§A(1,2),A(1,3),A(2,1),A(2,3),A(3,1),A(3,2)§B(1,2),B(1,3),B(2,1),B(2,3),B(3,1),B(3,2)状态空间表示法（5）用状态空间表示,首先必须定义状态的描述形式,把问题的一切状态都表示出来,其次定义算符,完成状态的转换问题的求解过程就是一个把算符不断地作用于状态的过程.如果在使用某个算符后得到的状态就是目标状态,就得到了问题的解.这个解就是从初始状态到目标状态所用算符构成的序列.个解就是从初始状态到目标状态所用算符构成的序列.算符的一次使用,就使问题由一种状态转变为另一种状态.可能有多个算符序列都可使问题从初始状态变到目标状态,这就得到了多个解.对任何一个状态,可使用的算符可能不止一个,这样由一个状态所生成的后继状态可能有多个.如何选择下一步的操作,由搜索策略决定.搜索控制策略（1）q搜索控制策略不可撤回的控制策略;试探性控制策略试探性控制策略回溯型图搜索搜索控制策略（2）不可撤回的控制策略例：八数码问题评价函数:f：（规定:评价函数非增）2831647512384765与的差异为4搜索控制策略（3）不可撤回的控制策略2831647528314765231847651123847651238476523184765f=4f=3f=3f=0f=1f=2搜索控制策略（4）不可撤回的控制策略2831476528314765832147658321476528132476581324765f=3f=3f=3f=3f=3f=313824765f=213824765f=1搜索控制策略（5）不可撤回的控制策略可能无解12584123848476384765目标f=2搜索控制策略（6）回溯策略例：四皇后问题QQQQ()()Q((1,1))()QQ((1,1))((1,1)(2,3))()Q((1,1))((1,1)(2,3))()QQ((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4))()QQ((1,1))((1,1)(2,3))((1,1)(2,4))Q((1,1)(2,4))((1,1)(2,4)(3.2))()QQ((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4))((1,1)(2,4)(3.2))()Q((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4))((1,1)(2,4)(3.2))()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4))((1,1)(2,4)(3.2))()((1,1))((1,1)(2,3))((1,1)(2,4))Q((1,2))((1,1)(2,4))((1,1)(2,4)(3.2))()((1,1))((1,1)(2,3))((1,1)(2,4))Q((1,2))Q((1,2)(2,4))((1,1)(2,4))((1,1)(2,4)(3.2))((1,2)(2,4))()((1,1))((1,1)(2,3))((1,1)(2,4))Q((1,2))Q((1,2)(2,4))Q((1,1)(2,4))((1,1)(2,4)(3.2))((1,2)(2,4))((1,2)(2,4)(3,1))QQQQ()((1,1))((1,1)(2,3))((1,1)(2,4))((1,2))((1,2)(2,4))((1,1)(2,4))((1,1)(2,4)(3.2))((1,2)(2,4))((1,2)(2,4)(3,1))((1,2)(2,4)(3,1)(4,3))3.1图搜索策略¾一些基本概念节点深度：根节点深度=0其它节点深度=父节点深度+12012-9-213301233.1图搜索策略¾一些基本概念路径设一节点序列为(n0,n1,…,nk)，对于i=1,…,k，若节点ni-1具有一个后继节点ni，则该序列称为从n0到nk的2012-9-2134i-1i0k路径。路径的耗散值一条路径的耗散值等于连接这条路径各节点间所有耗散值的总和。用C(ni,nj)表示从ni到nj的路径的耗散值。3.1图搜索策略¾一些基本概念扩展一个节点生成出该节点的所有后继节点，并给出它们之间的耗散值。这一过程称为“扩展一个节点”。2012-9-21353.1图搜索策略¾搜索搜索是AI中的一个基本问题，它与推理密切相关AI研究的对象大多是属于结构不良或非结构化的问题。很难获得全部信息，更无现成的算法可供求解使用，只有靠经验，利用已有知识逐步检索2012-9-2136求解使用，只有靠经验，利用已有知识逐步检索求解。不断寻找可利用知识，构造一条代价最小的推理路线，这一过程称搜索。对结构性较好，理论上有算法可依的问题，如果问题复杂，受计算机在时间和空间上的限制，也无法付诸实用。这就是组合爆炸问题，也可采用搜索的方法求解。3.1图搜索策略¾搜索状态空间具有树状结构的问题用图搜索。网络结构的状态空间图需化成树状结构才能应用这些搜索策略。在图的表示方法中，每一个节点对应一个状态，2012-9-2137在图的表示方法中，每一个节点对应一个状态，每条连线对应一个操作符，在产生式系统中分别用数据库和规则来标记。从图的初始节点开始至目标节点终止，分别代表初始数据库和满足终止条件的数据库。求得把一个数据库变换为另一数据库的规则序列问题就等价于求解图中的一条路径。3.1图搜索策略¾一般的图搜索算法1,G=G0(G0=s),OPEN=(s);2,CLOSED=();3,LOOP:IFOPEN=()EXIT(FAIL);2012-9-21383,LOOP:IFOPEN=()EXIT(FAIL);4,n=FIRST(OPEN),REMOVE(n,OPEN),ADD(n,CLOSED);5,IFGOAL(n)EXIT(SUCCESS);6,EXPAND(n)→{mi},G=ADD(mi,G);3.1图搜索策略¾一般的图搜索算法7,标记和修改指针：ADD(mj,OPEN),并标记mj到n的指针；2012-9-21398,对OPEN中的节点按某种原则重新排序；9,GOLOOP；S01262012-9-214023456扩展节点1以前的搜索图1262012-9-214123456扩展节点1后的搜索图3.2盲目搜索—宽度优先搜索如果搜索是以接近起始节点的程度依次扩展节点的，那么这种搜索就叫做宽度优先搜索。这种搜索是逐层进行的，在对下一层的任意节点进行搜索之前，必须搜索完2012-9-2142层的任意节点进行搜索之前，必须搜索完本层的所有节点。“先产生的节点先扩展”3.2盲目搜索—宽度优先搜索算法中要用一个OPEN表和一个CLOSED表。OPEN表中登录被产生的节点，此表中的节点都是等待扩展的。由于先产生的节2012-9-2143节点都是等待扩展的。由于先产生的节点优先扩展，所以该OPEN表是一个先进先出的顺序表。CLOSED表登录已被扩展的节点(中间节点或叶节点)3.2盲目搜索—宽度优先搜索OPEN表CLOSED表2012-9-2144状态