[计算机软件及应用]3章-搜索--人工智能研究生课程.ppt

第 3 章 搜索（目录）,1,问题表达： 显示 状态图 与或树 隐式 搜索方法： 盲目 ( 固定法则) 启发 （启发信息）,3.1 显式存储 （状态空间表示法，与或树表示法则） 3.2 隐式存储 3.3 盲目搜索 （广度、 深度、有界深度、代价树优先搜索） 3.4 启发搜索 3.5 A算法 3.6 与或树的盲目和启发搜索 3.7 博弈树,结构不良或非结构化,3.1 显式存储.,2,显式存储的概念： 把问题的全部状态空间图直接都存于计算机中的方式称为图的显式存储。 适用条件：显式存储需要占据计算机的大量存储空间和处理时时间。 特点：其优点是直观、明了，但缺点是占据存储空间大。 图的显式存储仅适用于状态空间十分有限以及较简单的问题求解。 例1：计算机文件存储等均为图的显式存储方式，资源管理器，目录 。 例2： 后面,3.1.1 状态空间表示法,(1) 状态 (State) 表示问题求解过程中每一步问题状况的数据结构，它可形式地表示为： 当对每一个分量都给予确定的值时，就得到了一个具体的状态。 （2）操作（operator） 操作也称为算符，它是把问题从一种状态变换为另一种状态的手段。当对一个问题 使用某个可用操作时，它将引起该状态中某些分量值的变化，从而使问题从一个具 体状态变为另一个具体状态。操作可以是一个机械步骤、一个运算、一条规则或一 个过程。操作可以理解为状态集合上的一个函数，它描述了状态之间的关系。 （3）状态空间（State space） 用来描述一个问题的全部状态以及这些状态之间的相互关系。 状态常用一个三元组：(S，F，G)来表示。 S为问题的所有初始状态的集合；F为操作的集合，G为目标状态的集合。 状态空间也可用一个赋值的有向图来表示，该有向图称为状态空间图。 在状态空间 图 中，节点表示问题的状态，有向边表示操作。,问题的状态空间图例子,4,状态树 有向图来表达， 有向弧加以连接， 操作数O表示了状态之间的转换关系,修道士和野人 MC问题,(S，F，G),2 状态空间问题求解.,任何以状态和操作为基础的问题求解方法都可称为状态空间问题求解方法，简称状态空求解问题的基本过程是，首先为问题选择适当的“状态”及“操作”的形式化个初始状态出发，每次使用一个“操作”，递增地建立起操作序列，直到达到目标状态为止。此时，由初始状态到目标状态所使用的算符序列就是该问题的一个解。 上述问题求解过程实际上是一个搜索过程，至于具体的搜索方法我们将在后面详细讨论，这里是一个一般描述。,3.1 .2 与/或树表达.,问题归约 当一个问题比较复杂时，如果直接进行求解往往比较困难，此时可通过分解或变换， 将它转化为一系列较简单的问题，然后通过对这些较简单问题的求解来实现对原问题的求解。 本原问题。那种不能(或不需要)再进行分解或变换，且可以直接解答的子问题。 本原问题可以作为终止归约的限制条件。 1问题的分解与等价变换 当把一个问题归约为子问题时，可采用对原问题的分解或变换方法。 (1) 分解与 如果一个问题P可以归约为一组子问题P (P1，P2P。）并且只有当所有 子问题都有解时原问题P才有解，任何一个子问题Pi无解都会导致原问题P无解， 则称此种归约为问题的分解。即分解所得到的子问题的“与”与原问题P等价。 (2) 等价变换或 如果一个问题P可以归约为一组子问题P (P1，P2P。）并且这些子问题P都 无解时，原问题P才无解，则称此种归约为问题的等价变换，简称变换，即变换所 得到的子问题的“或”与原问题P等价。,2 问题归约的与或树表示,原问题归约为一系列本原问题的过程可以很方便地用一个与或树来表示。 (1) 与树 把一个原问题分解为若干个子问题可用一个“与树”来表示。 例如，设P可以分解为三个子问题P1、P2、P3的与，节点P为“与”节点。 (2) 或树 把一个原问题变换为若干个子问题可用一个“或树”来表示。 例如，设P可以变换为三个子问题P1、P2、P3的或，即节点P为“或”节点。 (3) 与或树 如果一个问题既需要通过分解，又需要通过变换才能得到其本原问题，则其归约过程 一般的归约过程多数是需要用与或树来表示的，其根节点对应着原始问题。 (4) 端节点与终止节点 没有子节点的节点称为端节点，本原问题所对应的节点称为终止节点。 (终止节点一定是端节点，但端节点却不一定是终止节点。),可解节点与不可解节点。,(5)可解节点与不可解节点 在与或树中，满足以下三个条件之一的节点为可解节点： 任何解构成终止节点都是可解节点。 对“或”节点，当其子节点中至少有一个为可解节点时，则该或节点就是可解节点。 对“与”节点，只有当其子节点全部为可解节点时，该与节点才是可解节点。 同样，可用类似的方法定义不可解节点： 不为终止节点的端节点是不可解节点。 对“或”节点，若其全部子节点都为不可解节点，则该或节点是不可解节点。 对“与”节点，只要其于节点中有一个为不可解节点，则该与节点是不可解节点。 (6) 解树 由可解节点构成， 并且由这些可解节点可以推出初始节点 (它对应着原始问题)为可解节点的子树为解树。 在解树中一定包含初始节点。,梵塔问题（表达）,9,例：梵塔问题(Tower of Hanoi Problem)。传说在印度贝那勒斯圣庙中，主神梵天 做了一个梵塔，它是在一个黄铜板上插有三根宝石针。其中在第一根针上，从下到 上，按照从大到小的顺序，贯穿了64片金片(如图所示)。梵天要求僧侣们轮流 把金片在三根宝石针之间移来移去，规定每次只能移动一片，且不许将大片压在小 片上，并说如果这64片金片全部移至另一根针上时，世界就会在一声霹雳之中毁灭。 梵塔问题(a) 初始状态 (b)目标状态之一（二）,梵塔问题的状态空间表示,10,例如用数组(Pa，Pb)表示，这里Pa，Pb1，2，3， 其中Pa代表A片处在Pa号宝石针上，Pb代表B片处在Pb号宝石针上根据9种可能状态，可以构成二阶梵塔问题的状态空间。,(Pa，Pb) （小大),三阶梵塔问题与或树表示,设有A、B、C三个金片及三根钢针，三个金片按自上而下从小到大的顺序穿在1号 钢针上，要求把它们全部移到3号钢针上，而且每次只能移动一个金片，任何时 刻都不能把大的金片压在小的金片上面，如图所示。 解；设用三元组(i，j，k) 表示问题在任一时刻的状态，用“”表示状态的转换。 在上述三元组中，i 代表金片C所在的钢针号，j 代表金片B所在的钢针号， k 代表金片A所在的钢针号。 利用问题归约方法，原问题可分解为以下三个子问题： (1) 把金片A及B移到2号钢针上的双金片移动问题。即 (1，1，1) (1，2，2) (2) 把金片C移到3号钢针上的单金片移动问题。 即 (1，2，2) (3，2，2) (3) 把金片A及B移到3号钢针的双金片移动问题。 即 (3，2，2) (3，3，3) 其中，子问题(1)和(3)都是一个二阶梵塔问题，它们都还可以再继续进行分解； 子问题(2)是本原问题，它已不需要再分解。,三阶梵塔问题的分解过程与或树.,（1、1、1） （1、1、3）,（1、1、1） （1、2、3）,（1、2、3） （1、2、2）,（3、2、2） （3、2、1）,（3、2、1） （3、3、1）,（3、3、1） （3、3、3）,三在该与或树中，有7个终止节点，它们分别对应着7个本原问题。 如果把这些本原问题从左至右排列起来，即得到了原始问题的解； (1，1，1) (1，1，3) (1，1，3) (1，2，3) (1，2，3) (1，2，2) (1，2，2) (3，2，2) (3，2，2) (3，2，1) (3，2，1) (3，3，1) (3，3，1) (3，3，3),3.2 隐式存储,13,(1) 图的隐式存储的概念： 仅在存储关于要求解问题的相关各种知识，只在必要时再由相关的信息和知识逐步生成状态空间图的方式称为图的隐式存储。 反向重构 (2) 适用条件：适用于一般问题求解，尤其适宜于状态空间极大的情况。 (3) 特点：优点是占据空间小，但不够直观，与图的显式存储的特点刚好相反。,3.3 搜索,14,3.3.3.1 搜索概念(Search) 搜索即寻找，设法在数量庞大、关系复杂的状态空间图中找到目标。 基本搜索策略 没有任何经验和知识起作用的、由某种规则所定的非智能性的搜索； 盲目搜索是按数学上的预定的控制策略进行搜索，在搜索过程中获得的中间信息并 不改变控制策略。由于搜索总是按预先规定的路线进行，没有考虑到问题本身的 特性，因此这种搜索具有盲目性，效率不高，不便于复杂问题的求解。 启发式搜索的特点在于是一种有准备的、追求效率而有的放矢的智能搜索，它要求 依据某种知识及信息的指导，通过步步探索，层层查找，逐一状态比较而找到符合 规定条件的目标状态解。 启发式搜索是在搜索中加入了与问题有关的启发性信息，用于指导搜索朝着最有 希望的方向前进，加速问题的求解过程并找到最优解。,3.3.1 搜索策略(树/网状结构图 ),15,盲目搜索(穷举式弱方法) 启发式搜索 广度优先搜索 (Breadth-first Search) 深度优先搜索 (Depth-first Search) 无穷分支，易于掉人陷阱。 有界深度优先搜索 代价树的推进搜索 例：电子（力）设备故障诊断 系统级子系统级板卡级组件级元件级（芯片级）,3.3.2 隐式图的搜索过程,隐式图的搜索过程的概念：根据要求解的问题在计算机中存储的有关知识， 逐步产生问题的状态空间图并检 （2）查解是否在其中的过程，叫做隐式图的搜索过程。隐式图的这种搜索过程是 我们求解问题的一种重要思考方法。 略例子。,3.3.3 状态空间图搜索典型例（编程基础）,17,3.3.3.1 修道士和野人MC 问题的状态空间图搜索求解分析（显式） 例 修道士和野人问题(The Missionaries and Cannibals Problem)。 在河的左岸有三个修道士、三个野人和一条船，修道士们想用这条船将所有的人 (修道士和野人)都运过河去，但是受到以下条件的限制：修道士和野人都会划船， 但船一次最多只能装运两个；在任何岸边野人数目都不得超过修道士，否则修道 士就会遭遇被野人攻击危险。试规划出一个确保全部成员安全过河的计划。 解 按上述步骤来进行求解分析： (1) 设定状态变量及确定值域 建立这个问题的状态空间， 设左岸的修道士数为m，则有m0，1，2，3； 对应右岸的修道士数为mR，则mR3 m； 左岸的野人数为c，则有c0，1，2，3； 对应右岸的野人数为cR，则cR3 c： 左岸的船数为b，故又有b=0，1，右岸的船数bR1 b,修道士和野人问题-2,(2) 确定状态组，分别列出初始状态集和目标状态集 问题的状态可以用一个三元数组来描述，以左岸的状态来标记，即 SL(m，c，b) 右岸的状态可以不必标出。 初始状态只有一个： So：(3，3，1)，初始状态表示了修道士和野人全部在河的左岸； 目标状态也只有一个：SG(0，0，0)，表示了修道士和野人从河的左岸全部渡河完毕。 (3) 定义并确定操作集 仍然以河的左岸为基点来考虑，把船从左岸划向右岸定义为 Pij 操作 (下标i表示船载的修道士数，j表示船载的野人数)； 同理，从右岸将船划回左岸称之为Q操作。则共有10和合法种操作，操作集为 F P0l，Pl0，P11，P02，P20，Q0l，Q10，Q11，Q02，Q20 (4) 估计全部的状态空间数 并尽可能列出全部的状态空间或予以描述 在这个问题中，全部的可能状态共有32个（4 4 2） 如下表所示。,18,修道士和野人问题-3,19,状态 m c b 状态 m c b 状态 m c b 状态 m c b S0 3 3 1 S8 1 3 1 S16 3 3 0 S24 1 3 0 S1 3 2 1 S9 1 2 1 S17 3 2 0 S25 1 2 0 S2 3 1 1 S10 1 1 1 S18 3 1 0 S26 1 1 0 S3 3 0 1 S11 1 0 1 S19 3 0 0 S27 1 0 0 S4 2 3 1 S12 0 3 1 S20 2 3 0 S28 0 3 0 S5 2 2 1 S13 0 2 1 S21 2 2 0 S29 0 2 0 S6 2 1 1 S14 0 1 1 S22 2 1 0 S30 0 1 0 S7 2 0 1 S15 0 0 1 S23 2 0 0 S31 0 0 0 S0：(3，3，1)为初始状态，Sn：(0，0，0)为目标状态。 按照题目规定的条件，应该划去不合法的状态，这样可以加快搜索求解的效率。例如，左岸边野人数目超过修道士的情况，S4、S8、S9、S20、S24、S25，6种； 右岸边野人数目超过修道土的情况，S6、S7、S11、S22、S23、S27； S15和S16不可能出现，因为船不可能停靠在无人的岸边； S9不可能出现，因为修道士不可在数量优势的野人底下把船安全地划回来； S28因为修道士也不可能在数量占优势的野人底下把船安全地划向对岸。 符合题目只有16个合理状态。,修道士和野人问题-4,20,(5) 当状态数量不是很大时，按问题的有序元组画出状态空间图； 依照状态空间图搜索求解；根据上述分析，共有16个合法状态和允许的操作， 可以划出修道士带野人问题的状态空间图，如图所示。,问题的状态空间十分庞大而不能全部以显式图的方式表达时？,梵塔问题的状态空间分析,21,直接求解的困难在于状态太大，解64阶，要把全部的状态空间图都显示出来不可能最优解长度2641=18446744073709511615 每秒2次 2900亿年 (1) 此问题是否有解? (2)若问题有解，则解的形式如何?能否找到解的规律? 先从n=2开始讨论。设其中的小金片称为A，大金片叫B，则问题的状态可以用金片穿在宝石针的编号排列情况来表示， 例如用数组(Pa，Pb)表示，这里Pa，Pb1，2，3，其中Pa代表A片处在Pa号宝石针上，Pb代表B片处在Pb号宝石针上根据9种可能状态，可以构成二阶梵塔问题的状态空间,12,21,(Pa，Pb) （小大),A B,3.3.3.2 高阶梵塔隐式,22,3.3.3.3 代价树的推进搜索（C-TSP问题）,23,城市数 路径数 7 2.5103 15 6.51011 20 1.21018 50 1.51064 100 510157 31 1.3261032 (31 1)!/2 18902 17102 15404 KM,5个城市交通问题代价树（广度优先）例子,例 城市交通问题。设有5个城市，它们之间的交通线路如图所示，图中的数字表示 两个城市之间的交通费用（代价）。用代价树的广度优先搜索，求从A市出发到E市 费用最小的交通路线。 解：,A C1 D1 E2 代价=8,下标l，2， 标出多次出现,3.4 启发式搜索,25,3.4.1 问题求解信息环境 (1) 全信息环境 Ee 运用知识和经验，设法采用最优算法，找到最佳路径，以便取得理想效果。 象棋博弈。 (2) 部分已知信息环境 Ep 充分利用已知的部分信息环境， 制定策略，设法按照最佳搜索路径取得最优解。或者设法把部分已知信息环境变为 清晰明了的全信息环境的智能搜索问题来求解。 军棋 (3) 未知信息环境 En 首先要设法变环境。为部分已知信息环境来解决。 侦察卫星、实地探险,3.4.2 启发式搜索原理,26,3.4.2 .1 启发式策略 3.4.2 .2 基本搜索特点及其局限性 (称为弱方法) 是依据某种固定规则运行的搜索，属于非启发的强力搜索, 没有表现出智能搜索的活跃性与灵活性。 基本搜索策略普遍适用于树状问题求解，控制性知识简单， 编程容易在计算机上实现。 实际搜索效率很低，故又被称为盲目搜索。一般必须知道问题的全部 状态空间，搜索效果差，求解能力弱. 启发性信息。启发性信息是指那种与具体问题求解过程有关的，并可指导搜索过程朝着最有希望方向前进的控制信息。启发性信息一般有以下三种： 有效地帮助确定扩展节点的信息； 有效的帮助决定哪些后继节点应被生成的信息： 能决定在扩展一个节点时哪些节点应从搜索树上删除的信息。,3.4.2 盲人爬山法（局部择优搜索）,27,搜索每到达一个节点后，其后继节点不是预定的或盲目的，而是在它的所有节点中，按估计函数f(x)选择最优者。（目标函数，适合函数，梯度） 优点是方法简单，要处理的资料量减少了，所以占用内存空间少、速度快。 主要只在单因素、单极值的情况下使用. 而在多极值情况下会遇到许多因难，导致找不到最佳解。 例如在二维或三维的情况下，就会遇到“多峰”问题、 “盆地”或“平台”、“山脊”问题等。,3.4.2 盲人爬山法-九宫问题举例,28,重排九宫问题。在33的方格棋盘上，分别放置标有数字1、2、3、4、 5、6、7、8共8个棋子，初始状态为So，目标状态为Sg，如图所示。 解：可使用的操作数符有4个：操作集F=fu，fd，fl，fr。 表示空格上、下、左、右移。 即只允许位于空格左、上、右、下的邻近棋子移入空格。,2 8 3 1 4 7 6 5,SO,1 2 3 8 4 7 6 5,SG,盲人爬山法举例-1,29,(解) 利用瞎子爬山法搜索策略，关键是找到一个好的目标函数。 这里把目标函数定义为 w(n)=0 其中w(n)代表节点n的格局与目标节点的格局相比，将牌位置不符的数n 总和，其中，每个将牌位置相符时，取值为0，不符取值为l；中格是空 格时(即没将牌占据)取0，不为空格取l。搜索目的设法使w(n)减少， 直到w(n)=0，就能达到目标节点的格局。 由图可见，W(SO)=3，W(SO2)= W(SO1)4，W(SO3)=5，W(SO45； 在进行第2步节点及路径选择时，遇到了一个小“平台”为W(SO2)= W(SO1)4；若选择W(SO2)= W(SO1)4，再进行瞎子爬山法搜索，于是，顺利完用了后 面的搜索，恰好在第4步寻找到SG，使得W(S31)=W(S4)=W(SG)=0。 利用瞎子爬山法搜索策略，得到搜索过程的一个搜索树示。,盲人爬山法举例-2,30,2 8 3 1 4 7 6 5,2 3 1 8 4 7 6 5,2 3 1 8 4 7 6 5,1 2 3 8 4 7 6 5,2 8 3 1 4 7 6 5,2 8 3 1 4 7 6 5,2 3 1 8 4 7 6 5,2 8 3 1 6 4 7 5,1 2 3 7 8 4 6 5,1 2 3 8 4 7 6 5,w=3,w=4,w=4,w=5,w=5,w=3,w=6,w=2,w=3,w=0=SG,1 2 3 8 4 7 6 5,SG,3.5 A 算法,31,3.5.1 估价函数 A算法 在图搜索算法中，如果能在搜索的每一步都利用估价函数 f(n)=g(n)+ h(n) 对Open表中的节点进行排序 f(n) 用来估计节点重要性的函数称为估价函数。 f(n)=g(n)+ h(n) =（实际代价+启发函数） 估价函数f(n)被定义为从初始节点S0出发，约束经过节点n到达目标节点 Sg的所有路径中最小路径代价的估计值。大小好坏由问题本身性质定。 g(n)是从初始节点S0到节点n的实际代价； 对g(n)的值，可以按指向父节点的指针，从节点n反向跟踪到初始节点S0， 得到一条从初始节点S0到节点n的最小代价路径，然后把这条路径上所有有 向边的代价相加，就得到g(n)的值。 h(n)是从节点n到目标节点Sg的最优路径的估计代价。 对h(n)的值，则需要根据问题自身的特性来确定，它体现的是问题自身 的启发性信息，因此也称h(n)也称启发函数。 h(n)=0 盲目搜索,f(n)=g(n)+ h(n),3.5.2 全局/局部择优搜索,32,1全局择优搜索 在全局择优搜索中，每当需要扩展节点时，总是从表的所有节点中选择 一个估价函数值最小的节点进行扩展。 总是从Open表的所有节点中选择一个估价函数值最小的节点进行扩展。 2局部择优搜索 在局部择优搜索中，每当需要扩展节点时，总是从刚生成的子节点中选 择一个估价函数值最小的节点进行扩展。,九宫问题估价函数 例子,33,2 8 3 1 4 7 6 5,2 3 1 8 4 7 6 5,2 3 1 8 4 7 6 5,1 2 3 8 4 7 6 5,2 8 3 1 4 7 6 5,2 8 3 1 4 7 6 5,2 3 1 8 4 7 6 5,2 8 3 1 6 4 7 5,1 2 3 7 8 4 6 5,1 2 3 8 4 7 6 5,w=3,w=3,w=0=SG,1 2 3 8 4 7 6 5,SG,f(S0)= 0+ 4,f(S1)=1+ 3,f(S2)=2+ 2,f(S3)=3+ 1,3.5.3 A*算法,34,A*算法 f*(n)=g*(n)+ h*(n) f(n)的估计f*(n)，g(n)的估计g*(n) ； h(n)的估计h*(n) 1 A*算法的可纳性 对任意一个状态空间图，当从初始节点到目标节点有路径存在时，如果搜索算法能在有限步内找到一条从初始节点到目标节点的最佳路径。 2 A*算法的最优性 A算法的搜索效率很大程度上取决于估价函数h(n)。在满足h(n)h*(n)的前提下，h(n)的值越大越好。h(n)的值越大，说明它携带的启发性信息越多,A*算法搜索时扩展的节点就越少，搜索效率就越高。 3 需要对h(n)的单调限制。 每扩展一个节点n时，都需要检查子节点和父节点的指针；如果能够保证，每当扩展一个节点时就已经找到了通往这个节点的最佳路径，就没有必要再去检查其后继节点是否已在Closed表中，原因是Closed表中的节点都已经找到了通往该节点的最佳路径。为满足这一要求，我们需要对启发函数h(n)增加单调性限制。,A*九宫问题举例 例子,35,2 8 3 1 4 7 6 5,1 2 3 7 8 4 6 5,2 3 1 8 4 7 6 5,1 2 3 8 4 7 6 5,2 8 3 1 4 7 6 5,2 3 1 8 4 7 6 5,2 8 3 1 4 7 6 5,2 3 1 8 4 7 6 5,1 2 3 8 4 7 6 5,f=6,g*=1 h*=4,f=6,g*=2 h*=2,g*=0 h*=4 f=4,g*=3 h*=1,g*=4 h*=0,f=6,3.6 与或树搜索,36,3.6.1 与或树的盲目搜索 3.6.2 与或树的启发搜索,(1) 把原始问题作为初始节点S0，并把它作为当前节点； (2) 应用分解或等价变换操作对当前节点进行扩展； (3) 为每个子节点设置指向父节点的指针； (4) 选择合适的子节点作为当前节点，反复执行第(2)步和第(3)步，在此期间需要多次调用可解标记过程或不可解标记过程，直到初始节点被标记为可解节点或不可解节点为止。 当搜索成功时，经可解标记过程标识的由初始节点及其下属的可解节点构成的子树称为解树。搜索过程中的可解标记过程与不可解标记过程都是自下而上进行的，即由子节点的可解性确定父节点的可解性； 在与或树中，除端节点和终止节点外，一个节点的可解性完全是由其子节点来决定的。对与节点，只有其所有子节点都为可解时它才为可解，只要有一个子节点不可解它就是不可解的；对或节点，只要有一个子节点可解它就是可解的，仅当所有子节点都是不可解时它才为不可解。这种由可解子节点来确定其父节点为可解节点的过程称为可解标记过程；,3.6.1.1 与或树的广度优先搜索,37,3.6.2.2 与或树的深度优先搜索,1 2 3 4 5,1 2 4 3 5,3.6.2 与或树启发搜索,38,3.6.2.1 解树的代价 (1) 若n为终止节点，则其代价h(n)0 (2) 若n为或节点，且子节点为n1，n2，则 n的代价为: h(n)minC (n，ni)+h(ni) 其中C (n，ni)是节点n到其子节点ni的边代价。 (3) 若n为与节点，则n的代价可用和代价法或最大代价法。 若用和代价法，则其计算公式为： h(n)C (n，ni)+h(ni) 若用最大代价法，则其计算公式为： h(n)maxC (n，ni)+h(ni) (4) 若n是端节点，但又不是终止节点，则n不可扩展，其代价定义为h(n) (5) 根节点的代价即为解树的代价。,按和代价： h(So)2+4+6+214 按最大代价：h(So)=2+6+2=10 按和代价： h(So)2+5+3+1=11 按最大代价：h(So)2+5+18,3.6.2.1 希望解树,39,定义 希望解树T (1) 初始节点S0在希望树T中； (2) 如果n是具有子节点nl，n2，.的或节点，则n的某个子节点ni在希望树。T中的充分必要条件是 h(n)minC (n，ni)+h(ni) (3) 如果是与节点，则n的全部子节点都在希望树T中。,最有希望成为最优解树的树，希望解树是随搜索过程不断改进,3.6.3 与或树的启发搜索步骤,(1) 把初始节点S0放人Open表中，计算h(S0)； (2) 计算希望树T； (3) 依次在Open表中取出T的端节点放人Closed表，并记该节点为n； (4) 如果节点n为终止节点，则做下列工作： 标记节点n为可解节点； 在T上应用可解标记过程，对n的先辈节点中的所有可解节点进行标记； 如果初始节点S0能够被标记为可解节点，则T就是最优解树，成功退出； 否则，从Open表中删去具有可解先辈的所有节点； 转第(2)步。 (5) 如果节点n不是终止节点，但可扩展，则做下列工作： 扩展节点n，生成n的所有子节点； 把这些子节点都放入Open表中，并为每一个子节点设置指向父节点n的指针； 计算这些子节点及其先辈节点的h值； 转第(2)步。 (6) 如果节点n不是终止节点，且不可扩展，则做下列工作： 标记节点n为不可解节点； 在T上应用不可解标记过程，对n的先辈节点中的所有不可解节点进行标记； 如果初始节点S。能够被标记为不可解节点，则问题无解，失败退出； 否则，从Open表中删去具有不可解先辈的所有节点； 转第(2)步。,Open表，Closed表是数据结构； Open表放刚生成，还没有扩展的节点 Closed表放已经扩展 ，或者要扩展的节点。,与或树的启发搜索结果例子,例子,扩展So后的与或树（2层 做了） 扩展E 后的与或树,希望树,每边代价为1,希望树,例子中，同时扩展了两层节点，实际是一层层扩展的,例子,0 0 2 2 0 0 5 0 3 2 2 2,G 2 J 6 M 2 9 7 6,H I K L N P,7,S0,8,9,3,3,A,E,3,B,D,11,C,F,7,6,0 0 2 2 3 2 2 2,G 2 J 6 7 6,H I K L,7,S0,8,9,3,3,A,E,3,B,D,11,C,F,3.7 博弈树的启发式搜索,44,双人完备信息博弈，就是两位选手对垒，轮流走步，每一方不仅知道对方已经走过的棋步，而且还能估计出对方未来的走步。对弈的结果是一方赢，另一方输；或者双方和局。这类博弈的实例有象棋、围棋等。 所谓机遇性