人工智能-第4章 与或图搜索.ppt

《人工智能-第4章 与或图搜索.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第四章与或图搜索1问题归约法2与或图3与或图搜索4AO*算法5博弈树的搜索问题:在边长为2的正方形内，任意放置5个点，求证其中必存在两个点，它们之间的距离不大于2。问题可转化为：在四个单位正方形内，任意放置5个点，至少有两个点在同一正方形内。1问题归约法问题:假定我们已经会求矩形的面积，现在要求如图所示的五边形的面积。方法分析:五边形的面积转化为矩形面积。IIIII①②③123I求解步骤：求五边形面积求1面积求2面积求3面积求I面积求II面积求III面积求①面积求②面积求③面积123IIIIII①②③问题归约法:当问题复杂时，可把初始问题分解成若干简单的子问题，若子问题仍复杂，可再进一

2、步分解，直到这些子问题的解可直接得到。这种问题的描述和求解方法，称为~.本原问题:可直接解答的问题称为~，它是不必证明的、自然成立的.归约法的组成：1）一个初始问题的描述；2）一组把问题变成子问题的算子(分解或转换)；3） 一组本原问题的描述不同的算子对应不同的关系,从而使问题归约的描述可用一个与或图的结构来表示.小结:2与或图与节点：把单个问题分解为几个子问题来求解。只有当所有子问题都有解，该父辈节点才有解。表示一种“与”关系。或节点：同一问题被转换为几种不同的后继问题。只要有一个后继问题有解，则原问题有解。表示一种“或”关系。与节点由与运算连接（超弧），如图（a）.或节点由或运算连接，如图

3、（b）.定义：与或图就是包含与节点和或节点的图，即存在超弧的图，也称为超图.超图与状态空间图有什么区别？与或图是一种更一般的图.定义：一超弧所相关的边数（K）被称为该超弧的度，实现的连接称为K-连接.K—连接符：从一个父节点指向一组含有K个后继节点的节点集.在与或图中，节点n0有两个连接符：1-连接符指向节点n1；2-连接符指向节点集合{n4、n5}；对于节点n0来讲，n1可称为或节点，n4、n5可称为与节点。与或图3与或图搜索含义：在与或图上执行搜索的过程，其目的在于标明起始节点是有解的，即，搜索不是去寻找到目标节点的一条路径，而是寻找一个解图。定义：一个节点被称为能解节点，其递归定义为：1

4、．终节点是能解节点（直接与本原问题相关联）；2．若非终节点有“或”子节点时，当且仅当其子节点至少有一个能解，该非终节点才能解；3．若非终节点有“与”子节点时，当且仅当其子节点均能解，该非终节点才能解。定义：不能解节点的递归定义为:1．没有后裔的非终节点是不能解的节点；2．若非终节点有“或”子节点时，当且仅当所有子节点均不能解时，该非终节点才不能解；3．若非终节点有“与”子节点时，当至少有一子节点不能解时，该非终节点才不能解.是由能解节点构成的一个子图，是包含一节点（n）到目的(终)节点集合（N）的、连通的能解节点的子图.在一个与或图G中，从节点n到节点集N的解图记为G，G是G的子图.1．若

5、n是N的一个元素，则G由单个节点n组成；2．若n有一个指向节点集{n1…,nk}的外向连接符K，使得从每一个节点ni(i=1,…,k)到N有一个解图，则G由节点n，连接符K，以及{n1,…,nk}中的每一个节点到N的解图所组成；3．否则n到N不存在解图.如果n=s为初始节点，则解图为所求解问题的解图.解图的定义：若解图的耗散值记为k(n,N)，则可递归计算如下：若n是N的一个元素，则k(n,N)=0；若n有一个外向连接符指向其后继节点集合{n1…,ni}，并设该连接符的耗散值为Cn（一般k-连接符的耗散值=k），则k(n,N)=Cn+k(n1,N)+…+k(ni,N)具有最小耗散值的解图称

6、为最佳解图，其值也用h*(n)标记。解图耗散值的计算：例：从节点n开始，正确选择一个外向连接符，一直进行下去直到产生的每一个后继节点成为集合N中的一个元素为止。下图给出了n0→{n7，n8}的三个解图（耗散值分别为8，7，5）.解图的求法与或图搜索与状态空间图搜索的区别：搜索目的不同：是证明起始节点是否可解，而可解节点是递归定义的，取决于后继节点是否可解，即搜索过程是能否找到可解的叶节点.结果不同：若初始节点被标示为可解，则搜索成功结束；若初始节点被标示为不可解，则搜索失败.节点处理不同：一旦发现不可解节点，应把该节点从图中删去.4与或图启发式搜索算法AO*假设：G；G；h(n)是从节点n到

7、一组终叶节点的一个最优解图的一个代价估计，评价函数q(n)=h(n)AO*过程:1.建立初始搜索图，G:=s，计算q(s)=h(s)，IFGOAL(s)THENM(s,SOLVED)；2.Untils已标记为SOLVED,do:3.Begin4.G:=FIND(G)；根据连接符标记（指针）找出一个待扩展的侯选局部解图G（连接符在11步标记）5.n:=G中的任一非终节点;选一个当前节点6.EX