人工智能 吉林大学珠海学院计算机科学与技术系 2.1 与或图 (AND/OR Graph) 的搜索 为严格描述 AND/OR 图，我们先推广弧的概念。在 有向图中的弧是从一个父亲节点指向它的儿子节 点的。 在 AND/OR 图中使用的弧叫做超弧，一个 超弧可以把一个父亲节点和 k 个儿子节点同时连接.

Presentation on theme: "人工智能 吉林大学珠海学院计算机科学与技术系 2.1 与或图 (AND/OR Graph) 的搜索 为严格描述 AND/OR 图，我们先推广弧的概念。在 有向图中的弧是从一个父亲节点指向它的儿子节 点的。 在 AND/OR 图中使用的弧叫做超弧，一个 超弧可以把一个父亲节点和 k 个儿子节点同时连接."— Presentation transcript:

1 人工智能 吉林大学珠海学院计算机科学与技术系 2.1 与或图 (AND/OR Graph) 的搜索 为严格描述 AND/OR 图，我们先推广弧的概念。在 有向图中的弧是从一个父亲节点指向它的儿子节 点的。 在 AND/OR 图中使用的弧叫做超弧，一个 超弧可以把一个父亲节点和 k 个儿子节点同时连接 起来，这样的弧也叫做 k 连弧，在 AND/OR 图中， k 连弧用弧线连接起来。当 k=1 时， k 连弧退化成 通常的有向图中的弧。

2 人工智能 吉林大学珠海学院计算机科学与技术系 k 连弧 一般的弧

3 人工智能 吉林大学珠海学院计算机科学与技术系 n7 n6 n3 n0 n1 n4 n2 n5 n8 与或图

4 人工智能 吉林大学珠海学院计算机科学与技术系 n5n5 n1n1 n3n3 n6n6 n7n7 n8n8 n5n5 n0n0 n7n7 n8n8 n4n4 n0n0 三个解图 n5n5 n7n7 n8n8 n4n4 n0n0

5 人工智能 吉林大学珠海学院计算机科学与技术系 在定义中假定 AND/OR 图不含回路，即是说， 图中不存在 一个节点的后裔也是这个节点的祖先的情形。 不含回路保 证了节点间具有部分序关系， 从而保证了下面定义的合理 性。 设 N 是 AND/OR 图 G 的目标节点集合， 从图中任意一个节 点 n 出发到 N 的一个解图是 AND/OR 图 G 的一个子图， 用 G’ 表示， 递归定义如下： 如果 n 是 N 中的一个节点， 则 G’ 只包括 n. 如果 n 有一条从 n 出发的 k 连弧 ai, 这个 k 连弧连接的儿子节 点是 {n1, n2,..., nk}, 则解图 G’ 由节点 n, k 连弧 ai, 和由 n1, n2,..., nk 出发的解图构成。 否则， G 没有从 n 出发到 N 的解图。

6 人工智能 吉林大学珠海学院计算机科学与技术系 与或图 设从节点 n 到目标节点集合 N 的费用用 c(n, N) 表示， 则 c(n, N) 定义如下： 如果 n 是 N 中的一个节点， 则 c(n, N)=0 ， 如果 n 有一条从 n 出发的 k 连弧 ai, 这个 k 连弧连接的儿子节点 是 {n1, n2,..., nk}, 则解图 G’ 由节点 n, k 连弧 ai, 和由 n1, n2,..., nk 出发的解图构成。这时，解图 G’ 的费用定义为 c(n, N)= c(ai)+ c(n, n1)+…+ c(n, nk), 其中 c(ai) 是 k 连弧 ai 的 费用. 否则， G 没有从 n 出发到 N 的解图。设其费用为无穷大 ∞. 。 例如，如果假定 k 连弧的费用是 k, 则图 3.4 所示的 AND/OR 图的两个解图中，左图的费用是 8 ， 右图的费用是 7 。

7 人工智能 吉林大学珠海学院计算机科学与技术系 2.2 与或图的启发式搜索 AND/OR 图的启发搜索过程 AO* 1. 建立一个只由根节点 s 构成的搜索图 G, 设从 s 出发的解图的 费用为 q(s)=h(s), 如果 s 是目标节点， 用 SOLVED 标记 s. 2. until s 被标上 SOLVED, do: 3. begin 4. 通过跟踪从 s 出发的有标记的超弧计算候选解图 G’( 这些 标记在后 面的步骤 11 中给出 ) 5. 在 G’ 中选一个不是目标节点的叶节点 n, 6. 扩展节点 n, 产生节点 n 的所有儿子 {n1, n2,..., nk}, 并把这 些儿子连到图 G 上, 对于每一个不曾在 G 中出现的儿子 nj, 设 q(nj)=h(nj), 如果这些儿子节点中的某些节点是目标节点, 则 把这些节点标记为 SOLVED.

8 人工智能 吉林大学珠海学院计算机科学与技术系 7. 建立一个由 n 构成的单元素集合 S. 8. 直到 S 变空, do: 9. begin 10. 从 S 中删除其儿子节点不在 S 中的节点, 记此节点为 m. 11. 按以下步骤修改 m 的费用 q(m), 对于每一个从 m 出发的 指向节点集合 {ni1, ni2,..., nik} 超弧 ai ，计算 qi(m)= c(ai)+ q(ni1)+…+ q(nik), 这里的 q( nij) 或者是在本循环内部的前面步骤计算出的值，或 者是在步骤 6 中指定的值。 设 q(m) 是所有 qi(m) 的最小者， 标记实现 这个最小值的超弧，如果本次标记与以前的标记不同， 擦去以前的 标记， 如果这些超弧指向的所有儿子节点都标记了 SOLVED, 则把 m 也标上 SOLVED. 12. 如果 m 标记了 SOLVED 或者 m 修改后的费用与以前的费用不同， 则把 m 通过标记的超弧连接的父亲节点加入到 S 中， 13 end 14. end

