第4章 与或图搜索

• 在与或图上执行搜索的过程，其目的在于表明起始节点 在与或图上执行搜索的过程， 是有解的，也就是说，搜索不是去寻找目标节点， 是有解的，也就是说，搜索不是去寻找目标节点，而是 寻找一个解图。 寻找一个解图。 • 一个节点被称为是能解节点(SOLVED)，其递归定义为： 一个节点被称为是能解节点(SOLVED)，其递归定义为： 能解节点(SOLVED) –1．终节点是能解节点（直接与本原问题相关联）； 1 终节点是能解节点（直接与本原问题相关联）； –2．若非终节点，且有“或”子节点时，当且仅当其 2 若非终节点，且有“ 子节点时， 子节点至少有一个能解 ，该非终节点才能解； 该非终节点才能解； –3．若非终节点，且有“与”子节点时，当且仅当其 3 若非终节点，且有“ 子节点时， 子节点均能解，该非终节点才能解。 子节点均能解，该非终节点才能解。
4.4 AO*算法
假设： 假设： • 估价函数q(n)、启发函数h(n)； 估价函数q(n)、启发函数h(n)； q(n) h(n) • G为当前扩展生成的与或图； 为当前扩展生成的与或图； • G′为一侯选局部解图，是G的一个子图； 为一侯选局部解图， 的一个子图； • h(n)是节点n的启发函数； h(n)是节点n的启发函数； 是节点 • q(n)是节点n的估价函数，是从节点n到一组叶节 q(n)是节点n的估价函数，是从节点n 是节点 点的一个最优解图的代价估计,初始值为h(n) h(n)； 点的一个最优解图的代价估计,初始值为h(n)；
• 一个节点被称为是不能解节点(UNSOLVED)，其递 一个节点被称为是不能解节点(UNSOLVED)， 不能解节点(UNSOLVED) 归定义为: 归定义为: –1．没有后裔的非终节点是不能解的节点； 1 没有后裔的非终节点是不能解的节点； –2．若非终节点，且有“或”子节点时，当且仅 2 若非终节点，且有“ 子节点时， 当所有子节点均不能解时，该非终节点不能解； 当所有子节点均不能解时，该非终节点不能解； –3．若非终节点，且有“与”子节点时，当至少 3 若非终节点，且有“ 子节点时， 有一子节点不能解时，该非终节点不能解。 有一子节点不能解时，该非终节点不能解。
建立含n的单一节点集合S. 7 、S:=(n); 建立含n的单一节点集合S. S为空 为空, 8、 Until S为空, do: 9、 11 、 指向节点集(n 的每一个连接符i • 对m指向节点集(n1i，n2i,…nki) 的每一个连接符i分别计算 n qi(m)=Ci+q(n1i)+…+q(nki),修改m的耗散值q(m)，q(m):= min )+ +q(n ),修改m的耗散值q(m)， 修改 q(m) (m)。 qi(m)。 加指针到min (m)的连接符上 或把指针修改到min (m)的连 的连接符上, • 加指针到min qi(m)的连接符上,或把指针修改到min qi(m)的连 接符上。 接符上。 SOLVED)；//若该连接符的所有子节 • IF M(nji, SOLVED) THEN M(m, SOLVED)；//若该连接符的所有子节
• 解图是包含某节点n到终节点集合N的、连通的能 解图是包含某节点n 终节点集合N 解节点的子图，其定义如下： 解节点的子图，其定义如下： • 一个与或图G中，从节点 n 到终节点集合N的解 一个与或图G 到终节点集合N 的子图。 图记为 G′， G′是G的子图。
–若 n 是 N 的一个元素，则 G′由单个节点n组成； 若 的一个元素， 由单个节点n组成； –若 n 有一个指向节点集{n1…,nk}的外向连接符 K， 若 有一个指向节点集{n ,n 并且每一个节点n (i=1,…,k) ,k)， 并且每一个节点ni到N都有一个解图 (i=1, ,k)，则 连接符K G′由节点 n，连接符K，以及 {n1 ,…,nk}中的每一个 ,n 节点到N的解图组成； 节点到N的解图组成； –否则 n 到 N 不存在解图。 否则 不存在解图。
P
。
R
Q
4.2 与或图
• 与节点：一个归约算子把单个问题变为几个子问题组 与节点： 成的集合，只有当所有子问题都有解， 成的集合，只有当所有子问题都有解，该父辈节点才 有解。这种关系称为“ 关系， 有解。这种关系称为“与”关系，对应节点称为与节 点。 • 与节点由与运算连接，如下图中Q和R，并用一条弧线 与节点由与运算连接，如下图中Q 将相关的边连接起来，弧线及所相关的边被称为超弧。 将相关的边连接起来，弧线及所相关的边被称为超弧。 • 超弧包含的边数（K）被称为该超弧的度，度为K的超 超弧包含的边数（ 被称为该超弧的度，度为K 弧也称为K-连接符。
点都是能解的, 点都是能解的,则m也能解
begin
10、 (S)，REMOVE(m,S)；//子节点不在集合 的节点m 子节点不在集合S 10、当mc∉(S)，REMOVE(m,S)；//子节点不在集合S的节点m
S)； 12 、IF M(m, SOLVED) ∨ (q(m) ≠ q0(m)) THEN ADD(ma, S)；//m
• 与或图包含超弧，因此也称为超图。 与或图包含超弧，因此也称为超图。 超图
P
R
Q
• 问题归约描述对应的与或图中
–原始问题描述对应于起始节点（或根节点）， 原始问题描述对应于起始节点（或根节点）， 原始问题描述对应于起始节点 –本原问题所对应的节点叫做叶节点。 本原问题所对应的节点叫做叶节点。 本原问题所对应的节点叫做叶节点 –在某些特殊情况下，不出现任何与节点（所有 在某些特殊情况下，不出现任何与节点（ 在某些特殊情况下 超弧度都为1），此时的图是普通图，问题归 约描述即是状态空间描述。 约描述即是状态空间描述。
能解或修正的耗散值与原先估算q 不同,则把m的所有先辈节点m 添加到S 能解或修正的耗散值与原先估算q0不同,则把m的所有先辈节点ma,添加到S中
13、 (与 匹配) 13、end (与9匹配) 14、 (与 匹配) 14、end (与3匹配) • AO*搜索算法可以理解为两个主要过程的重复。 搜索算法可以理解为两个主要过程的重复。
• 具有最小耗散值的解图称为最佳解图，其值用 具有最小耗散值的解图称为最佳解图， (n)标记 待求解问题的解图的值为h (s)。 标记。 h*(n)标记。待求解问题的解图的值为h*(s)。
• 解图的求法是：从节点n开始，正确选 解图的求法是：从节点n开始， 择一个外向连接符， 择一个外向连接符，如此进行下去直 到由此产生集合N中的所有元素为止。 到由此产生集合N中的所有元素为止。 • 图4-3给出了n0→{n7，n8}的三个解图 给出了n 耗散值分别为8 （耗散值分别为8，7，5）。
kkkk-
–4-6步：自上而下的图生长过程。 4 自上而下的图生长过程。
• 先通过有标记的连接符，找到目前为止最好的一个局部解 先通过有标记的连接符， 然后对其中一个非终节点进行扩展， 图，然后对其中一个非终节点进行扩展，并对其后继节点 估计耗散值和加能解标记。 估计耗散值和加能解标记。
–7-12步：自下而上的估价函数值的修正、指针的标 7 12步 自下而上的估价函数值的修正、 记和SOLVED的标注过程。 SOLVED的标注过程 记和SOLVED的标注过程。
• 归约法的问题表示由下列三部分组成： 归约法的问题表示由下列三部分组成： –1）一个初始问题的描述； 1 一个初始问题的描述； –2）一组把问题变成子问题的算子； 2 一组把问题变成子问题的算子； –3） 一组本原问题的描述 3 • 同一问题产生的若干子问题之间的关系是 同时的” 可以用“与或图” “同时的”，可以用“与或图”表示问题 归约的状态空间。 归约的状态空间。
第四章 与或图搜索
• 4.1 问题归约法 • 4.2 与或图 • 4.3 与或图搜索 • 4.4 AO*算法 • 4.5 博弈树的搜索
4.1 问题归约法
• 当问题复杂时，可把初始问题分解成若干简单 当问题复杂时， 的子问题，若子问题仍复杂，可再进一步分解， 的子问题，若子问题仍复杂，可再进一步分解， 直到这些子问题的解可直接得到。 直到这些子问题的解可直接得到。这种问题的 描述和求解方法，称为问题归约法。 描述和求解方法，称为问题归约法。 • 可直接解答的问题称为本原问题，是不必证明 可直接解答的问题称为本原问题， 自然成立的。 的、自然成立的。
• 如果n=s为初始节点，则此解图是所求解问题的 如果n=s为初始节点， n=s为初始节点 解图。 解图。
• 与或图中耗散值的计算。 与或图中耗散值的计算。
–设连接符的耗散值规定为，k-连接符耗散值=k，则 设连接符的耗散值规定为， 连接符耗散值=k， 设连接符的耗散值规定为 =k 解图耗散值k(n, N)可递归计算如下 可递归计算如下： 解图耗散值k(n, N)可递归计算如下：
4.2 与或图
• 或节点：几个算子适用于同一个问题，从而产 或节点：几个算子适用于同一个问题， 生不同的后继问题集合。 生不同的后继问题集合。这时只要有一个后继 问题有解，该父辈问题有解，此时关系是“ 问题有解，该父辈问题有解，此时关系是“或” 关系，对应节点称为或节点。 关系，对应节点称为或节点。 • 或节点由或运算连接，如下图中的Q和R 或节点由或运算连接，如下图中的Q
• 若n是N的一个元素，则k(n, N)=0； 的一个元素， N)=0； • 若n有一个外向连接符指向后继节点集合{n1…,ni}，并设 有一个外向连接符指向后继节点集合{n ,n 该连接符的耗散值为C N)+…+k(n N)。 该连接符的耗散值为Cn，则k(n, N)=Cn+k(n1, N)+ +k(ni, N)。
THEN
s已标记为 已标记为SOLVED, 2、 Until s已标记为SOLVED, do: :=FIND(G)。//根据连接符标记 指针）找出（选择） 根据连接符标记（ 4、 G′ :=FIND(G)。//根据连接符标记（指针）找出（选择）一个待扩展的 n:=G′中的任一非终节点 一非终节点。 5、 n:=G′中的任一非终节点。 EXPAND(n),生成子节点集 生成子节点集{n 6、 EXPAND(n),生成子节点集{ni}， },G),计算 计算q(n IF ni∉G，G:=ADD({ni},G),计算q(ni)=h(ni)， ,SOLVED)。 IF GOAL(ni) THEN M(ni,SOLVED)。