《与或图搜索-copy北航6系人工智能.ppt》由会员分享，可在线阅读，更多相关《与或图搜索-copy北航6系人工智能.ppt（21页珍藏版）》请在三一办公上搜索。
1、,第二章 问题求解基本原理,搜 索 技 术(二)基 于 问 题 空 间 的 与 或 图 搜 索,基于问题空间的与或图搜索,与或图搜索有关概念,与或解图及其能解标记与费用计算,最佳与或解图的启发式搜索算法 AO*算法,AO*算法应用实例,与或图搜索有关概念,问题描述回顾-（S,S0,F,G)：S：问题和子问题集合,S0：初始问题；F：操作算子集合，用于将初始问题(或子问题)分解成更简单的子问题；G：本原问题集合，其中每一个问题均是不言自明的公理、已知事实等，或是已经证明的定理。,与或图搜索有关概念,分解规则:if n0 then n1（nn）；if n then n n；if n then（nn
2、）；if n then（nn）；if nthen n n；if n then n（nn）；if n then nn；,初始问题:n0;本原（终叶）问题:n,n,问题及子问题：n0，n7，n8，n1，n2，,动态搜索过程：1、隐含生成一个与或图;2、求解一个与或解图,与或图搜索有关概念,仅由 K=1 的外向 k-连接符构成的搜索空间:,无环与或图：与或图中，如果每一个后继节点不再是该节点的祖先节点，这种与或图称为无环与或图。,外向K-连接符：在与或图中，任一节点通过若干个外向 k-连接符（k元算子）与其后继节点相连接，其中K=1 的外向 k-连接符：或连接符；K 1 的外向 k-连接符：与连接符
3、。,普通有向图,由 K 1 的外向 k-连接符构成的搜索空间:,与或图。,问题求解过程：,与或图搜索有关概念,首先,自上而下地生成与或图;然后,自下而上地寻找与或解图的搜索过程。,与或图搜索有关概念,与或解图及其能解标记与费用计算,最佳与或解图的启发式搜索算法 AO*算法,AO*算法应用实例,基于问题空间的与或图搜索,与或解图及其能解标记与费用计算,定义:与或图 G 中，从任一节点 n 到叶节点(本原问题)集合 N 的一个局部解图 G 递归定义如下：若 n 属于 N,则此解图 G 由单一节点n组成；若 n 有一个指向节点n1,n2,.,nk的外向 k-连接符（k 1),而且从每一个 ni(i=
4、1,2,.k)到 N 都有一个解图，则 n 到 N 的解图 G由节点 n、连接符 k 以及n1,n2,.,nk中每个节点 ni 到 N 的解图组成。否则，n 到 N 无解图。,与或解图及其能解标记与费用计算,按递归定义自上而下地生成以n为根节点的与或图一般算法：选择 n 的一个外向k连接符，扩展其后继节点。判断各后继节点是否属于 N，若否，则对该 k 连接符指向的每一个后继节点，选择一个外向k连接符的后继节点继续进行扩展；上述过程周而复始，直到最底层的外向k连接符的每个后继节点均属于 N 为止。,针对任意节点的外向K连接符的选择顺序不同,对应的搜索策略可不同:盲目搜索，启发式搜索。,标记能解节
5、点（Solved)：终叶节点是能解节点；对于非终叶节点：如果 n 有多个用 k=1 的连接符连接的或子节点，iff 这些或子节点中至少有一个能解，节点 n 是能解节点；,与或解图及其能解标记与费用计算,如果 n 有用 k1 的连接符连接的与子节点。Iff 这些与子节点全部能解，节点 n 是能解节点。,定义:,与或解图及其能解标记与费用计算,标记不能解节点（Unsolved),没有后裔的非终节点是不能解节点；,对于有后裔的非终节点n：如果 n 有多个用 k=1 连接符连接的或子节点，iff 所有这些或子节点均不能解，节点 n 是不能解节点；,如果 n 有用 k1 连接符连接的与子节点。Iff 这
6、些与子节点中有一节点不能解，节点 n 是不能解节点。,与或解图及其能解标记与费用计算,标记能解节点，求以n为根节点的与或解图：,n,n,n,与或解图及其能解标记与费用计算,解图费用定义：设 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最佳解图花费计算
7、：C(n，N)=min(C(n，N)i)i=1,与或解图及其能解标记与费用计算,求解图的花费：(设每条边为单位花费),n,n,n,基于问题空间的与或图搜索,与或图搜索有关概念,与或解图及其能解标记与费用计算,最佳与或解图启发式搜索算法 AO*算法,AO*算法应用实例,最佳与或图启发式搜索 AO*算法概述,算法交替执行以下两个阶段的操作：第一阶段：自顶向下地生成局部与或图-选择迄今为止最好的局部解图；对该解图的一个非终叶节点进行扩展，计算该节点各个K-连接符连接的后继节点解图的花费计值；如果可能，标记后继节点为能解节点。,第二阶段：自下而上地计算修正与或图花费估计值-确定最小花费连接符；如果必要
8、，修改父节点的花费值；或标记父节点为能解节点;此过程不断进行直到到达局部解图的根节点为止。,AO*算法数据结构：,s：初始节点；n：当前节点。,G：以 s 为根节点产生的与或图；,G：当前选择的局部与或解图；,h(m)：任意节点 m 到 N 的启发式费用估计值；,q(n)：目前得到的以节点 n 为根的解图的最小费用；,q0(n)：上一次获得的以节点n为根的解图的最小费用。,AO*算法：,AO*算法：,基于问题空间的与或图搜索,与或图搜索有关概念,与或解图及其能解标记与费用计算,最佳与或解图的启发式搜索算法 AO*算法,AO*算法应用实例,作业,数字重写问题的变换规则如下: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）。,
