与或图搜索

北京航空航天大学软件开发环境国家重点实验室Slide1第二章问题求解基本原理搜索技术(二)基于问题空间的与或图搜索北京航空航天大学软件开发环境国家重点实验室Slide2基于问题空间的与或图搜索与或图搜索有关概念与或解图及其能解标记与费用计算最佳与或解图的启发式搜索算法–AO*算法AO*算法应用实例北京航空航天大学软件开发环境国家重点实验室Slide3与或图搜索有关概念问题描述回顾-（S,S0,F,G)：S：问题和子问题集合,S0：初始问题；F：操作算子集合，用于将初始问题(或子问题)分解成更简单的子问题；G：本原问题集合，其中每一个问题均是不言自明的公理、已知事实等，或是已经证明的定理。北京航空航天大学软件开发环境国家重点实验室Slide4与或图搜索有关概念分解规则:ifn0thenn1∨（n４∧n５）；ifn１thenn２∨n３；ifn２then（n４∧n５）；ifn３then（n５∧n６）；ifn４thenn５∨n８；ifn５thenn６∨（n７∧n８）；ifn６thenn７∧n８；n2n５n８初始问题:n0;本原（终叶）问题:{n７,n８}问题及子问题：{n0，n7，n8，n1，n2，……}动态搜索过程：1、隐含生成一个与或图;2、求解一个与或解图北京航空航天大学软件开发环境国家重点实验室Slide5与或图搜索有关概念仅由K=1的外向k-连接符构成的搜索空间:无环与或图：与或图中，如果每一个后继节点不再是该节点的祖先节点，这种与或图称为无环与或图。外向K-连接符：在与或图中，任一节点通过若干个外向k-连接符（k元算子）与其后继节点相连接，其中K=1的外向k-连接符：或连接符；K〉1的外向k-连接符：与连接符。普通有向图由K1的外向k-连接符构成的搜索空间:与或图。北京航空航天大学软件开发环境国家重点实验室Slide6问题求解过程：与或图搜索有关概念首先,自上而下地生成与或图;然后,自下而上地寻找与或解图的搜索过程。北京航空航天大学软件开发环境国家重点实验室Slide7与或图搜索有关概念与或解图及其能解标记与费用计算最佳与或解图的启发式搜索算法–AO*算法AO*算法应用实例基于问题空间的与或图搜索北京航空航天大学软件开发环境国家重点实验室Slide8与或解图及其能解标记与费用计算定义:与或图G中，从任一节点n到叶节点(本原问题)集合N的一个局部解图G’递归定义如下：若n属于N,则此解图G’由单一节点{n}组成；若n有一个指向节点{n1,n2,….,nk}的外向k-连接符（k≥1),而且从每一个ni(i=1,2,….k)到N都有一个解图，则n到N的解图G’由节点n、连接符k以及{n1,n2,….,nk}中每个节点ni到N的解图组成。否则，n到N无解图。北京航空航天大学软件开发环境国家重点实验室Slide9与或解图及其能解标记与费用计算按递归定义自上而下地生成以n为根节点的与或图一般算法：选择n的一个外向k连接符，扩展其后继节点。判断各后继节点是否属于N，若否，则对该k连接符指向的每一个后继节点，选择一个外向k连接符的后继节点继续进行扩展；上述过程周而复始，直到最底层的外向k连接符的每个后继节点均属于N为止。针对任意节点的外向K连接符的选择顺序不同,对应的搜索策略可不同:盲目搜索，启发式搜索。北京航空航天大学软件开发环境国家重点实验室Slide10标记能解节点（Solved)：终叶节点是能解节点；对于非终叶节点：•如果n有多个用k=1的连接符连接的或子节点，iff这些或子节点中至少有一个能解，节点n是能解节点；与或解图及其能解标记与费用计算•如果n有用k1的连接符连接的与子节点。Iff这些与子节点全部能解，节点n是能解节点。定义:北京航空航天大学软件开发环境国家重点实验室Slide11与或解图及其能解标记与费用计算标记不能解节点（Unsolved)没有后裔的非终节点是不能解节点；对于有后裔的非终节点n：•如果n有多个用k=1连接符连接的或子节点，iff所有这些或子节点均不能解，节点n是不能解节点；•如果n有用k1连接符连接的与子节点。Iff这些与子节点中有一节点不能解，节点n是不能解节点。北京航空航天大学软件开发环境国家重点实验室Slide12与或解图及其能解标记与费用计算标记能解节点，求以n为根节点的与或解图：n８n８n８北京航空航天大学软件开发环境国家重点实验室Slide13与或解图及其能解标记与费用计算解图费用定义：设k-连接符的花费C(k)=k,以n为根节点的局部解图的费用C(n,N)可递归计算如下：若n属于N,则C(n,N)=0；若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最佳解图花费计算：C(n，N)=min(C(n，N)i)i=1北京航空航天大学软件开发环境国家重点实验室Slide14与或解图及其能解标记与费用计算求解图的花费：(设每条边为单位花费)n８n８n８北京航空航天大学软件开发环境国家重点实验室Slide15基于问题空间的与或图搜索与或图搜索有关概念与或解图及其能解标记与费用计算最佳与或解图启发式搜索算法–AO*算法AO*算法应用实例北京航空航天大学软件开发环境国家重点实验室Slide16最佳与或图启发式搜索AO*算法概述算法交替执行以下两个阶段的操作：第一阶段：自顶向下地生成局部与或图-选择迄今为止最好的局部解图；对该解图的一个非终叶节点进行扩展，计算该节点各个K-连接符连接的后继节点解图的花费计值；如果可能，标记后继节点为能解节点。第二阶段：自下而上地计算修正与或图花费估计值-确定最小花费连接符；如果必要，修改父节点的花费值；或标记父节点为能解节点;此过程不断进行直到到达局部解图的根节点为止。北京航空航天大学软件开发环境国家重点实验室Slide17AO*算法数据结构：s：初始节点；n：当前节点。G：以s为根节点产生的与或图；G’：当前选择的局部与或解图；h(m)：任意节点m到N的启发式费用估计值；q(n)：目前得到的以节点n为根的解图的最小费用；q0(n)：上一次获得的以节点n为根的解图的最小费用。北京航空航天大学软件开发环境国家重点实验室Slide18AO*算法：选择最有希望的局部解图G’及G’中合适的非叶节点n：G’:=Find(G),n:=Select(G’)扩展节点n，计算{mj}的启发式信息：{mi}:=Expand(n),G’:={mi}∪G’,对所有mj:q(mj):=h(mj)mj到N的估计值;如果mj属于N则Mark(mj，Sovled)。建立以n节点为初始节点的祖先节点集合：A:={n}A=Φ?YesNo北京航空航天大学软件开发环境国家重点实验室Slide19m:=Remove(A)针对m的L个k连接符，求m的最小花费q(m)：qi(m):=C(mi)+q(ni1)+q(ni2)+……+q(nik))1iL;q(m):=minqi(m)（i=1,2,….,L);标记m指向当前花费最小的k连接符。如果m最小花费ki连接符连接的所有节点nij可解,标记节点m可解，即对（j=1,2,….,k)：ijMark(nij,Sovled)-Mark(m,Sovled),Mark(m,Sovled)∨q(m)≠q0(m)将m的父节点ma送集合A:A:=A∪{ma}YesNoAO*算法：北京航空航天大学软件开发环境国家重点实验室Slide20基于问题空间的与或图搜索与或图搜索有关概念与或解图及其能解标记与费用计算最佳与或解图的启发式搜索算法–AO*算法AO*算法应用实例北京航空航天大学软件开发环境国家重点实验室Slide21作业数字重写问题的变换规则如下:6-3,3;6-4,2;4-3,1;4-2,2;3-2,1;2-1,1。问如何用这些规则把数字6变换成一个由若干个1组成的数字串。试用AO*算法进行求解，并给出搜索图。求解时设k=连接符的花费值是k个单位，h函数值规定为：h(1)=0,h(n)=n（n1）。