与或图搜索问题

1、第二章 与或图搜索问题,第二章 与或图搜索问题,与或树是用于表示问题及其求解过程的又一种形式化方法。 对于一个复杂问题，直接求解往往比较困难，因此通过下述方法进行简化： 分解：把一个复杂问题简化为若干简单的子问题，重复此过程，直到不需要再分解或者不能再分解为止。若每个子问题都可求解，则原问题可求解。因此下图称为“与”树,第二章 与或图搜索问题,等价变换：对于一个复杂问题，除了可用“分解”方法进行求解外，还可利用同构或同态的等价变换，把它变换为若干个较为容易求解的新问题。若新问题中有一个可求解，则就得到了原问题的解。因此下图称为“或”树,第二章 与或图搜索问题,与或树,2.1 基本概念,本原问题

2、：不能再分解或变换，而且可以直接求解的子问题。 端节点与终止节点：没有子节点的节点称为端节点；本原问题所对应的节点称为终止节点。显然，终止节点一定是端节点，但端节点不一定是终止节点。 可解节点：满足下列条件之一者，称为可解节点： 1. 它是一个终止节点； 2. 它是一个“或”节点，且其子节点中至少有一个是可解节点； 3.它是一个“与”节点，且其子节点中全部都是可解节点,2.1 基本概念,不可解节点：关于可解节点的三个条件全部不满足的节点称为不可解节点。 解树：由可解节点构成，并且由这些节点可推出初始节点（它对应于原始问题）为可解节点的子树称为解树,解树,与或树的广度优先搜索,1. 把初始节点S

3、0放入OPEN表。 2. 把OPEN表中的第一个节点（记为节点n)取出放入CLOSED表。 3. 如果节点n可扩展，则作下列工作： 3.1 扩展节点n，将其子节点放入OPEN 表的尾部，并为每个子节点配置指向父节点的指针，以备标识过程使用。 3.2 考察这些子节点中有否终止节点。若有，则标识这些终止节点为可解节点，并应用可解标识过程对其父节点、祖父节点等先辈节点中的可解节点进行标识。如果初始节点S0也被标识为可解节点，就得到了解树，搜索成果，退出搜索过程；如果不能确定S0为可解节点，则从OPEN表中删去具有可解先辈的节点。 3.3 转第2步,与或树的广度优先搜索（续,4. 如果节点n不可扩展，

4、则作下列工作。 4.1. 标识节点n为不可解节点。 4.2. 应用不可解标识过程对节点n的先辈节点中不可解的节点进行标识，如果初始节点S0也被标识为不可解节点，则搜索失败，表明原问题无解，退出搜索过程；如果不能确定S0为不可解节点，则从OPEN表中删去具有不可解先辈的节点。 4.3 转第2步,与或树的广度优先搜索：示例,与或树的广度优先搜索：示例,1).首先扩展1号节点，得到2号节点和3号节点，由于这两个子节点均不是终止节点，所以接着扩展2号节点。此时OPEN表中只剩下3号节点。 (2).扩展2号节点后，得到4号节点和t1节点。此时OPEN表中的节点有：3，4, t1。由于t1是终止节点，则标

5、识它为可解节点，并应用可解标识过程，对其先辈节点中的可解节点进行标识。在此例中，因为t1的父节点是一个“与”节点，因此仅有t1可解尚不能确定2号节点是否为可解节点 。所以继续搜索。下一步扩展的节点是3号节点,示例(续,扩展3号节点得到5号节点与B节点，两者都不是终止节点，所以接着扩展4号节点。 扩展4号节点后得到节点A和t2。由于t2是终止节点，所以标识它为可解节点，并用可解标识过程标识出4、2均为可解节点，但1号节点目前还不能确定它是否是可解节点。此时5号节点是OPEN标中的第一个待考察的节点，所以下一步扩展5号节点。 扩展5号节点，得到t3、t4，由于t3、t4均为终止节点，所以被标识为可

6、解节点，通过应用可解标识过程可得到5、3、1号节点均为可解节点,与或树的有界深度优先搜索,1. 把初始节点S0放入OPEN表。 2. 把OPEN表中的第一个节点（记为节点n)取出放入CLOSED表。 3. 如果节点n的深度大于等于深度界限，则转第5步的5.1步。 4. 如果节点n可扩展，则作下列工作： 4.1 扩展节点n，将其子节点放入OPEN 表的首部，并为每个子节点配置指向父节点的指针，以备标识过程使用。 4.2 考察这些子节点中有否终止节点。若有，则标识这些终止节点为可解节点，并应用可解标识过程对其父节点、祖父节点等先辈节点中的可解节点进行标识。如果初始节点S0也被标识为可解节点，就得到

