人工智4与或图搜索copy

1、北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 slide 1第二章第二章 问题求解基本原理问题求解基本原理搜搜 索索 技技 术术 (二二) 基基 于于 问问 题题 空空 间间 的的 与与 或或 图图 搜搜 索索北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 slide 2基于基于问题空间问题空间的与的与或图搜索或图搜索n与或图搜索与或图搜索有关概念有关概念 与或解图与或解图及其及其能解标记能解标记与与费用计算费用计算 最佳与或解图的启发式搜索算法最佳与或解图的启发式搜索算法 ao*算法算法 ao*算法算法应用实例应用

2、实例北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 slide 3与或图搜索与或图搜索有关概念有关概念n 问题描述问题描述回顾回顾 - - （s, ss, s0 0, f, g ), f, g )： w s s：问题和子问题集合：问题和子问题集合, s, s0 0：初始问题；：初始问题；w f f：操作算子集合，用于将初始问题：操作算子集合，用于将初始问题( (或子问题或子问题) )分解分解成更成更简单的子问题；简单的子问题；w g g：本原问题集合，其中每一个问题均是不言自明的公理：本原问题集合，其中每一个问题均是不言自明的公理、已知事实等，或是已经证明

3、的定理。、已知事实等，或是已经证明的定理。北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 slide 4与或图搜索与或图搜索有关概念有关概念分解规则分解规则: : if n if n0 0 then nthen n1 1 （n nn n）；）； if nif n then nthen n n n； if nif n thenthen（n nn n）；）； if nif n thenthen（n nn n）；）； if nif nthen nthen n n n； if nif n then nthen n （n nn n）；）； if nif n then

4、 nthen nn n；n2nn初始问题初始问题: : n n0 0 ; ;本原（终叶）问题本原（终叶）问题: : n n, , n n 问题及子问题：问题及子问题： n n0 0， n n7 7，n n8 8， n1，n2， 动态搜索动态搜索过程：过程：1 1、隐含生成隐含生成一个与或图一个与或图; ;2 2、求解一个、求解一个与或解图与或解图北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 slide 5与或图搜索与或图搜索有关概念有关概念n仅由仅由 k = 1 k = 1 的外向的外向 k-k-连接符构成的搜索空间连接符构成的搜索空间: : 无环与或图

5、无环与或图：与与或图中，如果每一个后继节点不再是该节或图中，如果每一个后继节点不再是该节点的祖先节点，这种与或图称为点的祖先节点，这种与或图称为无环与或图无环与或图。 外向外向k-k-连接符连接符：在与或图中，任一节点通过在与或图中，任一节点通过若干个若干个外向外向 k-k-连连接符（接符（k k元算子）与其后继节点相连接，其中元算子）与其后继节点相连接，其中k = 1 k = 1 的外向的外向 k-k-连接符：连接符：或或连接符；连接符；k k 1 1 的外向的外向 k-k-连接符：连接符：与与连接符。连接符。 普通有向图普通有向图由由 k k 1 1 的外向的外向 k-k-连接符构成的搜索

6、空间连接符构成的搜索空间: :与或图与或图。北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 slide 6 问题求解过程问题求解过程 ：与或图搜索有关概念与或图搜索有关概念 首先首先, 自上而下地自上而下地或图或图; 然后然后, 自下而上地自下而上地与或解图与或解图的的搜索搜索过程。过程。北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 slide 7n与或图搜索与或图搜索有关概念有关概念 与或解图与或解图及其及其能解标记能解标记与与费用计算费用计算 最佳与或解图的启发式搜索算法最佳与或解图的启发式搜索算法 ao*算法算

7、法 ao*算法算法应用实例应用实例基于问题空间的基于问题空间的与或图搜索与或图搜索北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 slide 8与或解图与或解图及其能解标记与费用计算及其能解标记与费用计算n定义定义: :与或图与或图 g g 中，从任一节点中，从任一节点 n n 到叶节点到叶节点( (本原问题本原问题) )集合集合 n n 的一的一个局部解图个局部解图 g g 递归定义递归定义如下：如下：v 若若 n n 属于属于 n,n,则此解图则此解图 g g 由单一节点由单一节点nn组成；组成；v 若若 n n 有一个指向节点有一个指向节点nn1 1

8、,n,n2 2, ,.,n.,nk k 的的外向外向 k-k-连接符（连接符（k k 1), 1), 而且从每一个而且从每一个 n ni i(i(i=1,2,=1,2,.k) .k) 到到 n n 都有一个解图都有一个解图，则，则 n n 到到 n n 的解图的解图 gg由节点由节点 n n、连接符、连接符 k k 以及以及nn1 1,n,n2 2, ,.,n.,nk k 中每个节点中每个节点 n ni i 到到 n n 的解图组成。的解图组成。v 否则，否则，n n 到到 n n 无解图。无解图。北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 slide

9、 9与或解图及其能解标记与费用计算与或解图及其能解标记与费用计算按按递归定义递归定义自上而下地自上而下地生成生成以以n为根节点的与或图一般算法：为根节点的与或图一般算法：w 选择选择 n n 的一个外向的一个外向k k连接符，连接符，扩展扩展其后继节点。其后继节点。w 判断各后继节点是否属于判断各后继节点是否属于 n n，w 若否，则对该若否，则对该 k k 连接符指向的每一个后继节点，选择一个连接符指向的每一个后继节点，选择一个外向外向k k连接符的后继节点继续进行扩展；连接符的后继节点继续进行扩展；w 上述过程周而复始，直到上述过程周而复始，直到最底层的最底层的外向外向k k连接符的每个后

