《人工智能及其应用》第03章

文学志南京信息工程大学计软学院2010年2月第3章搜索推理技术文学志南京信息工程大学计软学院2010年2月3.1搜索的含义3.2图搜索策略3.3盲目搜索3.3启发式搜索文学志南京信息工程大学计软学院2010年2月3.1搜索的含义文学志南京信息工程大学计软学院2010年2月搜索的含义人工智能所研究的对象大多属于结构不良或非结构化的问题，对于这些问题，一般很难获得其全部信息，更没有现成的算法可供求解使用。因此，只能依靠经验，利用已有知识逐步摸索求解。像这种根据问题的实际情况，不断寻找可利用知识，从而构造一条代价最小的推理路线，使问题得以解决的过程称为~。搜索的类型根据搜索过程是否使用启发式信息盲目搜索：按预定的控制策略进行搜索，在搜索过程中获得的中间信息并不改变控制策略。启发式搜索：在搜索中加入了与问题有关的启发性信息，用于指导搜索朝着最有希望的方向前进，加速问题的求解过程，并找到最优解。文学志南京信息工程大学计软学院2010年2月3.2图搜索策略文学志南京信息工程大学计软学院2010年2月图搜索策略的定义先把问题的初始状态作为当前扩展节点对其进行扩展，生成一组子节点，然后检查问题的目标状态是否出现在这些节点中。若出现，则搜索成功，找到了该问题的解；若没出现，则再按照某种搜索策略从已生成的子节点中选择一个节点作为当前节点。重复上述过程，直到目标状态出现在子节点中或者没有可供扩展的子节点为止。所谓对一个节点进行“扩展”是指对该节点用某个可用操作进行作用，生成该节点的一组子节点。图搜索算法中的几个重要名词术语OPEN表:用于存放刚生成的节点，由于这些节点还没有进行扩展，因此OPEN表也称为未扩展节点表；CLOSED表：用于存放已经扩展或将要扩展的节点，因此CLOSED表也称为已扩展节点表。文学志南京信息工程大学计软学院2010年2月图搜索(GRAPHSEARCH)的一般过程(1)建立一个只含有起始节点S的搜索图G，把S放到一个叫做OPEN的未扩展节点表中。(2)建立一个叫做CLOSED的已扩展节点表，其初始为空表。(3)LOOP：若OPEN表是空表，则失败退出。(4)选择OPEN表上的第一个节点，把它从OPEN表移出并放进CLOSED表中。称此节点为节点n。(5)若n为一目标节点，则有解并成功退出，此解是追踪图G中沿着指针从n到S这条路径而得到的(指针将在第7步中设置)。(6)扩展节点n，同时生成不是n的祖先的那些后继节点的集合M。把M的这些成员作为n的后继节点添入图G中。(7)对那些未曾在G中出现过的(既未曾在OPEN表上或CLOSED表上出现过的)M成员设置一个通向n的指针。把M的这些成员加进OPEN表。对已经在OPEN或CLOSED表上的每一个M成员，确定是否需要更改通到n的指针方向。对已在CLOSED表上的每个M成员，确定是否需要更改图G中通向它的每个后裔节点的指针方向。(8)按某一任意方式或按某个探试值，重排OPEN表。(9)GOLOOP。文学志南京信息工程大学计软学院2010年2月图搜索方法分析图搜索过程的第8步对OPEN表上的节点进行排序，以便能够从中选出一个“最好”的节点作为第4步扩展用。这种排序可以是任意的即盲目的(属于盲目搜索)，也可以用以后要讨论的各种启发思想或其它准则为依据(属于启发式搜索)。每当被选作扩展的节点为目标节点时，这一过程就宣告成功结束。这时，能够重现从起始节点到目标节点的这条成功路径，其办法是从目标节点按指针向S返回追溯。当搜索树不再剩有未被扩展的端节点时，过程就以失败告终(某些节点最终可能没有后继节点，所以OPEN表可能最后变成空表)。在失败终止的情况下，从起始节点出发，一定达不到目标节点。文学志南京信息工程大学计软学院2010年2月3.3盲目搜索文学志南京信息工程大学计软学院2010年2月3.2.1宽度优先搜索定义如果搜索是以接近起始节点的程度依次扩展节点的，那么这种搜索就叫做宽度优先搜索(breadth-firstsearch)。特点这种搜索是逐层进行的；在对下一层的任一节点进行搜索之前，必须搜索完本层的所有节点。文学志南京信息工程大学计软学院2010年2月宽度优先搜索算法(1)把起始节点放到OPEN表中(如果该起始节点为一目标节点，则求得一个解答)。(2)如果OPEN是个空表，则没有解，失败退出；否则继续。(3)把第一个节点(节点n)从OPEN表移出，并把它放入CLOSED的扩展节点表中。(4)扩展节点n。如果没有后继节点，则转向上述第(2)步。(5)把n的所有后继节点放到OPEN表的末端，并提供从这些后继节点回到n的指针。(6)如果n的任一个后继节点是个目标节点，则找到一个解答，成功退出；否则转向第(2)步。文学志南京信息工程大学计软学院2010年2月宽度优先搜索方法分析宽度优先搜索是图搜索一般过程的特殊情况，将图搜索一般过程中的第8步具体化为本算法中的第6步，这实际是将OPEN表作为“先进先出”的队列进行操作。宽度优先搜索方法能够保证在搜索树中找到一条通向目标节点的最短途径；这棵搜索树提供了所有存在的路径(如果没有路径存在，那么对有限图来说，我们就说该法失败退出；对于无限图来说，则永远不会终止)。举例把宽度优先搜索应用于八数码难题时所生成的搜索树，这个问题就是要把初始棋局变为如下目标棋局的问题：12384765提问：宽度优先搜索方法中OPEN表需要按什么方式进行操作？A．先进后出B．先进先出文学志南京信息工程大学计软学院2010年2月3.2.2深度优先搜索定义在此搜索中，首先扩展最新产生的(即最深的)节点。深度相等的节点可以任意排列。这种盲目(无信息)搜索叫做深度优先搜索(depth-firstsearch)。特点首先，扩展最深的节点的结果使得搜索沿着状态空间某条单一的路径从起始节点向下进行下去；只有当搜索到达一个没有后裔的状态时，它才考虑另一条替代的路径。文学志南京信息工程大学计软学院2010年2月2.2.2与或图表示与或图的有关定义可解节点：与或图中一个可解节点的一般定义可以归纳如下(1)终叶节点是可解节点(因为它们与本原问题相关连)。(2)如果某个非终叶节点含有或后继节点，那么只有当其后继节点至少有一个是可解的时，此非终叶节点才是可解的。(3)如果某个非终叶节点含有与后继节点，那么只要当其后继节点全部为可解时，此非终叶节点才是可解的。不可解节点：不可解节点的一般定义归纳于下(1)没有后裔的非终叶节点为不可解节点。(2)如果某个非终叶节点含有或后继节点，那么只有当其全部后裔为不可解时，此非终叶节点才是不可解的。(3)如果某个非终叶节点含有与后继节点，那么只要当其后裔至少有一个为不可解时，此非终叶节点才是不可解的。文学志南京信息工程大学计软学院2010年2月2.2.2与或图表示与或图构图规则(1)与或图中的每个节点代表一个要解决的单一问题或问题集合。图中所含起始节点对应于原始问题。(2)对应于本原问题的节点，叫做终叶节点，它没有后裔。(3)对于把算符应用于问题A的每种可能情况，都把问题变换为一个子问题集合；有向弧线自A指向后继节点，表示所求得的子问题集合。(4)一般对于代表两个或两个以上子问题集合的每个节点，有向弧线从此节点指向此子问题集合中的各个节点。(5)在特殊情况下，当只有一个算符可应用于问题A，而且这个算符产生具有一个以上子问题的某个集合时，由上述规则3和规则4所产生的图可以得到简化。文学志南京信息工程大学计软学院2010年2月3.4启发式搜索文学志南京信息工程大学计软学院2010年2月3.4.1启发式搜索策略和估价函数语法和语义谓词逻辑的基本组成部分是谓词符号、变量符号、函数符号和常量符号，并用圆括弧、方括弧、花括弧和逗号隔开，以表示论域内的关系。原子公式是由若干谓词符号和项组成，只有当其对应的语句在定义域内为真时，才具有值T(真)；而当其对应的语句在定义域内为假时，该原子公式才具有值F(假)。连词和量词连词有∧(与)、∨(或)，全称量词(x)，存在量词(x)。原子公式是谓词演算的基本积木块，运用连词能够组合多个原子公式以构成比较复杂的合适公式。文学志南京信息工程大学计软学院2010年2月3.4.2有序搜索几个有关定义用连词∧把几个公式连接起来而构成的公式叫做合取，而此合取式的每个组成部分叫做合取项。一些合适公式所构成的任一合取也是一个合式公式。用连词∨把几个公式连接起来所构成的公式叫做析取，而此析取式的每一组成部分叫做析取项。由一些合适公式所构成的任一析取也是一个析取公式。用连词→连接两个公式所构成的公式叫做蕴涵。蕴涵的左式叫做前项，右式叫做后项。如果前项和后项都是合适公式，那么蕴涵也是合适公式。前面具有符号～的公式叫做否定。一个合适公式的否定也是合适公式。量化一个合适公式中的某个变量所得到的表达式也是合适公式。如果一个合适公式中某个变量是经过量化的，就把这个变量叫做约束变量，否则就叫它为自由变量。在合适公式中，感兴趣的主要是所有变量都是受约束的。这样的合适公式叫做句子。文学志南京信息工程大学计软学院2010年2月2.3.2谓词公式谓词合式公式的定义在谓词演算中合适公式的递归定义如下：(1)原子谓词公式是合适公式。(2)若A为合适公式，则～A也是一个合适公式。(3)若A和B都是合适公式，则(A∧B)，(A∨B)，(A=B)和(A←→B)也都是合适公式。(4)若A是合适公式，x为A中的自由变元，则(x)A和(x)A都是合适公式。(5)只有按上述规则(1)至(4)求得的那些公式，才是合适公式。文学志南京信息工程大学计软学院2010年2月2.3.2谓词公式合适公式的性质(1)否定之否定～(～P)等价于P(2)P∨Q等价于～P→Q(3)狄·摩根定律～(P∨Q)等价于～P∧～Q～(P∧Q)等价于～P∨～Q(4)分配律P∧(Q∨R)等价于(P∧Q)∨(P∧R)P∨(Q∧R)等价于(P∨Q)∧(P∨R)(5)交换律P∧Q等价于Q∧PP∨Q等价于Q∨P(6)结合律(P∧Q)∧R等价于P∧(Q∧R)(P∨Q)∨R等价于P∨(Q∨R)文学志南京信息工程大学计软学院2010年2月2.3.2谓词公式合适公式的性质(7)逆否律P→Q等价于～Q→～P此外，还可建立下列等价关系：(8)～(x)P(x)等价于(x)［～P(x)］～(x)P(x)等价于(x)［～P(x)］(9)(x)［P(x)∧Q(x)］等价于(x)P(x)∧(x)Q(x)(x)［P(x)∨Q(x)］等价于(x)P(x)∨(x)Q(x)(10)(x)P(x)等价于(y)P(y)(x)P(x)等价于(y)P(y)文学志南京信息工程大学计软学院2010年2月2.3.3置换与合一置换假元推理：就是由合适公式W1和W1→W2产生合适公式W2的运算。全称化推理：是由合适公式(x)W(x)产生合适公式W(A)，其中A为任意常量符号。一个表达式的置换就是在该表达式中用置换项置换变量。一般说来，置换是可结合的，但置换是不可交换的。合一寻找项对变量的置换，以使两表达式一致，叫做合一(unification)。如果一个置换s作用于表达式集｛Ei｝的每个元素，则用｛Ei｝s来表示置换例的集。称表达式集｛Ei｝是可合一的。如果存在一个置换s使得：E1s=E2s=E3s=…那么称此s为｛Ei｝的合一者，因为s的作用是使集合｛Ei｝成为单一形式。举例：表达式P［x,f(y),B］的一个置换为s1=｛z/x,w/y｝，则：P［x,f(y),B］s1=P［z,f(w),B］文学志南京信息工程大学计软学院2010年2月本章小结主要内容状态空间法是一种基于解答空间的问题表示和求解方法，它是以状态和操作符为基础的。在利用状态空间图表示时，从某个初始状态开始，每次加一个操作符，递增地建立起操作符的试验序列，直到达到目标状态为止。由于状态空间法需要扩展过多的节点，容易出现“组合爆炸”，因而只适用于表示比较简单的问题。问题归约法从目标(要解决的问题)出发，逆向推理，通过一系列变换把初始问题变换为子问题集合和子子问题集合，直至最后归约为一个平凡的本原问题集合。这些