7、了解树，搜索成果，退出搜索过程；如果不能确定S0为可解节点，则从OPEN表中删去具有可解先辈的节点。 4.3 转第2步,与或树的有界深度优先搜索（续,5. 如果节点n不可扩展，则作下列工作。 5.1. 标识节点n为不可解节点。 5.2. 应用不可解标识过程对节点n的先辈节点中不可解的节点进行标识，如果初始节点S0也被标识为不可解节点，则搜索失败，表明原问题无解，退出搜索过程；如果不能确定S0为不可解节点，则从OPEN表中删去具有不可解先辈的节点。 5.3 转第2步,与或树的有序搜索,与或树的有序搜索是用来求取代价最小的解树的一种搜索方法，为了求得代价最小的解树，就要在每次确定欲扩展的节点时，先

8、往前多看几步，计算以下扩展这个节点可能要付出的代价，并选择代价最小的节点进行扩展。像这样根据代价决定搜索路线的方法称为与或树的有序搜索，它是一种启发式搜索策略,与或树的有序搜索：耗散值的计算,设用c(x,y)表示节点x到其子节点y的代价，则计算节点x的方法如下： 如果x是终止节点，则定义节点x的代价h(x)=0; 如果x是“或”节点， y1, y2, , yn是它的子节点，则节点x的代价由下式计算得到 h(x)=minc(x, yi) + h(yi) 如果x是“与”节点， 则节点x的代价有两种计算方法：和代价法与最大代价法。 和代价法： 最大代价法： 如果x不可扩展，且又不是终止节点，则定义h

9、(x),耗散值（代价值）的计算：示例,解树：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,与或树的有序搜索,计算任一节点x的代价h(x)时，都要求已知其子节点yi的代价h(yi)。但搜索是自上而下进行的，即

10、先有父节点，后有子节点，除非节点x的全部子节点都是不可扩展节点，否则子节点的代价是不知道的。那么如何计算x的代价值h(x)呢？ 解决的办法是根据问题本身提供的启发式信息定义一个启发函数，由此函数估算出子节点yi的代价h(yi)，然后再按和代价或者最大代价计算出节点x的代价值h(x)。有了h(x)，节点x的父节点、祖父节点以及直到初始节点S0的各先辈节点的代价h都可自下而上的逐层推算出来,与或树的有序搜索,当节点yi被扩展后，也是先用启发函数估算出其子节点的代价，然后再算出h(yi)。此时算出的h(yi)可能与原先估算出的h(yi)不相同，这时应该用后算出的h(yi)取代原先估算出的h(yi)，

11、并且按此h(yi)自下而上地重新计算各先辈节点的h值。当节点yi的子节点又被扩展时，上述过程又要重新进行一遍。总之，每当有一代新的节点生成时，都要自下而上地重新计算其先辈节点的代价，这是一个自上而下地生成节点，又自下而上地计算代价h的反复进行的过程,与或树的有序搜索：希望树,有序搜索的目的是求出最优解树，即代价最小的树。这就是要求搜索过程中任一时刻求出的部分解树其代价是最小的。为此，每次选择欲扩展的节点时都应挑选有希望成为最优解树一部分的节点进行扩展。由于这些节点及其先辈节点（包括初始节点S0）所构成的与/或树有可能成为最优解树的一部分，因此称它为希望树。 希望树： 1. 初始节点在希望树T中