10、继连接符的每个后继节点均属于节点均属于 n n 为止。为止。针对任意节点的针对任意节点的外向外向k连接符连接符的的选择选择顺序不同顺序不同, 对应的搜索策略可不同对应的搜索策略可不同: 盲目搜索，启发式搜索。盲目搜索，启发式搜索。北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 slide 10n标记标记能解节点能解节点（solved)：w 终叶节点是能解节点；终叶节点是能解节点；w 对于非终叶节点：对于非终叶节点： 如果如果 n n 有多个用有多个用 k=1 k=1 的连接符连接的的连接符连接的或子节点或子节点，iffiff 这这些或子节点中至少有一个能解

11、，节点些或子节点中至少有一个能解，节点 n n 是能解节点；是能解节点；与或解图及其与或解图及其能解标记能解标记与费用计算与费用计算 如果如果 n n 有用有用 k1 k1 的连接符连接的的连接符连接的与子节点与子节点。iffiff 这些与这些与子节点全部能解，节点子节点全部能解，节点 n n 是能解节点。是能解节点。定义定义:北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 slide 11与或解图及其与或解图及其能解标记能解标记与费用计算与费用计算n标记标记不能解节点不能解节点（unsolved) 没有后裔的非终节点是不能解节点没有后裔的非终节点是不能解

12、节点；w 对于有后裔的非终节点对于有后裔的非终节点n n： 如果如果 n n 有多个用有多个用 k=1 k=1 连接符连接的连接符连接的或子节点或子节点，iffiff 所有所有这些或子节点均不能解，节点这些或子节点均不能解，节点 n n 是不能解节点；是不能解节点； 如果如果 n n 有用有用 k1 k1 连接符连接的连接符连接的与子节点与子节点。iffiff 这些与这些与子节点中有一节点不能解，节点子节点中有一节点不能解，节点 n n 是不能解节点。是不能解节点。北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 slide 12与或解图及其与或解图及其能解

13、标记能解标记与费用计算与费用计算 标记标记能解节点能解节点，求以，求以n为根为根节点的与或解图：节点的与或解图：nnn北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 slide 13与或解图及其能解标记与与或解图及其能解标记与费用计算费用计算n解图费用解图费用定义：定义：设设 k-k-连接符的花费连接符的花费 c(k)= k, c(k)= k, 以以 n n 为根节点为根节点的局部解图的费用的局部解图的费用 c(n,nc(n,n) ) 可可递归计算递归计算如下：如下：w 若若 n n 属于属于 n, n, 则则 c(n,n) = 0c(n,n) = 0；w

14、 若若 n n 有有 m m 个个外向外向 k-k-连接符（连接符（k k 1) 1) 。设其中第。设其中第 i i 个外向个外向 k-k-连接符的费用为连接符的费用为 c cnini，其连接的后继节点，其连接的后继节点为为nni i1 1,n,ni i2 2, ,.,n.,ni ik k ，则节，则节点点 n n 通过此连接符到通过此连接符到 n n 的一个解图的费用为：的一个解图的费用为： c(nc(n，n)n)i i = c = cn ni i + c(n+ c(ni i1 1，n) + n) + . + c(n. + c(ni ik k，n)n) m最佳解图花费最佳解图花费计算：计算：

15、 c(nc(n，n) = min ( c(nn) = min ( c(n，n)n)i i ) ) i = 1i = 1 北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 slide 14与或解图及其能解标记与与或解图及其能解标记与费用计算费用计算 求解图的花费：求解图的花费：(设每条边为设每条边为单位花费单位花费)nnn北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 slide 15基于问题空间的与基于问题空间的与或图搜索或图搜索n与或图搜索与或图搜索有关概念有关概念与或解图与或解图及其及其能解标记能解标记与与费用计算费

16、用计算 最佳与或解图启发式搜索算法最佳与或解图启发式搜索算法 ao*算法算法 ao*算法算法应用实例应用实例北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 slide 16最佳与或图启发式搜索最佳与或图启发式搜索 aoao* * 算法概述算法概述n算法交替执行交替执行以下两个阶段的操作：w 第一阶段：自顶向下自顶向下地生成生成局部与或图 - 选择选择迄今为止最好的局部解图；对该解图的一个非终叶节点进行扩展扩展，计算该节点各个k-连接符连接的后继节点解图的花费计值；如果可能，标记后继节点为能解节点。w 第二阶段：自下而上自下而上地计算修正计算修正与或图花费估

17、计值 - - 确定确定最小花费连接符；如果必要，修改修改父节点的花费值；或标记标记父节点为能解节点;此过程不断进行直到到达局部解图的根节点为止。北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 slide 17ao*算法数据结构算法数据结构： s： 初始节点；初始节点；n：当前节点。当前节点。 g： 以以 s 为根节点产生的与或图；为根节点产生的与或图；g： 当前选择的局部与或解图当前选择的局部与或解图 ；h(m)： 任意节点节点 m 到到 n 的启发式费用估计值；的启发式费用估计值；q (n)：目前得到的以节点目前得到的以节点 n 为根的解图的最小费用；为

18、根的解图的最小费用；q0 (n)：上一次获得的以节点上一次获得的以节点n为根的解图的最小费用。为根的解图的最小费用。北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 slide 18ao* 算法：算法：选择选择最有希望的局部解图最有希望的局部解图g 及及g 中合适的非叶节点中合适的非叶节点n：g:= find ( g ), n := select ( g)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北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 slide 19 m:= remove ( a )针对针对m 的的l个个 k 连接符，求连接符，求 m 的最小