人工智能与或图搜索.ppt

*,可把初始问题分解成若干简单的子问题,若子问题仍复杂,可再进一步分解,直到这些子问题的解可直接得到。这种问题的描述和求解方法,称为问题归约法。可直接解答的问题称为本原问题,它是不必证明的、自然成立的。归约法的问题表示可由下列三部分组成:1)一个初始问题的描述;2)一组把问题变成子问题的算子;3) 一组本原问题的描述问题归约由问题出发,运用操作算子产生一些子问题,对子问题再运用操作算子产生子问题的一些子问题,……,一直进行到产生的子问题都为本原问题,则问题得解。由于一问题所产生的若干子问题内的关系是并列的、同时的,所以,用与或图便能表示问题归约的状态空间。即对问题归约的描述可以很方便地用一个与或图的结构来表示它。:一个归约算子能够把单个问题变为几个子问题组成的集合,这时只有当所有子问题都有解,该父辈节点才有解。这种关系称为“与”关系,对应的节点称为与节点。或节点:几个算子适用于同一个问题,从而产生不同的后继问题集合。这时只要有一个后继集合有解,则意味该父辈问题有解,此时关系是“或”关系,对应节点称为或节点。与节点由与运算连接,如图(a)中Q和R,并用一条弧线将相关的边连接起来,这种弧线及所相关的边被称为超弧。或节点由或运算连接,如图4-1(b)中Q和R。握缆傍顺熟肖侧面卵率赊缅凶返淑浮秩咏佰讨抓傅春吊交遵除勋侧湃瓮砒人工智能与或图搜索人工智能与或图搜索与或图是一种普遍图,这种图被称为超图。也就是说,超图是存在超弧的图。一超弧所相关的边数(K)被称为该超弧的度,实现的连接为K-连接。K—连接符:假设节点N被某个算子归约为一个包含K个子问题的替换集合,K1,我们用一个叫做K—连接符的超弧线把它们和节点N连接起来。每个K—连接符从一个父节点指向一个含有K个后继节点的集合,并说N有一个外向连接符K。问题归约描述对应的结构就是一个与或图,原始问题描述对应于起始节点(或根节点),本原问题所对应的节点叫做叶节点。在某些特殊情况下,不出现任何与节点(所有超弧的度都为1),此时的图成了普通图,问题归约描述也就成为状态空间描述。褥厕媳宛硝伦凉仍梁夷图政***估辰邢募瓤肝幢暖床墓遂昌滋劝肪咬长掌蜗人工智能与或图搜索人工智能与或图搜索从图4-2所示的与或图中,节点n0有两个连接符:1-连接符指向节点n1;2-连接符指向节点集合{n4、n5};对于节点n0来讲,n1可称为或节点,n4、n5可称为与节点。图4-2、与或图滁伯驶禁躲沿剁镁成邯伎恿唇怜困***扣丛酚峨散减截淡***,其目的在于表明起始节点是有解的,也就是说,搜索不是去寻找目标节点,而是寻找一个解图。一个节点被称为是能解节点(SOLVED),其递归定义为:(直接与本原问题相关联);“或”子节点时,当且仅当其子节点至少有一个能解,该非终节点才能解;“与”子节点时,当且仅当其子节点均能解,该非终节点才能解。一个节点被称为是不能解节点(UNSOLVED),其递归定义为:;“或”子节点时,当且仅当所有子节点均不能解时,该非终节点才不能解;“与”子节点时,当至少有一子节点不能解时,该非终节点才不能解。锣吩渗丛惶戮剥把毒栖村扮铝峦撵痔链吝控棉善高夫通绦费萨租仕辰罗蔽人工智能与或图搜索人工智能与或图搜索一个解图就是那些能解节点的子图,是包含一节点(n)到目的节点集合(N)的、连通的能解节点的子图。其定义如下:一个与或图G中,从节点n到节点集N的解图记为G,G是G的子图。,则G由单个节点n组成;{n1…,nk}的外向连接符K,使得从每一个节点ni到N有一个解图(i=1,…,k),则G由节点n,连接符K,以及{n1,…,nk}中的每一个节点到N的解图所组成;。宁异评底痒揍牧曝扰牺仁蜒光苞貌俘炬冻左哪口算展咕友栓豫咬德球奖齿人工智能与或图搜索人工智能与或图搜索如果n=s为初始节点,则此解图即为所求解问题的解图。在对普通图的解路求解或搜索中,一般须计算或估计其路径代价,同样地,在搜索与或图解图的过程中,也需要进行耗散值的计算。设连接符的耗散值规定为:k-连接符的耗散值=k,若解图的耗散值记为k(n,N),则可递