12、; 2. 如果节点x在希望树中，则一定有： 2.1 如果x是具有节点y1，y2，yn的“或”节点，则具有 h(x) = minc(x, yi) + h(yi)值的那个子节点也应在T中。 2.2 如果x 是“与”节点，则它的全部子节点都应在T中,与或树的有序搜索：算法,1. 把初始节点S0放入OPEN表中。 2. 求出希望树T，即根据当前搜索树中节点的代价h求出以S0为根的希望树T。 3. 依次把OPEN表中T的端节点N选出放入CLOSED表中。 4. 如果节点N是终止节点，则作如下工作： 4.1 标识N为可解节点。 4.2 对T应用可解标识过程，把N的先辈节点中的可解节点都标识为可解节点。 4

13、.3 若初始节点S0能被标识为可解节点，则T就是最优解树，成功退出。 4.4 否则，从OPEN表中删去具有可解先辈的所有节点,与或树的有序搜索：算法（续,5. 如果节点N不是终止节点，且它不可扩展，则作下列工作： 5.1 标识N为不可解节点。 5.2 对T应用不可解 标识过程，把N的先辈节点中的不可解节点都标识为不可解节点。 5.3 若初始节点S0也被标识为不可解节点，则失败退出。 5.4 否则，从OPEN表中删去具有不可解先辈的所有节点。 6.如果节点N不是终止节点，但它可扩展，则作下列工作： 6.1 扩展节点N，产生N的所有子节点。 6.2 把这些子节点都放入OPEN表中，并为每个子节点配

14、置指向父节点（节点N）的指针。 6.3 计算这些子节点的h值及其先辈节点的h值。 7. 转第2步,与或树的有序搜索：示例,H(G)=7, h(H)=6, h(E)=7, h(D)=11, S0的右子树算出的h(S0)12，而左子树的h(S0)9，因此左子树为希望树,一次扩展两层，B C E F下面的值均为按某种启发式方法估算出来的,与或树的有序搜索：示例,与或树的有序搜索：示例,博弈概述,诸如下棋、打牌、竞技、战争等一类竞争性智能活动称为博弈。博弈有很多种，我们讨论最简单的二人零和、全信息、非偶然博弈，其特征如下：(1) 对垒的MAX、MIN双方轮流采取行动，博弈的结果只有三种情况：MAX方胜

15、，MIN方败；MIN方胜，MAX方败；和局。(2) 在对垒过程中，任何一方都了解当前的格局及过去的历史。(3) 任何一方在采取行动前都要根据当前的实际情况，进行得失分析，选取对自已为最有利而对对方最为不利的对策，不存在掷骰子之类的碰运气因素。即双方都是很理智地决定自己的行动,博弈概述,在博弈过程中，任何一方都希望自己取得胜利。因此，当某一方当前有多个行动方案可供选择时，他总是挑选对自己最为有利而对对方最为不利的那个行动方案。此时，如果我们站在MAX方的立场上，则可供MAX方选择的若干行动方案之间是或关系，因为主动权操在MAX方手里，他或者选择这个行动方案，或者选择另一个行动方案，完全由MAX方

16、自已决定。当MAX方选取任一方案走了一步后，MIN方也有若干个可供选择的行动方案，此时这些行动方案对MAX方来说它们之间则是与关系，因为这时主动权操在MIN方手里，这些可供选择的行动方案中的任何一个都可能被MIN方选中，MAX方必须应付每一种情况的发生,博弈概述,这样，如果站在某一方(如MAX方，即MAX要取胜)，把上述博弈过程用图表示出来，则得到的是一棵与或树。描述博弈过程的与或树称为博弈树，它有如下特点：(1) 博弈的初始格局是初始节点。(2) 在博弈树中，或节点和与节点是逐层交替出现的。自己一方扩展的节点之间是或关系，对方扩展的节点之间是与关系。双方轮流地扩展节点。(3) 所有自己一方获

