与或图搜索-copy北航6系人工智能

《与或图搜索-copy北航6系人工智能》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章问题求解基本原理搜索技术(二)基于问题空间的与或图搜索北京航空航天大学软件开发环境国家重点实验室Slide1基于问题空间的与或图搜索n与或图搜索有关概念§与或解图及其能解标记与费用计算§最佳与或解图的启发式搜索算法–AO*算法§AO*算法应用实例北京航空航天大学软件开发环境国家重点实验室Slide2与或图搜索有关概念n问题描述回顾-（S,S0,F,G)：wS：问题和子问题集合,S0：初始问题；wF：操作算子集合，用于将初始问题(或子问题)分解成更简单的子问题；wG：本原问题集合，其中每一个问题均是不言自

2、明的公理、已知事实等，或是已经证明的定理。北京航空航天大学软件开发环境国家重点实验室Slide3与或图搜索有关概念问题及子问题：{n0，n7，n8，n1，n2，……}分解规则:ifn0thenn1∨（n４∧n５）；n2ifnthenn∨n；１２３ifnthen（n∧n）；２４５n５ifnthen（n∧n）；３５６ifnthenn∨n；４５８ifnthenn∨（n∧n）；５６７８n８ifnthenn∧n；６７８动态搜索过程：初始问题:n0;1、隐含生成一个与或图;本原（终叶）问题:{nn}2、求解一个与或解图７

3、,８北京航空航天大学软件开发环境国家重点实验室Slide4与或图搜索有关概念§外向K-连接符：在与或图中，任一节点通过若干个外向k-连接符（k元算子）与其后继节点相连接，其中K=1的外向k-连接符：或连接符；K〉1的外向k-连接符：与连接符。n仅由K=1的外向k-连接符构成的搜索空间:普通有向图由K1的外向k-连接符构成的搜索空间:与或图。§无环与或图：与或图中，如果每一个后继节点不再是该节点的祖先节点，这种与或图称为无环与或图。北京航空航天大学软件开发环境国家重点实验室Slide5与或图搜索有关概念§问题

4、求解过程：北京航空航天大学软件开发环境国家重点实验室Slide6基于问题空间的与或图搜索n与或图搜索有关概念§与或解图及其能解标记与费用计算§最佳与或解图的启发式搜索算法–AO*算法§AO*算法应用实例北京航空航天大学软件开发环境国家重点实验室Slide7与或解图及其能解标记与费用计算n定义:与或图G中，从任一节点n到叶节点(本原问题)集合N的一个局部解图G’递归定义如下：v若n属于N,则此解图G’由单一节点{n}组成；v若n有一个指向节点{n1,n2,….,nk}的外向k-连接符（k≥1),而且从每一个ni

5、(i=1,2,….k)到N都有一个解图，则n到N的解图G’由节点n、连接符k以及{n1,n2,….,nk}中每个节点ni到N的解图组成。v否则，n到N无解图。北京航空航天大学软件开发环境国家重点实验室Slide8与或解图及其能解标记与费用计算按递归定义自上而下地生成以n为根节点的与或图一般算法：w选择n的一个外向k连接符，扩展其后继节点。w判断各后继节点是否属于N，w若否，则对该k连接符指向的每一个后继节点，选择一个外向k连接符的后继节点继续进行扩展；w上述过程周而复始，直到最底层的外向k连接符的每个后继节点

6、均属于N为止。针对任意节点的外向K连接符的选择顺序不同,对应的搜索策略可不同:盲目搜索，启发式搜索。北京航空航天大学软件开发环境国家重点实验室Slide9与或解图及其能解标记与费用计算定义:n标记能解节点（Solved)：w终叶节点是能解节点；w对于非终叶节点：•如果n有多个用k=1的连接符连接的或子节点，iff这些或子节点中至少有一个能解，节点n是能解节点；•如果n有用k>1的连接符连接的与子节点。Iff这些与子节点全部能解，节点n是能解节点。北京航空航天大学软件开发环境国家重点实验室Slide10与或解图

7、及其能解标记与费用计算n标记不能解节点（Unsolved)没有后裔的非终节点是不能解节点；w对于有后裔的非终节点n：•如果n有多个用k=1连接符连接的或子节点，iff所有这些或子节点均不能解，节点n是不能解节点；•如果n有用k>1连接符连接的与子节点。Iff这些与子节点中有一节点不能解，节点n是不能解节点。北京航空航天大学软件开发环境国家重点实验室Slide11与或解图及其能解标记与费用计算标记能解节点，求以n为根节点的与或解图：n８n８n８北京航空航天大学软件开发环境国家重点实验室Slide12与或解图及其

8、能解标记与费用计算n解图费用定义：设k-连接符的花费C(k)=k,以n为根节点的局部解图的费用C(n,N)可递归计算如下：w若n属于N,则C(n,N)=0；w若n有m个外向k-连接符（k≥1)。设其中第i个外向k-连接符的费用为Cni，其连接的后继节点为{ni1,ni2,….,nik}，则节点n通过此连接符到N的一个解图的费用为：C(n，N)i=Cni+C(ni1，N)+….+C(nik，N)m§最