小结:
• 问题归约法: 当问题复杂时，可把初始问题分解成若 干简单的子问题，若子问题仍复杂，可再进一步分解 ，直到这些子问题的解可直接得到。这种问题的描述 和求解方法，称为~.
• 本原问题: 可直接解答的问题称为~ ，它是不必证明 的、自然成立的.
• 归约法的组成：
1）一个初始问题的描述；
2）一组把问题变成子问题的算子 (分解或转换)；
• 定义：不能解节点的递归定义为:
1．没有后裔的非终节点是不能解的节点；
2．若非终节点有 “或” 子节点时，当且仅 当所有子节点均不能解时，该非终节点才不 能解；
3．若非终节点有 “与” 子节点时，当至少 有一子节点不能解时，该非终节点才不能解 .
解图的定义：
• 是由能解节点构成的一个子图，是包含一节点（n） 到目的(终)节点集合（N）的、连通的能解节点的子 图.
• 结果不同：若初始节点被标示为可解，则 搜索成功结束；若初始节点被标示为不可 解，则搜索失败.
• 节点处理不同：一旦发现不可解节点，应 把该节点从图中删去.
4 与或图启发式搜索算法 AO*
• 假设：G；G；h(n)是从节点 n 到一组终叶节点的 一个最优解图的一个代价估计，评价函数 q(n)=h(n)
3 与或图搜索
• 含义：在与或图上执行搜索的过程，其目的在于标明 起始节点是有解的，即，搜索不是去寻找到目标节点 的一条路径，而是寻找一个解图。
• 定义：一个节点被称为能解节点，其递归定义为： 1．终节点是能解节点（直接与本原问题相关联）； 2．若非终节点 有 “或” 子节点时，当且仅当其子 节点至少有一个能解 ，该非终节点才能解； 3．若非终节点有 “与” 子节点时，当且仅当其子 节点均能解，该非终节点才能解。
G:= ADD({ni},G),计算 q(ni)=h(ni)，IF GOAL(ni) THEN M(n , SOLVED);
n1 17 n3 6
2
n26 2
n7 0
n0 18
2n5 2
0 n8
n07
n0 7
2 n4
2 n5 1 3 2 0 n8
解图的求法
n7
0 n7
n0
n2
n4
n5
n8
n0 5
2
Байду номын сангаасn4 1
2 n5
2
1
n80
与或图搜索与状态空间图搜索的区别：
• 搜索目的不同：是证明起始节点是否可解 ，而可解节点是递归定义的，取决于后继 节点是否可解，即搜索过程是能否找到可 解的叶节点.
3） 一组本原问题的描述
• 不同的算子对应不同的关系,从而使问题归约的描述 可用一个与或图的结构来表示.
2 与或图
• 与节点：把单个问题分解为几个子问题来求解。只 有当所有子问题都有解，该父辈节点才有解。表示 一种 “与” 关系。
• 或节点：同一问题被转换为几种不同的后继问题。 只要有一个后继问题有解，则原问题有解。表示一 种 “或” 关系。
• 在一个与或图 G 中，从节点 n 到节点集 N 的解图 记为 G， G 是 G 的子图. 1．若 n 是N的一个元素，则G由单个节点n组成； 2．若 n 有一个指向节点集 {n1…,nk} 的外向连接 符 K，使得从每一个节点 ni (i=1,…,k) 到 N 有 一个解图 ，则 G由节点 n，连接符 K，以及 {n1 ,…,nk}中的每一个节点到 N 的解图所组成； 3．否则 n 到 N 不存在解图.
• 如果 n=s 为初始节点，则解图为所求解问题的解图 .
解图耗散值的计算：
• 若解图的耗散值记为 k(n, N)，则可递归计 算如下：
–若 n 是 N 的一个元素，则 k(n, N)=0； –若 n 有一个外向连接符指向其后继节点集合
{n1…,ni}，并设该连接符的耗散值为 Cn（一般 k-连接符的耗散值=k ），则
第四章 与或图搜索
1 问题归约法 2 与或图 3 与或图搜索 4 AO*算法 5 博弈树的搜索
1 问题归约法
• 问题: 在边长为 2 的正方形内，任意放置 5 个 点，求证其中必存在两个点，它们之间的距离不 大于2。
• 问题可转化为：在四个单位正方形内，任意放置5 个点，至少有两个点在同一正方形内。
AO*过程:
1.建立初始搜索图，G:=s，计算 q(s)=h(s)，IF GOAL(s) THEN M(s,SOLVED)；
2. Until s 已标记为 SOLVED, do:
3. Begin 4. G := FIND(G)；根据连接符标记（指针）找出一
个待扩展的侯选局部解图G（连接符在11步标记） 5. n := G 中的任一非终节点; 选一个当前节点 6. EXPAND(n),生成子节点集{ni}，如果 ni G，
• K—连接符：从一个父节点指向一组含有 K个后继节点的节点集.
n1 n3
n0
n2 n5
• 在与或图中，节 点 n0 有两个连接
n4 符：1-连接符指 向节点 n1；2-连 接符指向节点集
合{n4、n5}；
n6
• 对于节点 n0 来讲
n8 ，n1 可称为或节
点，n4、n5 可称
n7
为与节点。
与或图
• 问题: 假定我们已经会求矩形的面积，现在要求 如图所示的五边形的面积。
• 方法分析: 五边形的面积转化为矩形面积。
①I 1
III ③ 23 II
②
求解步骤：
求五边形面积
①I 1
III ③
3 2 II
求 1面积 求 2面积 求 3面积
②
求 I面积 求 ①面积
求 II面积 求 III面积 求 ②面积 求 ③面积
P
P
Q
Q
R
R
(a)
(b)
• 与节点由与运算连接（超弧），如图（a）.
• 或节点由或运算连接，如图（b）.
• 定义：与或图就是包含与节点和或节点 的图，即存在超弧的图，也称为超图.
• 超图与状态空间图有什么区别？ 与或图是一种更一般的图.
• 定义：一超弧所相关的边数（K）被称为 该超弧的度，实现的连接称为K-连接.
k(n, N)= Cn+ k(n1, N)+…+ k(ni, N)
• 具有最小耗散值的解图称为最佳解图，其值 也用 h*(n) 标记。
• 例：从节点 n 开始，正确选择一个外
向连接符，一直进行下去直到产生的
n1
每一个后继节点成为集合N中的一个元 n3
素为止。下图给出了 n0 →{n7，n8}的 三个解图（耗散值分别为 8，7，5）. n6