17、胜的终局都是本原问题，相应的节点是可解节点；所有使对方获胜的终局都认为是不可解节点。我们假定MAX先走，处于奇数深度级的节点都对应下一步由MAX走，这些节点称为MAX节点，相应地偶数级为MIN节点,1997年5月11日，IBM开发的“深蓝”击败了国际象棋冠军卡斯帕罗夫,1980年他获得世界少年组冠军 1982年他并列夺得苏联冠军 1985年22岁的卡斯帕罗夫成为历史上最年轻的国 际象棋冠军 积分是2849，这一分数是有史以来最高分。 远远领先于第二位的克拉姆尼克的2770,卡氏何许人也,电脑棋手：永不停歇的挑战,1988年“深思”击败了丹麦特级大师拉森。 1993年“深思”第二代击败了丹麦世界

18、优秀女棋手小波尔加,电脑棋手：永不停歇的挑战,2001年“更弗里茨” 击败了除了克拉姆尼克之外的所有排名世界前十位的棋手。 2002年10月“更弗里茨”与世界棋王克拉姆尼克在巴林交手，双方以4比4战平。 2003年1至2月“更年少者”与卡斯帕罗夫在纽约较量，3比3战平,许多人在努力,机器博弈,20世纪50年代，有人设想利用机器智能来实现机器与人的对弈。 1997年IBM的“深蓝”战胜了国际象棋世界冠军卡斯帕罗夫，惊动了世界。 加拿大阿尔伯塔大学的奥赛罗程序Logistello和西洋跳棋程序Chinook也相继成为确定的、二人、零和、完备信息游戏世界冠军 西洋双陆棋这样的存在非确定因素的棋类也有

19、了美国卡内基梅隆大学的西洋双陆琪程序BKG这样的世界冠军。 对围棋、中国象棋、桥牌、扑克等许多种其它种类游戏博弈的研究也正在进行中,机器博弈的基本思想,机器博弈的核心思想就是对博弈树节点的估值过程和对博弈树搜索过程的结合,博弈树,在博弈的任何一个中间阶段，站在博弈双方其中一方的立场上，可以构想一个博弈树。这个博弈树的根节点是当前时刻的棋局，它的儿子节点是假设再行棋一步以后的各种棋局，孙子节点是从儿子节点的棋局再行棋一步的各种棋局，以此类推，构造整棵博弈树，直到可以分出胜负的棋局,机器博弈系统的构成,知识表示 规则集，产生机制，构建博弈树 搜索技术 估值技术,博弈搜索,博弈搜索的基本思想已经提出

20、半个多世纪，目前广泛研究的是确定的、二人、零和、完备信息的博弈搜索。 没有随机因素的博弈在两个人之间进行，在任何一个时刻，一方失去的利益即为另一方得到的利益，不会出现“双赢”的局面，而且在任何时刻，博弈的双方都明确的知道每一个棋子是否存在和存在于哪里。 二人、零和、完备信息的博弈搜索理论已经很系统。极大极小算法是所有搜索算法的基础。 一类是作为主流的深度优先的alpha-beta搜索及其系列增强算法 另一类是最佳优先的系列算法,解谜：电脑是怎样下棋的 人机博弈程序的一般设计方法,以中国 棋为例,1）第一步该做什么,数据结构的选取,棋盘表示,占用空间-少 操作速度-快 是否方便-方便,在机器中表

21、示棋局，让程序知道 博弈状态,九列十行,十四种不同的棋子,三十二个棋子,几种棋盘表示的方式,二维数组直观,紧凑的数据结构省空间，不直 观，速度,比特棋盘用于8*8棋盘（国际象 棋），64位主机,2）接下来怎么办,产生合法走步的规则，使博弈能公正的进行，并且能够判断对手是否乱走。依赖于具体棋类特征。 是一段将局面所有可能的正确走法罗列出来的程序。称之为走法产生,几种走法产生的实现方式,一般做法,建立小型数据库,位运算,位运算走法产生之例,寻找象的可走步,位运算走法产生之要求,一个基于比特棋盘的完善的数据库 该数据库应位于内存中,3）终于到核心了,从所有的走法中找出最佳的走法， 也就是,搜索,2.

