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

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