9 人工智能 吉林大学珠海学院计算机科学与技术系 算法分为两个阶段 1. 4-6 步. 自顶向下的产生候补解图, 并扩展候补 解图的过程. 2. 7-12, 自底向上修正费用值, 标记弧及的过程. 例 H(n0)=3, H(n1)=2, H(n2)=4, H(n3)=4, H(n4)=1, H(n5)=1, H(n6)=2, H(n7)=0, H(n8)=0,

10 人工智能 吉林大学珠海学院计算机科学与技术系 n1 n5 n4 1 2 1 5, n0 n1 n5 n4 5 1 n2,4 n7,0 3, n0 4 n8,0 n6,2 5, n0 n1 n5 n4 5 1 n2,4 n7,0 n8,0 n6,2 n3, 4 22 一次循环后 二次循环后 三次循环后 四次循环后 图 3.5 AO* 搜索算法的例子 n1 n5 n4 1 2 1 3, n0 n3 4 n2 4

11 人工智能 吉林大学珠海学院计算机科学与技术系 5, n0 n5 n4 1 n7,0 n8,0 2 搜索得到的解图

12 人工智能 吉林大学珠海学院计算机科学与技术系 2.3 博弈树的搜索 穷尽的极大极小过程。 两个游戏者分别为 MAX 和 MIN, MAX 想取得高的分数， 而 MIN 想取得低的分数，把整个棋的状态以及所有可能的移动都 用一个有与或图表示出来， 对于某一游戏者求出他的解图， 就是为游戏者制定的赢的策略。 Nim 游戏，桌子上有 7 枚硬币， 由 MAX 和 MIN 两个人分别 把一堆硬币分成不相等的两堆，谁不能继续做下去，谁就算 输， 为 MAX 制定一个赢的策略。 知识表示， 二元组《 s, p 》, 其中 s 为一集合， 表示桌面上各 堆的硬币数， p 表示对当前状态应该移动的游戏者。例如 （ 2 ， 3 ， 2 ， MAX ） 表示现在桌面上有 3 堆硬币， 分别为 2 ， 3 ， 2 个， 此时应抡 到 MAX 移动。

13 人工智能 吉林大学珠海学院计算机科学与技术系 1

14 人工智能 吉林大学珠海学院计算机科学与技术系 固定深度的极大极小过程。 实际的游戏的状态空间是非常大的， 例如国际象棋有 10 120 个状态， 要想把所有状态都列出来， 实际上是做不 到的， 改进的处理方法是在当前状态下把游戏扩展到某 一固定的深度， 对这个深度的树的叶节点进行状态估值， 然后分别逐层地以取极大和取极小的方式上传， 最终给 出对游戏者移动的最佳建议 例； 九宫游戏 估值函数： MAX 所能占据的行， 列和对角线数 - MAX 所能占据的行， 列和对角线数 如果 MAX 赢， 为无穷大 如果 MIN 赢， 为 0 5-4=1

15 人工智能 吉林大学珠海学院计算机科学与技术系 两步棋的例子 S JIHGFED A BC MAX 取极大 值 MIM 取极小 值 MAX (-2) (0) (-6) (9) (-4)(-3) (-4) (-2) (-6) MAX 的移动

16 人工智能 吉林大学珠海学院计算机科学与技术系 过程 MINMAX: 算法分为两个阶段, 第一阶段用宽度优先产生给定深 度内的所有节点, 然后对所有叶节点进行状态估值. 第二阶 段自低向上倒推估计值, 一层取极小, 一层去极大. 直至求 出初始节点的估值.

17 人工智能 吉林大学珠海学院计算机科学与技术系 MIN MAX 6-5=1, 5-5=0, 4-5=-1 5-6=-1, 5-5=0, 5-6=-1, 6-6=0, 4-6=-2 5-4=1 6-4=2

18 人工智能 吉林大学珠海学院计算机科学与技术系

19 人工智能 吉林大学珠海学院计算机科学与技术系 Alpha-beta 过程 在固定深度的极大极小过程中， 对于一个给定的节点， 需要先扩展到给定的深度， 然后对叶节点进行估值，在 一层一层地向上返回值， 决定最佳移动。 为提高效率， 我们可以按深度优先方式， 从左边开始， 先对最左分支 扩展到给定深度， 定出极大和极小的取值界限，即 alpha 值和 beta 值， 然后一边扩展一边估值， 并把估值同 alpha 值和 beta 值相比较，这样就可以省掉许多节点的估 值， 当然这些节点也不必产生了， 因此提高了算法的效 率， 这就是 Alpha-beta 过程。

20 人工智能 吉林大学珠海学院计算机科学与技术系

21 人工智能 吉林大学珠海学院计算机科学与技术系 Alpha-beta 剪枝的原则 1 。 在任一个 MIN 节点， 如果发现了其 beta 值小于或者 等于它的一个 MAX 祖先节点的 alpha 值，则可以剪枝 2 。 在任一个 MAX 节点下， 如果发现了其 alpha 值大于 或者等于它的一个 MIN 祖先节点的 bata 值，则可以剪枝

22 人工智能 吉林大学珠海学院计算机科学与技术系 253 120 3 3 3 MAX MIN MAX 0 2

23 人工智能 吉林大学珠海学院计算机科学与技术系 MI N 图 3.8 alpha-beta 剪枝过程 0 5 -3 3 3 -3 0 2 2 -3 0 -2 3 5 4 1 -3 0 6 8 9 -3 MA X 最佳移动 β=0 α=0 β=0 α=0 α=1 β=-3 β=1 α=6 α=1