22、3 博弈树搜索,博弈问题：诸如下棋、打牌、战争等一类竞争性智能活动称为博弈。其中最为简单的一种称为“二人零和、全信息、非偶然”博弈。 对垒的A、B双方轮流采取行动，博弈的结果只有三种情况：A方胜，B方败；B方胜、A方败；双方战成平局。 在对垒过程中，任何一方都了解当前的格局及过去的历史。 任何一方在采取行动前都要根据当前的实际情况，进行得失分析，选取对自己最为有利而对对方最为不利的对策，不存在“碰运气”的偶然因素。即双方都是很理智地决定自己的行动,中国象棋,一盘棋平均走50步，总状态数约为10的161次方。 假设1毫微秒走一步，约需10的145次方年。 结论：不可能穷举,极大极小方法,基本思想

23、： 1. 设博弈的一方为A、一方为B。极大极小分析法是为其中的一方（如A）寻找一个最优行动方案的方法。 2. 为了找到当前的最优行动方案，需要对各个方案可能产生的后果进行比较。具体地说，就是要考虑每一方案实施后对方可能采取的所有行动，并计算可能的得分。 3. 为计算得分，需要根据问题的特性信息定义一个估价函数，用来估算当前博弈树端节点的得分。此时估算出来的得分称为静态估值。 4. 当端节点的估值计算出来后，再推算出父节点的得分。其方法是：对“或”节点，选其子节点中一个最大的得分作为父节点的得分，这是为了使自己在可供选择的方案中选一个对自己最有利的方案；对“与”节点，选其子节点中一个最小的得分作

24、为父节点的得分，这是为了立足于最坏的情况。这样计算出的父节点的得分称为倒推值。 5. 如果一个行动方案能获得较大的倒推值，则它就是当前最好的行动方案,1，极小极大过程,极大极小分析法：一子棋,一子棋游戏：估价函数定义如下 设棋局为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后直线的数目,极大极小分析法：一子棋,A的第一着棋生成的博弈树。每一着棋都要导致博弈树深度加2：一层是自

25、己，一层是对方,剪枝,上述的极小极大分析法，实际是先生成一棵博弈树，然后再计算其倒推值，致使极小极大分析法效率较低。于是在极小极大分析法的基础上提出了-剪枝技术。 -剪枝技术的基本思想或算法是，边生成博弈树边计算评估各节点的倒推值，并且根据评估出的倒推值范围，及时停止扩展那些已无必要再扩展的子节点，即相当于剪去了博弈树上的一些分枝，从而节约了机器开销，提高了搜索效率,剪枝,与”节点G的值不能升高其父节点C的值，则对节点G以下的分枝可停止搜索，并使G的倒推值为。这种剪枝称为剪枝,或”节点D的值不能降低其父节点A的值，则对节点D以下的分枝可停止搜索，并使D的倒推值为。这种剪枝称为剪枝,1) 对于一

26、个与节点MIN，若能估计出其倒推值的上确界，并且这个值不大于 MIN的父节点(一定是或节点)的估计倒推值的下确界，即，则就不必再扩展该 MIN节点的其余子节点了(因为这些节点的估值对MIN父节点的倒推值已无任何影响 了)。这一过程称为剪枝。(2) 对于一个或节点MAX，若能估计出其倒推值的下确界，并且这个值不小于 MAX的父节点(一定是与节点)的估计倒推值的上确界，即，则就不必再扩展该MAX节点的其余子节点了(因为这些节点的估值对MAX父节点的倒推值已无任何影响 了)。这一过程称为剪枝,从算法中看到：(1) MAX节点(包括起始节点)的值永不减少；(2) MIN节点(包括起始节点)的值永不增加。在搜索