人工智能第三章基本问题求解方法

第三章基本的问题求解方法,问题求解的过程：1）知识表示；2）针对问题，分析特征，选择合适的方法来求解（包括搜索和推理）方法：1）基于状态图方法-搜索；2）基于谓词逻辑方法-推理；3）基于结构化的知识表示方法来求解问题；本章介绍搜索技术,搜索技术是人工智能的基本技术之一,在人工智能各应用领域中被广泛地使用。早期的人工智能程序与搜索技术联系就更为紧密，几乎所有的早期的人工智能程序都是以搜索为基础的。A.Newell和HASimon-LT程序ANewell和HASimon-GPS(GeneralProblemSolver)R.Fikes和N.Nilsson-STRIPS(StanfordResearchInstituteProblemSolver)现在,搜索技术渗透在各种人工智能系统中,在专家系统、自然语言理解、自动程序设计、模式识别、机器人学、信息检索和博奕都广泛使用。,搜索(search),路径状态序列搜索寻找从初始状态到目标状态的路径;,搜索的必要性,AI为什么要研究search?问题没有直接的解法;解方程组;定理证明;需要探索地求解;,搜索与检索的区别,状态是否动态生成;检索:静态;在数据库中检索某人的纪录;搜索:动态生成;下棋,几个问题,目标状态是否确定?确定:定理证明,eight-puzzle不确定:求积分,下棋;确定目标的性质;问题的解:路径(解路径)/目标状态;需要路径:下棋不需要路径:电路设计需要/不需要:诊病约束条件目标状态不确定时,用来约束目标状态的性质;X+Y=4:非整数解/整数解,几个问题(续1),多解性;X+Y=4:整数解最优解评价标准/判断准则;min(x*y)北京-上海:时间最短/费用最少最优解是否唯一?下棋,搜索问题,状态空间,搜索不是检索,难点,启发式方法,搜索方法的评价标准,搜索问题是AI核心理论问题之一。一般一个问题可以用好几种搜索技术解决,选择一种好的搜索技术对解决问题的效率很有关系,甚至关系到求解问题有没有解。搜索方法好的标准,一般认为有两个：(1)搜索空间小;(2)解最佳。,搜索分类,搜索从问题性质上来看,可分为一般搜索和博奕搜索,从处理方法上来看,可分为盲目搜索和启发式搜索。还可以分得更细。到目前为止,AI领域中已提出许多具体的搜索方法,概括起来有：(1)求任一解路的搜索策略回溯法；爬山法(HillClimbing)；宽度优先法(Breadth-first)；深度优先法(Depth-first)(2)求最佳解路的搜索策略大英博物馆法(BritishMuseum)；最佳图搜索法(A*)(3)求与或关系解图的搜索法一般与或图搜索法(AO*)；极小极大法(Minimax)剪枝法(Alpha-betaPruning)；启发式剪枝法(HeuristicPruning),TOPICS,回溯策略（Backtracking）图搜索（GRAPHSEARCH）无信息搜索启发式搜索,TOPIC1Backtracking,回溯策略,例：四皇后问题,(),(),Q,(1,1),(),Q,Q,(1,1),(1,1)(2,3),(),Q,(1,1),(1,1)(2,3),(),Q,Q,(1,1),(1,1)(2,3),(1,1)(2,4),(),Q,Q,(1,1),(1,1)(2,3),(1,1)(2,4),Q,(1,1)(2,4)(3.2),(),Q,Q,(1,1),(1,1)(2,3),(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)(3.2),(),(1,1),(1,1)(2,3),(1,1)(2,4),(1,1)(2,4)(3.2),(),(1,1),(1,1)(2,3),(1,1)(2,4),(1,1)(2,4)(3.2),Q,(1,2),(),(1,1),(1,1)(2,3),(1,1)(2,4),(1,1)(2,4)(3.2),Q,(1,2),Q,(1,2)(2,4),(),(1,1),(1,1)(2,3),(1,1)(2,4),(1,1)(2,4)(3.2),Q,(1,2),Q,(1,2)(2,4),Q,(1,2)(2,4)(3,1),存在问题及解决办法,问题和解决方法：深度问题对搜索深度加以限制死循环问题状态重复:AB，BC,CA记录从初始状态到当前状态的路径,TOPIC2GRAPHSEARCH,图搜索策略问题的引出回溯搜索：只保留从初始状态到当前状态的一条路径。图搜索：保留所有已经搜索过的路径。,N5,一些基本概念,图：一个节点的集合。节点由弧连接起来。有向图：弧是一个节点指向另一个节点的图，称为有向图。后继/父亲：如果有一条弧从ni指向nj，则nj称为ni的后继，ni称为nj的父辈（父亲）；,一些基本概念(续1),路径：如果存在一个节点序列（ni0，ni1，nik），nij是nij-1是的后继，j=1，k，则称这个序列是从节点ni0到节点nik的一条路径，长度为k。祖先/后裔：如果存在一条从ni到nj的路径，则称nj是ni的后裔，ni称为nj的祖先。树：每个节点最多只有一个父辈。没有父辈的节点称为根节点。没有后继的节点称为叶节点。,一些基本概念(续2),节点深度：根节点深度=0其它节点深度=父节点深度+1,0,1,2,3,一些基本概念（续3）,扩展一个节点生成出该节点的所有后继节点。弧的费用有一条弧连接ni和nj两个节点,用C(ni,nj)表示使用规则从ni到nj的费用(耗散值)。玉泉路-天安门路径的耗散值一条路径的耗散值等于连接这条路径各节点间所有耗散值的总和。用C(ni,nj)表示从ni到nj的路径的耗散值。,GRAPHSEARCH的思路,OPEN表已经生成但未扩展节点CLOSED表已扩展节点扩展节点i生成节点j指针调整指针,图搜索（GraphSearch）的一般过程,1、建立一个只有起始节点S的搜索图G，把S放入一个叫open的未扩展节点表；2、建立已扩展节点表closed，初始为空；3、LOOP；若open为空，则失败退出；4、选open表中的第一个节点，设为n，移入closed表；5、若n为目标节点，则成功退出，该问题的解即是G中沿S指向n的路径；6、若不是目标节点，则扩展n，生成不是n的祖先的那些后继节点的集合m，把m的成员作为n的后继加入G中；7、对未曾在G中出现过的m成员，设一通向n的指针，把它们加入open表。对已在closed或open表上的m成员，确定是否要更改到n的指针方向，对已在closed上的m成员，确定是否要更改G中通向每个后裔节点的指针方向。8、按某一方式（深度优先、宽度优先、A*算法）重排open表9、GOLOOP,例子,例：右图中黑节点表示已扩展，白节点表示未扩展，问题：先扩展6号节点生成m1=4，7，然后扩展节点1，生成m2=2，按算法第七步重新修改原图。,6,1,2,4,5,3,难点！算法中第七步,7,扩展节点6生成m1=4，7的调整,再扩展节点1生成m2=2的调整,最终结果,图搜索与回溯算法的区别,扩展节点:回溯算法:生成一个儿子节点.图搜索:扩展节点,生成所有儿子节点.候选节点:回溯算法:一个.图搜索:多个.回溯:回溯算法:返回父亲节点.图搜索:不一定返回父亲节点.,TOPIC3无信息搜索,如果在GRAPHSEARCH中，对节点的排序不使用与问题相关的信息，则称为无信息图搜索（盲目搜索）宽度优先和深度优先,1、breadth-firstsearch,宽度优先搜索：如果搜索是以接近起始节点的程度依次扩展节点的。搜索逐层进行；在对下一层的任一节点进行搜索之前，必须搜索完本层的所有节点。,(1)把起始节点放到OPEN表中(如果该起始节点为一目标节点，则求得一个解答)。(2)如果OPEN是个空表，则没有解，失败退出；否则继续。(3)把第一个节点(节点n)从OPEN表移出，并把它放入CLOSED的扩展节点表中。(4)扩展节点n。如果没有后继节点，则转向上述第(2)步。(5)把n的所有后继节点放到OPEN表的末端，并提供从这些后继节点回到n的指针。(6)如果n的任一个后继节点是个目标节点，则找到一个解答，成功退出；否则转向第(2)步。,算法,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,21,22,23,24,26,27,28,29,30,31,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,搜索演示,已扩展节点正在扩展节点,扩展的子节点未扩展节点,目标,宽度优先法应用示例,宽度优先法求九宫重排问题,23184765,1,2,5,6,7,3,目标,8,4,宽度优先搜索是图搜索一般过程的特殊情况，将图搜索一般过程中的第8步具体化为本算法中的第6步，这实际是将OPEN表作为“先进先出”的队列进行操作。一定能找到解找到的解一定是最佳解(在每个路径消耗是同样的意义上)搜索的空间大、慢。,分析,深度优先搜索：首先扩展最新产生的(即最深的)节点。深度相等的节点可以任意排列。特点：扩展最深的节点,使得搜索沿着状态空间某条单一的路径从起始节点向下进行下去；只有当搜索到达一个没有后裔的状态时，它才考虑另一条替代的路径。算法：与宽度优先相似，不同在于：(5)把n的所有后继节点放到OPEN表的前端,2、depth-firstsearch,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,23,24,26,27,28,29,30,31,1,2,活结点表,1,1,2,1,1,2,4,2,2,4,8,4,4,8,16,8,8,16,16,8,17,8,8,17,17,8,8,4,9,4,4,9,18,9,9,18,18,9,19,9,19,19,4,4,2,5,2,2,5,10,5,5,10,20,9,9,9,10,10,20,20,10,21,10,10,21,21,10,10,5,11,5,5,11,演示,例九宫重排问题,836475,初始状态,12384765,目标状态,应用示例,23184765,1,2,3,4,5,6,7,8,9,a,b,d,目标,分析,不一定能找到解。解不一定是最佳解。,3、其他方法,含有深度界限的深度优先搜索算法：基于代价树的搜索算法：,TOPIC4heuristicsearch,盲目搜索效率低，耗费过多的计算空间与时间，这是组合爆炸的一种表现形式。利用知识来引导搜索，达到减少搜索范围，降低问题复杂度的目的。启发式方法的本质是部分地放弃算法一般化,通用化的概念,把所要解的问题的具体领域的知识加进算法中去,以提高算法的效率。,启发式搜索：就是利用与问题有关的启发信息进行搜索启发信息：与具体问题有关的特性信息启发信息的强度强：降低搜索工作量，但可能导致找不到最优解弱：一般导致工作量加大，极限情况下变为盲目搜索，但可能可以找到最优解难点：获取；强度的确定；,启发信息的用途,a、用于决定要扩展的下一节点（避免盲目扩展）b、在扩展过程中，用于决定生成哪一个或哪几个后继（以免太多无用节点）C、用于决定被抛弃or被修剪的节点（博羿中常用，其它不常见）。,基本思想,启发式搜索过程中,要对OPEN表进行排序,这就需要有一种方法来计算待扩展节点有希望通向目标节点的不同程度,我们总是希望能找到最有希望通向目标节点的待扩展节点优先扩展。希望的量度就是通过估价函数f（n）来描述的,估价函数：定义为从初始节点经过n节点到达目的节点的路径的最小代价的估计值，,X,W,Z,g(X),h(X),估价函数的形式为f(n)=g(n)+h(n)g（n）是到目前为止,从s到n的最小路径（实际值）h（n）n节点到目标节点最佳路径的估计值，体现了启发信息通常f（n）由经验和直觉得到的，有很多种取法，关键在于h（n）。,eg八数码难题的估价函数f（n）=g（n）+h（n）d（n）：节点n的深度w（n）：不在位的数字个数p（n）：不在位的数字离目标的距离之和例：右图（a）中2、8、1、6不在位，w（n）=4，p（n）=1+2+1+1=5；（b）6、8、2、1不在位，w（n）=4，p（n）=3+2+2+2=9,s（n）：沿着周围那些非中心方格上依顺时针方向检查n格局中每一将牌，如果其后紧跟的将牌正好是目标格局中该将牌的后续者，则该将牌得0分，否则得2分；在中中方格上有将牌得1分，无得0分；将所有将牌得分之和即为s（n）。图（c）中s（a）=6。,例子:eight-puzzle,评价函数f(n)=d(n)+W(n)d(n):节点n的深度;W(n):与目标相比,错位的数字数目，即不在位的数字个数;,初始状态,目标状态,28316475,s(4),A(6),B(4),C(6),D(5),E(5),F(6),G(6),H(7),I(5),J(7),K(5),L(5),M(7),目标,1,2,3,4,5,6,由前例看出,与深度优先搜索和宽度优先搜索相比较,启发式搜索大大减少了搜索范围,大大减少了扩展的节点,大大减少了生成的节点,从而达到降低问题复杂度,提高算法的效率的目的。,估价函数的进一步说明,f*(n)=g*(n)+h*(n)：从s经过n到g的最短路径g*(n)：从s到n的最短路径h*(n)：从n到g的最短路径f（n）=g（n）+h（n）：从s经过n到g的最短路径的估计值g(n)、h(n)分别是g*(n)、h*(n)的估计值,g(n)一般取实际走过的路径的费用和.g(n)g*(n)随着算法的执行，由于指针的变动，g(n)会下降.h0没有启发式信息;,启发式搜索算法,A算法A*算法,A算法,在Graphsearch过程中，如果第8步的重排open表是依据f（n）=g（n）+h（n）进行的，则称该过程为A算法。g(n)取实际走过的路径的费用和;节点排序是按照f(n)从小到大排;如前例-九宫重排问题,算法A*,在A算法中，如果满足条件：0h(n)h*(n)则A算法称为A*算法。称h（x）为h*（x）的下界，它表示某种偏于保守的估计。启发式搜索算法A*又称为最佳图搜索算法(OptimalSearch)。,5、经典例题（八数码难题）：设有八数码难题，起始状态如右图，要求找出九宫重排的最终解路径，并画框图。,28316475,解法一：第一步：取估价函数为f（n）=d（n）+w（n），则显然按照定义1它是A算法；第二步：因为w（n）指的是不在位的个数，所以w（n）=4，即估计只需要走4步即可到达目标状态，而实际上要到达目标状态肯定要大于3步，即w（x）w*（x），满足定义，所以是A*算法；第三步：画图，并计算各个状态f（n）的值，取f（n）值最小的节点进行扩充。(图见前),解法二：取估价函数为f（n）=d（n）+P（n），同理也是A*算法；如图,TipsA算法与A*算法区别,区别在于在A*算法中，0h(n)h*(n)示例：八数码难题中h(n)的三种定义h(n)=w(n),h(n)=p(n)-A*算法h(n)=p(n)+3s(n)-A算法,A*算法具有可采纳性,一般地说对任意一个图,当s到目标节点有一条路径存在时,如果搜索算法总是在找到一条从s到目标节点的最佳路径上结束,则称该搜索算法是可采纳的(Admissibility)。,A*就具有可采纳性即当问题有解时,A*一定能找到一条到达目标节点的最佳路径。（why？）,证明见参考资料-A*算法具有可采纳性考虑h(n)0的情况！,A*算法的理论意义,A*算法的理论意义在于给出了求解最佳解的条件h(n)h*(n),对给定的问题,函数h*(n)在问题有解的条件下客观上是存在的。但在问题求解过程中不可能都明确知道。因此,对实际问题,能不能使所定义的启发函数满足下界范围条件?这是个问题。如果困难很大,那未A*算法的实际应用就会受到限制。,以前面-八数码难题为例定义h(n)为任意节点与目标之间的差异若取=w(n)(将牌不在位个数),那未很容易看出,尽管我们对具体的h*(n)是多少很难确切知道,但根据“不在位”将牌个数这个估计,就能得出至少要移动W(n)步才能到达目标,显然有h(n)=W(n)h*(n)。进一步考虑任意节点与目标之间距离的信息,即取h(n)=p(n),p(n)定义为每一个将牌与其目标位置之间距离(不考虑夹在其间的将牌)的总和,那未同样能断定至少也要移动p(n)步才能达到目标，仍然有P(n)h*(n)。,启发信息的