与或图搜索问题.pptVIP

1 第二章 与或图搜索问题 目标 目标 初始节点s a b c 2 第二章 与或图搜索问题 与或树是用于表示问题及其求解过程的又一种形式化 方法。 对于一个复杂问题，直接求解往往比较困难，因此通 过下述方法进行简化： 分解：把一个复杂问题简化为若干简单的子问题，重 复此过程，直到不需要再分解或者不能再分解为止。 若每个子问题都可求解，则原问题可求解。因此下图 称为“与”树。 P P3 P2 P1 3 第二章 与或图搜索问题 等价变换：对于一个复杂问题，除了可用“分解”方法 进行求解外，还可利用同构或同态的等价变换，把它 变换为若干个较为容易求解的新问题。若新问题中有 一个可求解，则就得到了原问题的解。因此下图称为“ 或”树 P P3 P2 P1 4 第二章 与或图搜索问题 与或树 P P3 P2 P1 P12P11 P32P33 P31 5 2.1 基本概念 本原问题：不能再分解或变换，而且可以直接求解的 子问题。 端节点与终止节点：没有子节点的节点称为端节点； 本原问题所对应的节点称为终止节点。显然，终止节 点一定是端节点，但端节点不一定是终止节点。 可解节点：满足下列条件之一者，称为可解节点： 1. 它是一个终止节点； 2. 它是一个“或”节点，且其子节点中至少有一个是可 解节点； 3.它是一个“与”节点，且其子节点中全部都是可解节点 。 6 2.1 基本概念 不可解节点：关于可解节点的三个条件 全部不满足的节点称为不可解节点。 解树：由可解节点构成，并且由这些节 点可推出初始节点（它对应于原始问题 ）为可解节点的子树称为解树。 7 解树 P t tt P t t t 8 与或树的广度优先搜索 1. 把初始节点S0放入OPEN表。 2. 把OPEN表中的第一个节点（记为节点n)取出放入CLOSED 表。 3. 如果节点n可扩展，则作下列工作： 3.1 扩展节点n，将其子节点放入OPEN 表的尾部，并为每 个子节点配置指向父节点的指针，以备标识过程使用。 3.2 考察这些子节点中有否终止节点。若有，则标识这些终 止节点为可解节点，并应用可解标识过程对其父节点、祖父 节点等先辈节点中的可解节点进行标识。如果初始节点S0也被 标识为可解节点，就得到了解树，搜索成果，退出搜索过程 ；如果不能确定S0为可解节点，则从OPEN表中删去具有可解 先辈的节点。 3.3 转第2步。 9 与或树的广度优先搜索（续） 4. 如果节点n不可扩展，则作下列工作。 4.1. 标识节点n为不可解节点。 4.2. 应用不可解标识过程对节点n的先辈节点中不 可解的节点进行标识，如果初始节点S0也被标识为不 可解节点，则搜索失败，表明原问题无解，退出搜索 过程；如果不能确定S0为不可解节点，则从OPEN表 中删去具有不可解先辈的节点。 4.3 转第2步。 10 与或树的广度优先搜索：示例 2 1 3 4t1 A B t2 t4 t3 5 11 与或树的广度优先搜索：示例 (1).首先扩展1号节点，得到2号节点和3号节点 ，由于这两个子节点均不是终止节点，所以接 着扩展2号节点。此时OPEN表中只剩下3号节 点。 (2).扩展2号节点后，得到4号节点和t1节点。此 时OPEN表中的节点有：3，4, t1。由于t1是终止 节点，则标识它为可解节点，并应用可解标识 过程，对其先辈节点中的可解节点进行标识。 在此例中，因为t1的父节点是一个“与”节点， 因此仅有t1可解尚不能确定2号节点是否为可解 节点 。所以继续搜索。下一步扩展的节点是3 号节点。 12 示例(续) 扩展3号节点得到5号节点与B节点，两者都不 是终止节点，所以接着扩展4号节点。 扩展4号节点后得到节点A和t2。由于t2是终止 节点，所以标识它为可解节点，并用可解标识 过程标识出4、2均为可解节点，但1号节点目 前还不能确定它是否是可解节点。此时5号节 点是OPEN标中的第一个待考察的节点，所以 下一步扩展5号节点。 扩展5号节点，得到t3、t4，由于t3、t4均为终止 节点，所以被标识为可解节点，通过应用可解 标识过程可得到5、3、1号节点均为可解节点 。 13 与或树的有界深度优先搜索 1. 把初始节点S0放入OPEN表。 2. 把OPEN表中的第一个节点（记为节点n)取出放入CLOSED 表。 3. 如果节点n的深度大于等于深度界限，则转第5步的5.1步。 4. 如果节点n可扩展，则作下列工作： 4.1 扩展节点n，将其子节点放入OPEN 表的首部，并为每 个子节点配置指向父节点的指针，以备标识过程使用。 4.2 考察这些子节点中有否终止节点。若有，则标识这些终 止节点为可解节点，并应用可解标识过程对其父节点、祖父 节点等先辈节点中的可解节点进行标识。如果初始节点S0也被 标识为可解节点，就得到了解树，搜索成果，退出搜索过程 ；如果不能确定S0为可解节点，则从OPEN表中删去具有可解 先辈的节点。 4.3 转第2步。 14 与或树的有界深度优先搜索（续） 5. 如果节点n不可扩展，则作下列工作。 5.1. 标识节点n为不可解节点。 5.2. 应用不可解标识过程对节点n的先辈节点中不 可解的节点进行标识，如果初始节点S0也被标识为不 可解节点，则搜索失败，表明原问题无解，退出搜索 过程；如果不能确定S0为不可解节点，则从OPEN表 中删去具有不可解先辈的节点。 5.3 转第2步。 15 与或树的有序搜索 与或树的有序搜索是用来求取代价最小 的解树的一种搜索方法，为了求得代价 最小的解树，就要在每次确定欲扩展的 节点时，先往前多看几步，计算以下扩 展这个节点可能要付出的代价，并选择 代价最小的节点进行扩展。像这样根据 代价决定搜索路线的方法称为与或树的 有序搜索，它是一种启发式搜索策略。 16 与或树的有序搜索：耗散值的计算 设用c(x,y)表示节点x到其子节点y的代价，则计算节点x 的方法如下： 1.如果x是终止节点，则定义节点x的代价h(x)=0; 2.如果x是“或”节点， y1, y2, , yn是它的子节点，则节 点x的代价由下式计算得到 h(x)=minc(x, yi) + h(yi) 3.如果x是“与”节点， 则节点x的代价有两种计算方法 ：和代价法与最大代价法。 4.和代价法： 5.最大代价法： 6.如果x不可扩展，且又不是终止节点，则定义h(x)= 。 17 耗散值（代价值）的计算：示例 解树：S0, A, t1和t2。S0, B, D, G, t4和t5。 由左边的解树可得： 和代价：h(A)=11,h(S0)=13 最大代价： h(A)=6,h(S0)=8 由右边的解树可得： 和代价：h(G)=3,h(D)=4,h(B)=6,h(S0)=8 最大代价： h(G)=2,h(D)=3,h(B)=5,h(S0)=7 显然，若按和代价计算，右边的解树是最优解树，其代价为8；若按最大代 价计算，右边解树解树仍然是最优解树，其代价为7。 S0 A t1t2 E B CD FG t4t5 t3 2 65 1 2 2 1 2 3 1 1 2 18 与或树的有序搜索 计算任一节点x的代价h(x)时，都要求已知其子节点yi 的代价h(yi)。但搜索是自上而下进行的，即先有父节 点，后有子节点，除非节点x的全部子节点都是不可扩 展节点，否则子节点的代价是不知道的。那么如何计 算x的代价值h(x)呢？ 解决的办法是根据问题本身提供的启发式信息定义一 个启发函数，由此函数估算出子节点yi的代价h(yi)，然 后再按和代价或者最大代价计算出节点x的代价值h(x) 。有了h(x)，节点x的父节点、祖父节点以及直到初始 节点S0的各先辈节点的代价h都可自下而上的逐层推算 出来。 19 与或树的有序搜索 当节点yi被扩展后，也是先用启发函数估算出 其子节点的代价，然后再算出h(yi)。此时算出 的h(yi)可能与原先估算出的h(yi)不相同，这时 应该用后算出的h(yi)取代原先估算出的h(yi)， 并且按此h(yi)自下而上地重新计算各先辈节点 的h值。当节点yi的子节点又被扩展时，上述过 程又要重新进行一遍。总之，每当有一代新的 节点生成时，都要自下而上地重新计算其先辈 节点的代价，这是一个自上而下地生成节点， 又自下而上地计算代价h的反复进行的过程。 20 与或树的有序搜索：希望树 有序搜索的目的是求出最优解树，即代价最小的树。这就是要求搜索过程中 任一时刻求出的部分解树其代价是最小的。为此，每次选择欲扩展的节点时 都应挑选有希望成为最优解树一部分的节点进行扩展。由于这些节点及其先 辈节点（包括初始节点S0）所构成的与/或树有可能成为最优解树的一部分， 因此称它为希望树。 希望树： 1. 初始节点在希望树T中; 2. 如果节点x在希望树中，则一定有： 2.1 如果x是具有节点y1，y2，yn的“或” 节点，则具有 h(x) = minc(x, yi) + h(yi)值的那个子节点也应在T中。 2.2 如果x 是“与”节点，则它的全部子节点 都应在T中。 21 与或树的有序搜索：算法 1. 把初始节点S0放入OPEN表中。 2. 求出希望树T，即根据当前搜索树中节点的代价h求出以S0为根 的希望树T。 3. 依次把OPEN表中T的端节点N选出放入CLOSED表中。 4. 如果节点N是终止节点，则作如下工作： 4.1 标识N为可解节点。 4.2 对T应用可解标识过程，把N的先辈节点中的可解节点都标 识为可解节点。 4.3 若初始节点S0能被标识为可解节点，则T就是最优解树，成 功退出。 4.4 否则，从OPEN表中删去具有可解先辈的所有节点。 22 与或树的有序搜索：算法（续 ） 5. 如果节点N不是终止节点，且它不可扩展，则作下列工作： 5.1 标识N为不可解节点。 5.2 对T应用不可解 标识过程，把N的先辈节点中的不可解节点 都标识为不可解节点。 5.3 若初始节点S0也被标识为不可解节点，则失败退出。 5.4 否则，从OPEN表中删去具有不可解先辈的所有节点。 6.如果节点N不是终止节点，但它可扩展，则作下列工作： 6.1 扩展节点N，产生N的所有子节点。 6.2 把这些子节点都放入OPEN表中，并为每个子节点配置指向 父节点（节点N）的指针。 6.3 计算这些子节点的h值及其先辈节点的h值。 7. 转第2步。 23 与或树的有序搜索：示例 S0 A BC D EF 3 3 3 2 h(A)=8, h(D)=7, h(S0)=8, 右子树为希望 树 S0 A BC G D E H 2 22 32 F H(G)=7, h(H)=6, h(E)=7, h(D)=11, S0的右 子树算出的h(S0)12，而左子树的h(S0)9 ，因此左子树为希望树 一次扩展两层，B C E F 下面的值均为按某种启发 式方法估算出来的 24 与或树的有序搜索：示例 S0 A C G D E H 2 22 32 F h(L)=2, h(M)=6, h(B)=3, h(A)=8, L、B均为可解节点。但节 点C目前不能肯定是可解节点，故A和S0也还不能确定为可解节 点。左子树仍然是希望树，下面对节点C进行扩展。 M L B 00 2 2 3 25 与或树的有序搜索：示例 S0 A C G D E H 2 22 32 F h(N)=2, h(P)=7, h(C)=3, h(A)=8, 由此可推算出h(S0)9。 B P N 00 3 2 M L 0 02 2 博弈概述 诸如下棋、打牌、竞技、战争等一类竞争性智能活动称为博弈。 博弈有很多种，我们讨论最简单的“二人零和、全信息、非偶然“ 博弈，其特征如下： (1) 对垒的MAX、MIN双方轮流采取行动，博弈的结果只有 三种情况：MAX方胜，MIN方败；MIN方胜，MAX方败；和局 。 (2) 在对垒过程中，任何一方都了解当前的格局及过去的历史 。 (3) 任何一方在采取行动前都要根据当前的实际情况，进行得 失分析，选取对自已为最有利而对对方最为不利的对策，不存在 掷骰子之类的“碰运气“因素。即双方都是很理智地决定自己的行 动。 博弈概述 在博弈过程中，任何一方都希望自己取得胜利。因此，当某一方 当前有多个行动方案可供选择时，他总是挑选对自己最为有利而 对对方最为不利的那个行动方案。此时，如果我们站在MAX方的 立场上，则可供MAX方选择的若干行动方案之间是“或“关系，因 为主动权操在MAX方手里，他或者选择这个行动方案，或者选择 另一个行动方案，完全由MAX方自已决定。当MAX方选取任一 方案走了一步后，MIN方也有若干个可供选择的行动方案，此时 这些行动方案对MAX方来说它们之间则是“与“关系，因为这时主 动权操在MIN方手里，这些可供选择的行动方案中的任何一个都 可能被MIN方选中，MAX方必须应付每一种情况的发生。 博弈概述 这样，如果站在某一方(如MAX方，即MAX要取胜)，把上述博弈 过程用图表示出来，则得到的是一棵“与或树“。描述博弈过程的 与或树称为博弈树，它有如下特点： (1) 博弈的初始格局是初始节点。 (2) 在博弈树中，“或“节点和“与“节点是逐层交替出现的。自 己一方扩展的节点之间是“或“关系，对方扩展的节点之间是“与“ 关系。双方轮流地扩展节点。 (3) 所有自己一方获胜的终局都是本原问题，相应的节点是可 解节点；所有使对方获胜的终局都认为是不可解节点。 我们假定MAX先走，处于奇数深度级的节点都对应下一步由 MAX走，这些节点称为MAX节点，相应地偶数级为MIN节点。 1997年5月11日，IBM开发的“深蓝” 击败了国际象棋冠军卡斯帕罗夫。 1980年他获得世界少年组冠军 1982年他并列夺得苏联冠军 1985年22岁的卡斯帕罗夫成为历史上最年轻的国 际象棋冠军 积分是2849，这一分数是有史以来最高分。 远远领先于第二位的克拉姆尼克的2770 卡氏何许人也？ 电脑棋手：永不停歇的挑战！ 1988年“深思”击败了丹麦特级大 师拉森。 1993年“深思”第二代击败了丹麦 世界优秀女棋手小波尔加。 电脑棋手：永不停歇的挑战！ 2001年“更弗里茨” 击败了除了克拉 姆尼克之外的所有排名世界前十位 的棋手。 2002年10月“更弗里茨”与世界棋王 克拉姆尼克在巴林交手，双方以4 比4战平。 2003年1至2月“更年少者”与卡斯帕 罗夫在纽约较量，3比3战平。 许多人在努力 机器博弈 20世纪50年代，有人设想利用机器智能来实现机器与 人的对弈。 1997年IBM的“深蓝”战胜了国际象棋世界冠军卡斯帕 罗夫，惊动了世界。 加拿大阿尔伯塔大学的奥赛罗程序Logistello和西洋跳 棋程序Chinook也相继成为确定的、二人、零和、完 备信息游戏世界冠军 西洋双陆棋这样的存在非确定因素的棋类也有了美国 卡内基梅隆大学的西洋双陆琪程序BKG这样的世界冠 军。 对围棋、中国象棋、桥牌、扑克等许多种其它种类游 戏博弈的研究也正在进行中。 机器博弈的基本思想 机器博弈的核心思想就是对博弈树节点 的估值过程和对博弈树搜索过程的结合 博弈树 在博弈的任何一个中间阶段，站在博弈 双方其中一方的立场上，可以构想一个 博弈树。这个博弈树的根节点是当前时 刻的棋局，它的儿子节点是假设再行棋 一步以后的各种棋局，孙子节点是从儿 子节点的棋局再行棋一步的各种棋局， 以此类推，构造整棵博弈树，直到可以 分出胜负的棋局。 机器博弈系统的构成 知识表示 规则集，产生机制，构建博弈树 搜索技术 估值技术 博弈搜索 博弈搜索的基本思想已经提出半个多世纪，目前广泛 研究的是确定的、二人、零和、完备信息的博弈搜索 。 没有随机因素的博弈在两个人之间进行，在任何一个时刻， 一方失去的利益即为另一方得到的利益，不会出现“双赢”的 局面，而且在任何时刻，博弈的双方都明确的知道每一个棋 子是否存在和存在于哪里。 二人、零和、完备信息的博弈搜索理论已经很系统。 极大极小算法是所有搜索算法的基础。 一类是作为主流的深度优先的alpha-beta搜索及其系列增强 算法 另一类是最佳优先的系列算法。 解谜：电脑是怎样下棋的 人机博弈程序的一般设计方法 以中国 棋为例 （1）第一步该做什么？ 数据结构的选取棋盘表示 占用空间-少 操作速度-快 是否方便-方便 在机器中表示棋局，让程序知道 博弈状态。 九列十行 十四种不同的棋子 三十二个棋子 几种棋盘表示的方式 二维数组直观 紧凑的数据结构省空间，不直 观，速度? 比特棋盘用于8*8棋盘（国际象 棋），64位主机 （2）接下来怎么办？ 产生合法走步的规则，使博弈能公正 的进行，并且能够判断对手是否乱走 。依赖于具体棋类特征。 是一段将局面所有可能的正确走法罗 列出来的程序。称之为走法产生。 几种走法产生的实现方式 一般做法 建立小型数据库 位运算 位运算走法产生之例 寻找象的可走步 位运算走法产生之要求 一个基于比特棋盘的完善的数据库 该数据库应位于内存中 （3）终于到核心了 从所有的走法中找出最佳的走法， 也就是 48 2.3 博弈树搜索 博弈问题：诸如下棋、打牌、战争等一类竞争性智能活 动称为博弈。其中最为简单的一种称为“二人零和、全 信息、非偶然”博弈。 对垒的A、B双方轮流采取行动，博弈的结果只有三种 情况：A方胜，B方败；B方胜、A方败；双方战成平局 。 在对垒过程中，任何一方都了解当前的格局及过去的历 史。 任何一方在采取行动前都要根据当前的实际情况，进行 得失分析，选取对自己最为有利而对对方最为不利的对 策，不存在“碰运气”的偶然因素。即双方都是很理智地 决定自己的行动。 49 中国象棋 一盘棋平均走50步，总状态数约为10的 161次方。 假设1毫微秒走一步，约需10的145次方 年。 结论：不可能穷举。 50 极大极小方法 基本思想： 1. 设博弈的一方为A、一方为B。极大极小分析法是为其中的一方（如A）寻 找一个最优行动方案的方法。 2. 为了找到当前的最优行动方案，需要对各个方案可能产生的后果进行比较 。具体地说，就是要考虑每一方案实施后对方可能采取的所有行动，并计算 可能的得分。 3. 为计算得分，需要根据问题的特性信息定义一个估价函数，用来估算当前 博弈树端节点的得分。此时估算出来的得分称为静态估值。 4. 当端节点的估值计算出来后，再推算出父节点的得分。其方法是：对“或” 节点，选其子节点中一个最大的得分作为父节点的得分，这是为了使自己在 可供选择的方案中选一个对自己最有利的方案；对“与”节点，选其子节点中 一个最小的得分作为父节点的得分，这是为了立足于最坏的情况。这样计算 出的父节点的得分称为倒推值。 5. 如果一个行动方案能获得较大的倒推值，则它就是当前最好的行动方案。 51 1，极小极大过程 05 -3 33 -3022 -30-23541-3 06 89-3 0-3 3-3 -3-2 1 -3 6-3 0316 0 1 1 极大 极小 a b 52 极大极小分析法：一子棋 一子棋游戏：估价函数定义如下 设棋局为P，估价函数为e(P)： 1. 若P是A必胜的棋局，则e(P)； 2. 若P是B必胜的棋局，则e(P)； 3. 若P是胜负未定的棋局，则e(P)=e(+P)- e(-P)。其中， e(+P)表示在棋局P上添上 所有的a后直线的数目， e(-P)表示在棋局 P上添上所有的b后直线的数目。 53 极大极小分析法：一子棋 A的第一着棋生成的博弈树。每一着棋都要导致 博弈树深度加2：一层是自己，一层是对方。 54 55 56 -剪枝 上述的极小极大分析法，实际是先生成一棵 博弈树，然后再计算其倒推值，致使极小极 大分析法效率较低。于是在极小极大分析法 的基础上提出了-剪枝技术。 -剪枝技术的基本思想或算法是，边生成博 弈树边计算评估各节点的倒推值，并且根据 评估出的倒推值范围，及时停止扩展那些已 无必要再扩展的子节点，即相当于剪去了博 弈树上的一些分枝，从而节约了机器开销， 提高了搜索效率。 57 -剪枝 S0 A B E DC H GF NMLP Q XX I SR X J TX K U X XX 284 1 -2 5 9 1 -5 2 1-2 2 5 2 5 1 -5 1 1 2 “与”节点G的值不能升高其父节 点C的值，则对节点G以下的分 枝可停止搜索，并使G的倒推值为 。这种剪枝称为剪枝 “或”节点D的值不能降低其父 节点A的值，则对节点D以下的 分枝可停止搜索，并使D的倒推 值为。这种剪枝称为剪枝。 58 (1) 对于一个与节点MIN，若能估计出其倒推值的上确 界，并且这个值不大于 MIN的父节点(一定是或节点 )的估计倒推值的下确界，即，则就不必再扩展该 MIN节点的其余子节点了(因为这些节点的估值对MIN 父节点的倒推值已无任何影响 了)。这一过程称为剪 枝。 (2) 对于一个或节点MAX，若能估计出其倒推值的下确 界，并且这个值不小于 MAX的父节点(一定是与节 点)的估计倒推值的上确界，即，则就不必再扩展 该MAX节点的其余子节点了(因为这些节点的估值对 MAX父节点的倒推值已无任何影响 了)。这一过程称 为剪枝。 59 从算法中看到： (1)