1、第一节第一节 知识推理的概念和类型知识推理的概念和类型第二节第二节 基本搜索策略基本搜索策略第三节第三节 启发式搜索策略启发式搜索策略第四节第四节 与与/或树图搜索或树图搜索第五节第五节 博弈树图搜索博弈树图搜索第三章第三章 知识的推理技术知识的推理技术第一节第一节 知识推理的概念和类型知识推理的概念和类型一、知识推理的概念一、知识推理的概念1、知识推理、知识推理运用知识求解问题运用知识求解问题2、知识推理技术、知识推理技术是问题从初始状态转移到目标状态的方法和途径是问题从初始状态转移到目标状态的方法和途径3、知识推理技术的研究目标、知识推理技术的研究目标寻找从初始状态沿着最优或最经济的寻找从
2、初始状态沿着最优或最经济的途径转移到目标状态的智能操作序列，实现问题求解过程的计算机化途径转移到目标状态的智能操作序列，实现问题求解过程的计算机化二、知识推理的分类二、知识推理的分类1、根据知识表达方式、根据知识表达方式图搜索法图搜索法如广度优先法、深度优先法如广度优先法、深度优先法逻辑论证法逻辑论证法如王浩命题逻辑算法、鲁滨逊谓词逻辑算法如王浩命题逻辑算法、鲁滨逊谓词逻辑算法2、根据推理过程的完备性、根据推理过程的完备性推理算法推理算法完备的推理过程，如广度优先法完备的推理过程，如广度优先法推理步骤推理步骤不完备的推理过程，如深度优先法不完备的推理过程，如深度优先法3、根据推理过程是否运用启
3、发性知识、根据推理过程是否运用启发性知识启发推理启发推理运用启发性知识，提高搜索效率，如全局择优法、局部运用启发性知识，提高搜索效率，如全局择优法、局部择优法择优法非启发推理非启发推理效率较低，如广度优先法效率较低，如广度优先法第一节第一节 知识推理的概念和类型知识推理的概念和类型三、符号模式匹配三、符号模式匹配1、概念、概念符号模式符号模式用于知识表达的各种符号表达式用于知识表达的各种符号表达式匹配匹配比较和选配比较和选配符号模式匹配符号模式匹配将一个符号表达式与另一个符号表达式进行比较和将一个符号表达式与另一个符号表达式进行比较和选配，判断它们是否可以相互匹配选配，判断它们是否可以相互匹配
4、事实模式事实模式目标模式目标模式目标模式的各分量都可被事实模式匹配，称目标模式可目标模式的各分量都可被事实模式匹配，称目标模式可匹配匹配第一节第一节 知识推理的概念和类型知识推理的概念和类型2、示例、示例例例1设有谓词公式设有谓词公式P1:MARRIAGE(john,mary)MALE(john)FEMALE(mary)P2:MARRIAGE(john,mary)MALE(john)检查检查P1、P2是否能够匹配是否能够匹配例例2含有变量的谓词公式含有变量的谓词公式P1:FATHER(joe,john)MAN(joe)P2:FATHER(x,y)MAN(x)考察考察P1、P2的匹配过程的匹配过
5、程第一节第一节 知识推理的概念和类型知识推理的概念和类型例例3设一个产生式系统包含一条如下规则设一个产生式系统包含一条如下规则IF(animal)is a(type)(child)THEN(child)is a(type)事实库中有如下事实：事实库中有如下事实：(1)bozo is a cheetah(2)bozo is a parent of billy(3)bozo is a parent of sugar(4)sweekums is a penguin(5)king is a parent of rex检查规则的前提部分能否被事实库匹配检查规则的前提部分能否被事实库匹配第一节第一节 知识
6、推理的概念和类型知识推理的概念和类型四、图搜索的基本概念四、图搜索的基本概念1、状态图搜索树、状态图搜索树巡回推销员问题巡回推销员问题假设一个推销员要到假设一个推销员要到4个城市去访问，然后回家，不个城市去访问，然后回家，不走回头路。问题是寻找一条最短的路径，使得推销员访问过每个城市后走回头路。问题是寻找一条最短的路径，使得推销员访问过每个城市后回到出发地。回到出发地。ABCD47106105第一节第一节 知识推理的概念和类型知识推理的概念和类型AABACADABCABDACBACDADBADCABCDABDCACBDACDBADBCADCBABCDA26ABDCA25ACBDA33ACDBE
7、25ADBCA33ADCBA2646107107510555101077106104462、存储方式、存储方式显式存储显式存储存储全部状态空间存储全部状态空间隐式存储隐式存储只存储与问题有关的部分知识只存储与问题有关的部分知识3、隐式图搜索方法、隐式图搜索方法运用叙述性知识，给出问题的部分状态描述运用叙述性知识，给出问题的部分状态描述运用过程性知识，给出生成器函数运用过程性知识，给出生成器函数G(x)父节点生成子节点的规父节点生成子节点的规则则运用控制性知识，给出评价函数运用控制性知识，给出评价函数 E(x)评价新生成的节点，控制评价新生成的节点，控制继续搜索的方向继续搜索的方向第一节第一节
8、知识推理的概念和类型知识推理的概念和类型4、隐式图搜索的基本过程、隐式图搜索的基本过程（1）给定初始状态）给定初始状态S0（2）用生成器函数）用生成器函数G(x)，由，由S0出发生成其子节点，检查是否出现目出发生成其子节点，检查是否出现目标状态标状态Sg，若出现，则成功，若出现，则成功（3）若未出现，继续搜索，用评价）若未出现，继续搜索，用评价E(x)对各子节点进行评价，选取对各子节点进行评价，选取最有希望的节点，再用最有希望的节点，再用G(x)生成其子节点，再检查是否出现生成其子节点，再检查是否出现Sg（4）如此逐步搜索，直到找到）如此逐步搜索，直到找到Sg为止为止第一节第一节 知识推理的概
9、念和类型知识推理的概念和类型5、搜索过程的完备性、搜索过程的完备性搜索过程是完备的搜索过程是完备的给定一类可解的状态空间给定一类可解的状态空间和一个搜索和一个搜索过程过程A，如对任一，如对任一S0S，搜索过程，搜索过程A总可以发现一条从总可以发现一条从S0到达到达Sg G的通路，则称搜索过程的通路，则称搜索过程A对问题类对问题类是完备的。是完备的。搜索过程是可采纳的搜索过程是可采纳的若若A找到的总是最佳解，则称它是可采纳的，找到的总是最佳解，则称它是可采纳的，记为记为A*6、启发式与非启发式搜索过程、启发式与非启发式搜索过程如果在估计函数如果在估计函数E(x)中包含有关于待求解问题的某些先验知
10、识，如解中包含有关于待求解问题的某些先验知识，如解的特性、解的分布规律等，那么搜索过程就能有选择地朝目标节点有的特性、解的分布规律等，那么搜索过程就能有选择地朝目标节点有效地推进，这时就称该搜索过程效地推进，这时就称该搜索过程A为关于问题类为关于问题类的启发式搜的启发式搜索过程，反之称为非启发式搜索过程索过程，反之称为非启发式搜索过程第一节第一节 知识推理的概念和类型知识推理的概念和类型第二节第二节 基本搜索策略基本搜索策略一、广度优先搜索法一、广度优先搜索法1、概念、概念由上到下，逐级生成由上到下，逐级生成从左到右，横扫各个节点从左到右，横扫各个节点评价函数评价函数E(x)=d(x)节点节点
11、x的深度的深度是搜索算法，并且是可采纳的是搜索算法，并且是可采纳的第二节第二节 基本搜索策略基本搜索策略2、流程、流程启动启动S0放入放入OPEN表表OPEN表表=NIL取取OPEN表中最前的节点表中最前的节点N放入放入CLOSED表冠以顺序表冠以顺序nN=SgN可扩展可扩展扩展扩展N,将其子节点依次放入将其子节点依次放入OPEN表末尾表末尾,配以指向配以指向N的返回指针的返回指针失败失败成功成功是是否否是是否否是是否否3、示例、示例重排九宫问题。在重排九宫问题。在3*3的方格棋盘上放置的方格棋盘上放置18八个数字，八个数字，其中有一个方格是空的。只允许把空格上、下、左、右的纸牌移入空其中有一
12、个方格是空的。只允许把空格上、下、左、右的纸牌移入空格，而空格移至该纸牌原来的位置。要求寻找从初始状态到目标状态格，而空格移至该纸牌原来的位置。要求寻找从初始状态到目标状态的最短途径。的最短途径。2 8 31 47 6 51 2 38 47 6 5初始状态初始状态目标状态目标状态解：定义生成器函数解：定义生成器函数G(x)纸牌移入空格的次序是从空格的左边开始，纸牌移入空格的次序是从空格的左边开始，顺时针方向移动，不允许斜向移动，不允许返回顺时针方向移动，不允许斜向移动，不允许返回第二节第二节 基本搜索策略基本搜索策略第二节第二节 基本搜索策略基本搜索策略2 8 31 47 6 52 8 3 1
13、 47 6 52 31 8 47 6 52 8 31 4 7 6 52 8 31 6 47 5 8 32 1 47 6 52 8 37 1 4 6 5 2 31 8 47 6 52 3 1 8 47 6 52 8 1 4 37 6 52 8 31 4 57 6 2 8 31 6 4 7 52 8 31 6 47 5 8 32 1 47 6 52 8 37 1 46 51 2 3 8 47 6 52 3 4 1 8 7 6 52 8 1 4 37 6 52 8 31 4 5 7 6 2 8 3 6 41 7 52 8 31 6 7 5 48 3 2 1 47 6 58 1 32 47 6 52
14、8 37 46 1 52 8 37 1 46 5 1 2 38 47 6 5123456789101112131415161718192021222324250第二节第二节 基本搜索策略基本搜索策略二、深度优先搜索法二、深度优先搜索法1、概念、概念由上到下，逐级生成由上到下，逐级生成同一级节点，最晚生成，优先扩展同一级节点，最晚生成，优先扩展评价函数评价函数E(x)=N(x)节点节点x生成的先后顺序生成的先后顺序不是搜索算法，是搜索步骤不是搜索算法，是搜索步骤目标节点在最晚分支中，效率较高目标节点在最晚分支中，效率较高第二节第二节 基本搜索策略基本搜索策略2、流程、流程启动启动S0放入放入OP
15、EN表表OPEN表表=NIL取取OPEN表中最后的节点表中最后的节点N放入放入CLOSED表冠以顺序表冠以顺序nN=SgN可扩展可扩展扩展扩展N,将其子节点依次放入将其子节点依次放入OPEN表末尾表末尾,配以指向配以指向N的返回指针的返回指针失败失败成功成功是是否否是是否否是是否否3、示例、示例重排九宫问题。在重排九宫问题。在3*3的方格棋盘上放置的方格棋盘上放置18八个数字，八个数字，其中有一个方格是空的。只允许把空格上、下、左、右的纸牌移入空其中有一个方格是空的。只允许把空格上、下、左、右的纸牌移入空格，而空格移至该纸牌原来的位置。要求寻找从初始状态到目标状态格，而空格移至该纸牌原来的位置
16、。要求寻找从初始状态到目标状态的最短途径。的最短途径。2 8 31 47 6 51 2 38 47 6 5初始状态初始状态目标状态目标状态解：定义生成器函数解：定义生成器函数纸牌移入空格的次序是从空格的左边开始，顺纸牌移入空格的次序是从空格的左边开始，顺时针方向移动，不允许斜向移动，不允许返回时针方向移动，不允许斜向移动，不允许返回第二节第二节 基本搜索策略基本搜索策略2 8 31 47 6 52 8 3 1 47 6 52 31 8 47 6 52 8 31 4 7 6 52 8 31 6 47 52 8 31 6 4 7 52 8 31 6 47 5 2 8 31 6 7 5 412302
17、 8 31 67 5 42 8 1 6 37 5 442 81 6 37 5 45第二节第二节 基本搜索策略基本搜索策略三、有界深度优先搜索法三、有界深度优先搜索法1、概念、概念深度优先搜索法的缺陷深度优先搜索法的缺陷引入搜索深度限制：引入搜索深度限制：ddmdm dg，一定可以找到，一定可以找到Sg若若dm选取不合适选取不合适dm dg，搜索效率降低，搜索效率降低2、流程、流程启动启动S0放入放入OPEN表，表，d(s0)=0OPEN表表=NIL取取OPEN表中最后的节点表中最后的节点N放入放入CLOSED表冠以顺序表冠以顺序nN=SgN可扩展可扩展扩展扩展N,将其子节点依次放入将其子节点依
18、次放入OPEN表末尾表末尾,配以指向配以指向N的返回指针，的返回指针，d(N)=d(N)+1失败失败成功成功是是否否是是否否是是否否d(N)=dm否否是是3、示例、示例重排九宫问题。设深度限制重排九宫问题。设深度限制dm=4，用有界深度优先搜索，用有界深度优先搜索法求解法求解2 8 31 47 6 51 2 38 47 6 5初始状态初始状态目标状态目标状态解：定义生成器函数解：定义生成器函数纸牌移入空格的次序是从空格的左边开始，顺纸牌移入空格的次序是从空格的左边开始，顺时针方向移动，不允许斜向移动，不允许返回时针方向移动，不允许斜向移动，不允许返回第二节第二节 基本搜索策略基本搜索策略2 8
19、 31 47 6 52 8 3 1 47 6 52 31 8 47 6 52 8 31 4 7 6 52 8 31 6 47 52 8 31 6 4 7 52 8 31 6 47 5 2 8 31 6 7 5 4162302 8 31 67 5 42 8 1 6 37 5 4542 8 3 6 41 7 57 8 32 6 41 7 52 8 36 41 7 598102 8 1 4 37 6 52 8 31 4 57 6 2 8 31 4 57 61511122 8 31 4 5 7 62 8 31 57 4 614132 81 4 37 6 516 2 81 4 37 6 52 4 81
20、37 6 51817 2 31 8 47 6 52 3 1 8 47 6 5 2 3 41 8 7 6 52420212 3 41 87 6 52 3 41 8 57 6 23221 2 3 8 47 6 5251 2 38 47 6 51 2 37 8 4 6 5272619第二节第二节 基本搜索策略基本搜索策略4、变界深度优先搜索法、变界深度优先搜索法将深度限制的固定值改为可变值，先取较小的将深度限制的固定值改为可变值，先取较小的dm，若未搜索到目标节，若未搜索到目标节点，则加大点，则加大dm值，再搜索，逐步加大值，再搜索，逐步加大dm值，逐步搜索，值，逐步搜索，当当dm=dg时，时，一定
21、可以搜索到目标节点一定可以搜索到目标节点可找到目标节点，但不一定是最短路径可找到目标节点，但不一定是最短路径再改进：再改进：d（Sgm)=min 1 i n(d（Sgi)改进后成为搜索算法，而且是可采纳的改进后成为搜索算法，而且是可采纳的第二节第二节 基本搜索策略基本搜索策略四、代价驱动搜索法四、代价驱动搜索法1、概念、概念代价代价从一个节点经过一条支路，转移到另一个节点所需要支付的从一个节点经过一条支路，转移到另一个节点所需要支付的时间或费用等时间或费用等代价树代价树在问题树上标明代价所形成的赋值问题树在问题树上标明代价所形成的赋值问题树代价驱动搜索法代价驱动搜索法根据根据“代价最小代价最小
22、”原则，优选最小代价的搜索路原则，优选最小代价的搜索路径径第二节第二节 基本搜索策略基本搜索策略2、代价驱动广度优先搜索法、代价驱动广度优先搜索法在广度优先法的基础上，令在广度优先法的基础上，令E(x)=C(x)从初始节点到节点从初始节点到节点x所支付所支付的代价的代价代价最小优先扩展代价最小优先扩展择优比较在所有新生成的节点间进行择优比较在所有新生成的节点间进行流程：流程：启动启动S0放入放入OPEN表，表，C(S0)=0OPEN表表=NIL取取OPEN表中最前的节点表中最前的节点N放入放入CLOSED表冠以顺序表冠以顺序nN=SgN可扩展可扩展扩展扩展N，将其子节点依次放入，将其子节点依次
23、放入OPEN表，表，配以指向配以指向N的返回指针，对的返回指针，对OPEN表表中所有节点按中所有节点按C(x)的大小排序（小在前）的大小排序（小在前）失败失败成功成功是是否否是是是是否否否否示例示例最小费用路线问题。设各城市之间的交通线路如图，出发地最小费用路线问题。设各城市之间的交通线路如图，出发地为为A城，目的地为城，目的地为E城，各支路的交通费用如图，寻找从城，各支路的交通费用如图，寻找从A城到城到E城的城的最小费用交通路线最小费用交通路线ABDEC321054347解：定义生成器函数解：定义生成器函数G(x)节点节点x的子节点取交通图中与的子节点取交通图中与x有有直接联系的节点（但其父
24、节点除外）直接联系的节点（但其父节点除外）第二节第二节 基本搜索策略基本搜索策略ABDEC321054347ABCDCDDEE273434105CEE4510BDE3410DE54BE45BCE445第二节第二节 基本搜索策略基本搜索策略3、代价驱动深度优先搜索法、代价驱动深度优先搜索法类似深度优先搜索法，择优比较在当前节点的子节点间进行类似深度优先搜索法，择优比较在当前节点的子节点间进行代价最小优先扩展代价最小优先扩展不一定能找到最优解不一定能找到最优解为避免进入无穷分支，可设置代价限制，当为避免进入无穷分支，可设置代价限制，当C(N)Cm时，转其他路径时，转其他路径流程：流程：启动启动S0
25、放入放入OPEN表，表，C(S0)=0OPEN表表=NIL取取OPEN表中最前的节点表中最前的节点N放入放入CLOSED表冠以顺序表冠以顺序nN=SgN可扩展可扩展扩展扩展N，将其子节点配以指向，将其子节点配以指向N的返回指针，的返回指针，并将子节点按并将子节点按C(x)的大小排序（小在前）的大小排序（小在前）依次放入依次放入OPEN表表失败失败成功成功是是否否是是是是否否否否ABDEC321054347ABCDCDDEE273434105示例示例第三节第三节 启发式搜索启发式搜索一、局部择优搜索法一、局部择优搜索法1、概念、概念启发式搜索方法，是深度优先搜索法的改进启发式搜索方法，是深度优先
26、搜索法的改进启发性信息包含在启发性信息包含在E(x)中中当一个节点被扩展时后，用当一个节点被扩展时后，用E(x)对它的每一个子节点进行计算，从中对它的每一个子节点进行计算，从中找出找出E(x)最小的那个节点，作为下一次要扩展的节点最小的那个节点，作为下一次要扩展的节点是小范围的局部择优，又称是小范围的局部择优，又称“瞎子爬山法瞎子爬山法”深度优先搜索法和代价树的深度优先搜索法是其特例深度优先搜索法和代价树的深度优先搜索法是其特例优点优点方法简便，搜索速度快方法简便，搜索速度快缺点缺点只适合单极值问题，是不完备的搜索步骤只适合单极值问题，是不完备的搜索步骤2、流程、流程启动启动S0放入放入OPE
27、N表表OPEN表表=NIL取取OPEN表中最前的节点表中最前的节点N放入放入CLOSED表冠以顺序表冠以顺序nN=SgN可扩展可扩展扩展扩展N，计算每个子节点的，计算每个子节点的E(x)，按按 E(x)大小将子节点依次放入大小将子节点依次放入OPEN表前面，表前面，小的在前，为每个子节点配以指向小的在前，为每个子节点配以指向N的返回指针的返回指针失败失败成功成功是是否否是是否否是是否否第三节第三节 启发式搜索启发式搜索3、示例、示例重排九宫问题。用局部择优搜索法求解重排九宫问题。用局部择优搜索法求解2 8 31 6 47 51 2 38 47 6 5初始状态初始状态目标状态目标状态解：解：定义
28、生成器函数定义生成器函数纸牌移入空格的次序是从空格的左边开始，顺时针纸牌移入空格的次序是从空格的左边开始，顺时针方向移动，不允许斜向移动，不允许返回方向移动，不允许斜向移动，不允许返回定义评价函数定义评价函数E(x)=h(x)，节点，节点x的格局与目标格局不符合的牌数的格局与目标格局不符合的牌数第三节第三节 启发式搜索启发式搜索2 8 31 6 47 52 8 31 6 4 7 52 8 3 1 4 7 6 52 8 31 6 47 5 54352 8 3 1 47 6 52 3 1 8 4 7 6 52 8 31 4 7 6 5433 8 32 1 47 6 52 8 3 7 1 4 6 5
29、438 32 1 47 6 538 3 2 1 47 6 58 1 3 2 4 7 6 5348 1 3 2 47 6 5443 1 38 2 47 6 58 1 3 7 2 4 6 5421028 1 3 2 4 7 6 538 1 3 2 4 7 6 58 1 3 2 6 4 7 51 38 2 47 6 51 3 8 2 47 6 51 2 38 47 6 5第三节第三节 启发式搜索启发式搜索二、全局择优搜索法二、全局择优搜索法1、概念、概念启发式搜索方法，弥补了局部优先搜索法的局限性启发式搜索方法，弥补了局部优先搜索法的局限性择优比较不仅仅在新生成的子节点中进行，而是在所有子节点中进行
30、择优比较不仅仅在新生成的子节点中进行，而是在所有子节点中进行又称又称“最好优先搜索法最好优先搜索法”广度优先搜索法和代价驱动的广度优先搜索法是其特例广度优先搜索法和代价驱动的广度优先搜索法是其特例2、流程、流程启动启动S0放入放入OPEN表表OPEN表表=NIL取取OPEN表中最前的节点表中最前的节点N放入放入CLOSED表冠以顺序表冠以顺序nN=SgN可扩展可扩展扩展扩展N，为每个子节点配以指向，为每个子节点配以指向N的返回指针，的返回指针，计算每个子节点的计算每个子节点的E(x)，将子节点依次放入，将子节点依次放入OPEN表，表，对对OPEN表中全部节点按表中全部节点按E(x)从小到大排序
31、，小的在前，从小到大排序，小的在前，失败失败成功成功是是否否是是否否是是否否第三节第三节 启发式搜索启发式搜索第三节第三节 启发式搜索启发式搜索3、评价函数的启发能力、评价函数的启发能力E(x)的启发能力的启发能力E(x)所包含的启发信息量的大小所包含的启发信息量的大小E(x)=vg(x)+wh(x)g(x)已付出的价值，是历史信息已付出的价值，是历史信息h(x)将要付出的价值，是启发信息将要付出的价值，是启发信息w，v强调纵向深入搜索，启发性强调纵向深入搜索，启发性，完备性，完备性v，w强调横向扫描，完备性强调横向扫描，完备性，启发性，启发性4、示例、示例重排九宫问题。用全局择优搜索法求解重
32、排九宫问题。用全局择优搜索法求解2 8 31 47 6 51 2 38 47 6 5初始状态初始状态目标状态目标状态解：解：定义生成器函数：纸牌移入空格的次序是从空格的左边开始，顺时针方定义生成器函数：纸牌移入空格的次序是从空格的左边开始，顺时针方向移动，不允许斜向移动，不允许返回向移动，不允许斜向移动，不允许返回定义评价函数：定义评价函数：E(x)=d(x)+h(x)d(x)节点节点x的深度的深度h(x)节点节点x的格局与目标格局不符合的牌数的格局与目标格局不符合的牌数第三节第三节 启发式搜索启发式搜索2 8 31 47 6 52 8 3 1 47 6 52 31 8 47 6 52 8 3
33、1 4 7 6 52 8 31 6 47 553544 8 32 1 47 6 52 8 37 1 4 6 556 2 31 8 47 6 52 3 1 8 4 7 6 5461 2 3 8 47 6 541 2 38 47 6 51 2 3 7 8 4 6 546第四节第四节 与与/或树图搜索或树图搜索一、与一、与/或树图搜索法的概念或树图搜索法的概念根节点根节点初试问题状态初试问题状态有解的叶节点有解的叶节点终止节点终止节点可解节点：可解节点：终止节点是可解节点终止节点是可解节点当且仅当其子节点中至少有一个是可解节点时，当且仅当其子节点中至少有一个是可解节点时，“或或”节点是可解节节点是可
34、解节点点当且仅当其子节点都是可解节点时，当且仅当其子节点都是可解节点时，“与与”节点是可解节点节点是可解节点不可解节点不可解节点没有子节点的非终止节点是不可解节点没有子节点的非终止节点是不可解节点当且仅当其全部子节点都是不可解节点时，当且仅当其全部子节点都是不可解节点时，“或或”节点是不可解节点节点是不可解节点当且仅当其子节点中至少有一个是不可解节点时，当且仅当其子节点中至少有一个是不可解节点时，“与与”节点是不可节点是不可解节点解节点第四节第四节 与与/或树图搜索或树图搜索可解过程可解过程标记可解节点（标记可解节点（）的过程，若根节点可解，搜索成功）的过程，若根节点可解，搜索成功不可解过程不
35、可解过程标记不可解节点（标记不可解节点（）的过程，若根节点不可解，搜）的过程，若根节点不可解，搜索失败索失败解树解树由导致根节点为可解节点的有关可解节点及由导致根节点为可解节点的有关可解节点及“树枝树枝”所组成所组成的子树的子树第四节第四节 与与/或树图搜索或树图搜索二、与二、与/或树图搜索法的流程或树图搜索法的流程（1）将初始问题设置为根节点）将初始问题设置为根节点（2）扩展初始节点，扩展深度可以大于）扩展初始节点，扩展深度可以大于1（3）设置返回指针）设置返回指针（4）反复执行（）反复执行（2）、（）、（3），直到：），直到：根节点可以标记为可解节点，搜索成功根节点可以标记为可解节点，搜索
36、成功根节点可以标记为不可解节点，搜索失败根节点可以标记为不可解节点，搜索失败第四节第四节 与与/或树图搜索或树图搜索三、解树代价的计算三、解树代价的计算1、“与与”节点代价计算法节点代价计算法（1）最大代价法）最大代价法)(),(max)(1iinixhxxcxh（2）代价和法）代价和法niiixhxxcxh1)(),()(x h(x)x1h(x1)x2h(x2)x3h(x3)c(x,x1)c(x,x3)c(x,x2)第四节第四节 与与/或树图搜索或树图搜索2、“或或”节点代价计算法节点代价计算法)(),(min)(1iinixhxxcxhx h(x)x1h(x1)x2h(x2)x3h(x3)
37、c(x,x1)c(x,x3)c(x,x2)3、叶节点代价的定义、叶节点代价的定义可解叶节点（终止节点）可解叶节点（终止节点）h(x)=0不可解叶节点不可解叶节点h(x)=4、解树的总代价、解树的总代价从终止节点出发，通过解树，逐级回溯，向从终止节点出发，通过解树，逐级回溯，向上计算根节点的代价上计算根节点的代价第四节第四节 与与/或树图搜索或树图搜索5、示例、示例设问题的与设问题的与/或树如图所示，计算解树的总代价或树如图所示，计算解树的总代价4456244324573Sa1a2a3a4a5a6b1b2b3b4b5第四节第四节 与与/或树图搜索或树图搜索四、与四、与/或树最好优先搜索法或树最好
38、优先搜索法1、概念、概念引入启发信息估计节点引入启发信息估计节点x的代价的代价h(x)由由h(x)估计最优解树的近根部分估计最优解树的近根部分希望解树希望解树0 0希望解树的定义：希望解树的定义：初始节点在希望解树中初始节点在希望解树中 若或节点若或节点x在希望解树中，则其子节点集中，具有最小代价的子节点在希望解树中，则其子节点集中，具有最小代价的子节点应在希望解树中应在希望解树中)(),(min1iinixhxxc若与节点若与节点x在希望解树中，则其子节点集中在希望解树中，则其子节点集中具有最大代价的子节点应在希望解树中（最大代价法）具有最大代价的子节点应在希望解树中（最大代价法）其全部子节
39、点均在希望解树中（代价和法）其全部子节点均在希望解树中（代价和法）)(),(max1iinixhxxc2、流程、流程启动启动S0放入放入OPEN表，估计表，估计h(S0)从从OPEN表依次选出表依次选出0 0的端节点的端节点N放入放入CLOSED表，顺序编号表，顺序编号N是终止节点是终止节点N可扩展可扩展否否由由h(x)估计估计0 0标记标记N为不可解节点，为不可解节点，对对0 0应用不可解过程应用不可解过程否否S0不可解不可解从从OPEN表中除去有表中除去有不可解父节点的节点不可解父节点的节点失败失败标记标记N为可解节点，为可解节点，对对0 0应用可解过程应用可解过程S0可解可解从从OPEN
40、表中除去有表中除去有可解父节点的节点可解父节点的节点成功成功是是是是否否否否扩展扩展N，子节点依次放入，子节点依次放入OPEN表，表，配以指向配以指向N的返回指针，的返回指针，估计子节点及其先辈节点的估计子节点及其先辈节点的h(x)是是是是第四节第四节 与与/或树图搜索或树图搜索3、示例、示例应用最好优先搜索法求与应用最好优先搜索法求与/或树的最小代价树。设每条树枝的代或树的最小代价树。设每条树枝的代价均为价均为1，每次扩展深度为，每次扩展深度为2解：解：SABCDEF3323322276700222630052293887 129第五节第五节 博弈树图搜索博弈树图搜索一、概念一、概念1、二人
41、零和、二人零和、全信息、非偶然全信息、非偶然0211122122*1*222211211*2*11,),(maxmin(),(,),(maxmin(),(DdDdddddDdDddddd2、博弈树、博弈树双方轮流扩展，是特殊的与双方轮流扩展，是特殊的与/或树或树第五节第五节 博弈树图搜索博弈树图搜索二、特点二、特点1、“与与”节点、节点、“或或”节点逐级交替出现节点逐级交替出现2、从我方看，所有敌方的节点都是、从我方看，所有敌方的节点都是“与与”节点节点3、从我方看，所有我方的节点都是、从我方看，所有我方的节点都是“或或”节点节点4、所有能使我方获胜的终局，其相应的端节点都是可解节点，得分为正
42、、所有能使我方获胜的终局，其相应的端节点都是可解节点，得分为正所有使敌方获胜的终局，对我方而言，是不可解节点，得分为负所有使敌方获胜的终局，对我方而言，是不可解节点，得分为负5、先走一方的初始状态相应于根节点、先走一方的初始状态相应于根节点第五节第五节 博弈树图搜索博弈树图搜索三、极大极小分析法三、极大极小分析法1、基本思想、基本思想评价函数：评价函数：E(x)=1(x)双方根据双方根据“极大、极小极大、极小”原则，选取对自己最有利的棋步原则，选取对自己最有利的棋步我方最优：我方最优：maxE(x)扩展扩展“或或”节点节点敌方最优：敌方最优：minE(x)扩展扩展“与与”节点节点从端节点的得分
43、估计值出发，倒推根节点的得分，选取我方得分极大，敌从端节点的得分估计值出发，倒推根节点的得分，选取我方得分极大，敌方得分极小的最优棋步，逐级搜索，求解博弈问题方得分极小的最优棋步，逐级搜索，求解博弈问题第五节第五节 博弈树图搜索博弈树图搜索2、示例、示例maxmaxmaxminmin2931-1-13-168203-57 4-2 6-1-18-1 032-1-16-10-5-2-1-1-1260-1-12-12第五节第五节 博弈树图搜索博弈树图搜索3、实际应用、实际应用 以一定的深度生成博弈树，应用启发性信息估计各端节点的估以一定的深度生成博弈树，应用启发性信息估计各端节点的估值值 用极大极小
44、分析法倒推根节点的估值，选取当前的最优棋步用极大极小分析法倒推根节点的估值，选取当前的最优棋步 以当前最优棋步为初始状态，按一定的深度生成搜索树，得下以当前最优棋步为初始状态，按一定的深度生成搜索树，得下一个最优棋步一个最优棋步 逐级搜索，达到终局为止逐级搜索，达到终局为止第五节第五节 博弈树图搜索博弈树图搜索示例示例一字棋博弈，用极大极小分析法求双方的最优棋步一字棋博弈，用极大极小分析法求双方的最优棋步解：扩展深度为解：扩展深度为2，估值函数，估值函数h(x)=我方路数我方路数对方路数对方路数2-1=13-2=12-2=02-3=-12-2=03-2=13-1=21-2=-11-3=-22-
45、3=-12-2=01-1=0-11-21第五节第五节 博弈树图搜索博弈树图搜索3、“”剪枝法剪枝法2722SABCDEF11=2第五节第五节 博弈树图搜索博弈树图搜索（1）、值的定义值的定义或节点或节点x x的的值值xx倒推估计值倒推估计值b(xb(x)的下界的下界,b(x,b(x)与节点与节点y y的的值值yy倒推估计值倒推估计值b(yb(y)的上界的上界,b(y,b(y)（2 2）规则）规则剪枝剪枝若与节点的若与节点的值，不能使其父节点的值，不能使其父节点的值升高，则该值升高，则该与节点以下的分枝可以剪掉与节点以下的分枝可以剪掉煎枝煎枝若或节点的若或节点的值，不能使其父节点的值，不能使其父节点的值降低，则该值降低，则该或节点以下的分枝可以剪掉或节点以下的分枝可以剪掉第五节第五节 博弈树图搜索博弈树图搜索（3）示例）示例2931-1-13-168203-57 4-2 6-1-18-1 0321602-1=226=220-5=00=2剪剪剪剪剪剪剪剪剪剪剪剪
