人工智能与专家系统第三章(同名436)课件

第一节知识推理的概念和类型第二节基本搜索策略第三节启发式搜索策略第四节与/或树图搜索第五节博弈树图搜索第三章知识的推理技术第一节知识推理的概念和类型第三章知识的推理技术1第一节知识推理的概念和类型一、知识推理的概念1、知识推理——运用知识求解问题2、知识推理技术——是问题从初始状态转移到目标状态的方法和途径3、知识推理技术的研究目标——寻找从初始状态沿着最优或最经济的途径转移到目标状态的智能操作序列，实现问题求解过程的计算机化第一节知识推理的概念和类型一、知识推理的概念2二、知识推理的分类1、根据知识表达方式图搜索法——如广度优先法、深度优先法逻辑论证法——如王浩命题逻辑算法、鲁滨逊谓词逻辑算法2、根据推理过程的完备性推理算法——完备的推理过程，如广度优先法推理步骤——不完备的推理过程，如深度优先法3、根据推理过程是否运用启发性知识启发推理——运用启发性知识，提高搜索效率，如全局择优法、局部择优法非启发推理——效率较低，如广度优先法第一节知识推理的概念和类型二、知识推理的分类第一节知识推理的概念和类型3三、符号模式匹配1、概念符号模式——用于知识表达的各种符号表达式匹配——比较和选配符号模式匹配——将一个符号表达式与另一个符号表达式进行比较和选配，判断它们是否可以相互匹配事实模式目标模式——目标模式的各分量都可被事实模式匹配，称目标模式可匹配第一节知识推理的概念和类型三、符号模式匹配第一节知识推理的概念和类型42、示例例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的匹配过程第一节知识推理的概念和类型2、示例第一节知识推理的概念和类型5例3——设一个产生式系统包含一条如下规则IF((>animal)isa(>type))∧((<animal)isaparentof(>child))THEN(<child)isa(<type)事实库中有如下事实：bozoisacheetahbozoisaparentofbillybozoisaparentofsugarsweekumsisapenguinkingisaparentofrex检查规则的前提部分能否被事实库匹配第一节知识推理的概念和类型例3——设一个产生式系统包含一条如下规则第一节知识推理的概6四、图搜索的基本概念1、状态图搜索树巡回推销员问题——假设一个推销员要到4个城市去访问，然后回家，不走回头路。问题是寻找一条最短的路径，使得推销员访问过每个城市后回到出发地。ABCD47106105第一节知识推理的概念和类型AABACADABCABDACBACDADBADCABCDABDCACBDACDBADBCADCBABCDA26ABDCA25ACBDA33ACDBE25ADBCA33ADCBA264610710751055510107710610446四、图搜索的基本概念ABCD47106105第一节知识推理72、存储方式显式存储——存储全部状态空间隐式存储——只存储与问题有关的部分知识3、隐式图搜索方法运用叙述性知识，给出问题的部分状态描述运用过程性知识，给出生成器函数G(x)——父节点生成子节点的规则运用控制性知识，给出评价函数E(x)——评价新生成的节点，控制继续搜索的方向第一节知识推理的概念和类型2、存储方式第一节知识推理的概念和类型84、隐式图搜索的基本过程（1）给定初始状态S0（2）用生成器函数G(x)，由S0出发生成其子节点，检查是否出现目标状态Sg，若出现，则成功（3）若未出现，继续搜索，用评价E(x)对各子节点进行评价，选取最有希望的节点，再用G(x)生成其子节点，再检查是否出现Sg（4）如此逐步搜索，直到找到Sg为止第一节知识推理的概念和类型4、隐式图搜索的基本过程第一节知识推理的概念和类型95、搜索过程的完备性搜索过程是完备的——给定一类可解的状态空间<S,F,G>和一个搜索过程A，如对任一S0∈S，搜索过程A总可以发现一条从S0到达Sg∈G的通路，则称搜索过程A对问题类<S,F,G>是完备的。搜索过程是可采纳的——若A找到的总是最佳解，则称它是可采纳的，记为A*6、启发式与非启发式搜索过程如果在估计函数E(x)中包含有关于待求解问题的某些先验知识，如解的特性、解的分布规律等，那么搜索过程就能有选择地朝目标节点有效地推进，这时就称该搜索过程A为关于问题类<S,F,G>的启发式搜索过程，反之称为非启发式搜索过程第一节知识推理的概念和类型5、搜索过程的完备性第一节知识推理的概念和类型10第二节基本搜索策略一、广度优先搜索法1、概念由上到下，逐级生成从左到右，横扫各个节点评价函数E(x)=d(x)——节点x的深度是搜索算法，并且是可采纳的第二节基本搜索策略一、广度优先搜索法11第二节基本搜索策略2、流程启动S0放入OPEN表OPEN表=NIL取OPEN表中最前的节点N放入CLOSED表冠以顺序nN=SgN可扩展扩展N,将其子节点依次放入OPEN表末尾,配以指向N的返回指针失败成功是否是否是否第二节基本搜索策略2、流程启动S0放入OPEN表OPEN表123、示例——重排九宫问题。在3*3的方格棋盘上放置1~8八个数字，其中有一个方格是空的。只允许把空格上、下、左、右的纸牌移入空格，而空格移至该纸牌原来的位置。要求寻找从初始状态到目标状态的最短途径。2831476512384765初始状态目标状态解：定义生成器函数G(x)——纸牌移入空格的次序是从空格的左边开始，顺时针方向移动，不允许斜向移动，不允许返回第二节基本搜索策略3、示例——重排九宫问题。在3*3的方格棋盘上放置1~8八个13第二节基本搜索策略2831476528314765231847652831476528316475832147652837146523184765231847652814376528314576283164752831647583214765283714651238476523418765281437652831457628364175283167548321476581324765283746152837146512384765123456789101112131415161718192021222324250第二节基本搜索策略283283214第二节基本搜索策略二、深度优先搜索法1、概念由上到下，逐级生成同一级节点，最晚生成，优先扩展评价函数E(x)=N(x)——节点x生成的先后顺序不是搜索算法，是搜索步骤目标节点在最晚分支中，效率较高第二节基本搜索策略二、深度优先搜索法15第二节基本搜索策略2、流程启动S0放入OPEN表OPEN表=NIL取OPEN表中最后的节点N放入CLOSED表冠以顺序nN=SgN可扩展扩展N,将其子节点依次放入OPEN表末尾,配以指向N的返回指针失败成功是否是否是否第二节基本搜索策略2、流程启动S0放入OPEN表OPEN表163、示例——重排九宫问题。在3*3的方格棋盘上放置1~8八个数字，其中有一个方格是空的。只允许把空格上、下、左、右的纸牌移入空格，而空格移至该纸牌原来的位置。要求寻找从初始状态到目标状态的最短途径。2831476512384765初始状态目标状态解：定义生成器函数——纸牌移入空格的次序是从空格的左边开始，顺时针方向移动，不允许斜向移动，不允许返回第二节基本搜索策略3、示例——重排九宫问题。在3*3的方格棋盘上放置1~8八个17283147652831476523184765283147652831647528316475283164752831675412302831675428163754428163754528328323283218第二节基本搜索策略三、有界深度优先搜索法1、概念深度优先搜索法的缺陷引入搜索深度限制：d≤dmdm≥dg，一定可以找到Sg若dm选取不合适dm<dg，搜索失败dm>>dg，搜索效率降低第二节基本搜索策略三、有界深度优先搜索法192、流程启动S0放入OPEN表，d(s0)=0OPEN表=NIL取OPEN表中最后的节点N放入CLOSED表冠以顺序nN=SgN可扩展扩展N,将其子节点依次放入OPEN表末尾,配以指向N的返回指针，d(N’)=d(N)+1失败成功是否是否是否d(N)=dm否是2、流程启动S0放入OPEN表，d(s0)=0OPEN表=N203、示例——重排九宫问题。设深度限制dm=4，用有界深度优先搜索法求解2831476512384765初始状态目标状态解：定义生成器函数——纸牌移入空格的次序是从空格的左边开始，顺时针方向移动，不允许斜向移动，不允许返回第二节基本搜索策略3、示例——重排九宫问题。设深度限制dm=4，用有界深度优先212831476528314765231847652831476528316475283164752831647528316754162302831675428163754542836417578326417528364175981028143765283145762831457615111228314576283157461413281437651628143765248137651817231847652318476523418765242021234187652341857623221238476525123847651237846527261928328323283222第二节基本搜索策略4、变界深度优先搜索法将深度限制的固定值改为可变值，先取较小的dm，若未搜索到目标节点，则加大dm值，再搜索，逐步加大dm值，逐步搜索，当dm=dg时，一定可以搜索到目标节点可找到目标节点，但不一定是最短路径再改进：d（Sgm)

=min1≤i≤n

(d（Sgi))改进后成为搜索算法，而且是可采纳的第二节基本搜索策略4、变界深度优先搜索法23第二节基本搜索策略四、代价驱动搜索法1、概念代价——从一个节点经过一条支路，转移到另一个节点所需要支付的时间或费用等代价树——在问题树上标明代价所形成的赋值问题树代价驱动搜索法——根据“代价最小”原则，优选最小代价的搜索路径第二节基本搜索策略四、代价驱动搜索法24第二节基本搜索策略2、代价驱动广度优先搜索法在广度优先法的基础上，令E(x)=C(x)——从初始节点到节点x所支付的代价代价最小优先扩展择优比较在所有新生成的节点间进行第二节基本搜索策略2、代价驱动广度优先搜索法25流程：启动S0放入OPEN表，C(S0)=0OPEN表=NIL取OPEN表中最前的节点N放入CLOSED表冠以顺序nN=SgN可扩展扩展N，将其子节点依次放入OPEN表，配以指向N的返回指针，对OPEN表中所有节点按C(x)的大小排序（小在前）失败成功是否是是否否流程：启动S0放入OPEN表，C(S0)=0OPEN表=NI26示例——最小费用路线问题。设各城市之间的交通线路如图，出发地为A城，目的地为E城，各支路的交通费用如图，寻找从A城到E城的最小费用交通路线ABDEC321054347解：定义生成器函数G(x)——节点x的子节点取交通图中与x有直接联系的节点（但其父节点除外）第二节基本搜索策略示例——最小费用路线问题。设各城市之间的交通线路如图，出发地27ABDEC321054347ABCDCDDEE273434105CEE4510BDE3410DE54BE45BCE445ABDEC321054347ABCDCDDEE273434128第二节基本搜索策略3、代价驱动深度优先搜索法类似深度优先搜索法，择优比较在当前节点的子节点间进行代价最小优先扩展不一定能找到最优解为避免进入无穷分支，可设置代价限制，当C(N)>Cm时，转其他路径第二节基本搜索策略3、代价驱动深度优先搜索法29流程：启动S0放入OPEN表，C(S0)=0OPEN表=NIL取OPEN表中最前的节点N放入CLOSED表冠以顺序nN=SgN可扩展扩展N，将其子节点配以指向N的返回指针，并将子节点按C(x)的大小排序（小在前）依次放入OPEN表失败成功是否是是否否流程：启动S0放入OPEN表，C(S0)=0OPEN表=NI30ABDEC321054347ABCDCDDEE273434105示例ABDEC321054347ABCDCDDEE273434131第三节启发式搜索一、局部择优搜索法1、概念启发式搜索方法，是深度优先搜索法的改进启发性信息包含在E(x)中当一个节点被扩展时后，用E(x)对它的每一个子节点进行计算，从中找出E(x)最小的那个节点，作为下一次要扩展的节点是小范围的局部择优，又称“瞎子爬山法”深度优先搜索法和代价树的深度优先搜索法是其特例优点——方法简便，搜索速度快缺点——只适合单极值问题，是不完备的搜索步骤第三节启发式搜索一、局部择优搜索法322、流程启动S0放入OPEN表OPEN表=NIL取OPEN表中最前的节点N放入CLOSED表冠以顺序nN=SgN可扩展扩展N，计算每个子节点的E(x)，按E(x)大小将子节点依次放入OPEN表前面，小的在前，为每个子节点配以指向N的返回指针失败成功是否是否是否第三节启发式搜索2、流程启动S0放入OPEN表OPEN表=NIL取OPEN表333、示例——重排九宫问题。用局部择优搜索法求解2831647512384765初始状态目标状态解：定义生成器函数——纸牌移入空格的次序是从空格的左边开始，顺时针方向移动，不允许斜向移动，不允许返回定义评价函数E(x)=h(x)，节点x的格局与目标格局不符合的牌数第三节启发式搜索3、示例——重排九宫问题。用局部择优搜索法求解283342831647528316475283147652831647554352831476523184765283147654338321476528371465438321476538321476581324765348132476544313824765813724654210281324765381324765813264751382476513824765123847652832832832835435第三节启发式搜索二、全局择优搜索法1、概念启发式搜索方法，弥补了局部优先搜索法的局限性择优比较不仅仅在新生成的子节点中进行，而是在所有子节点中进行又称“最好优先搜索法”广度优先搜索法和代价驱动的广度优先搜索法是其特例第三节启发式搜索二、全局择优搜索法362、流程启动S0放入OPEN表OPEN表=NIL取OPEN表中最前的节点N放入CLOSED表冠以顺序nN=SgN可扩展扩展N，为每个子节点配以指向N的返回指针，计算每个子节点的E(x)，将子节点依次放入OPEN表，对OPEN表中全部节点按E(x)从小到大排序，小的在前，失败成功是否是否是否第三节启发式搜索2、流程启动S0放入OPEN表OPEN表=NIL取OPEN表37第三节启发式搜索3、评价函数的启发能力E(x)的启发能力——E(x)所包含的启发信息量的大小E(x)=v·g(x)+w·h(x)g(x)——已付出的价值，是历史信息h(x)——将要付出的价值，是启发信息w↑，v↓——强调纵向深入搜索，启发性↑，完备性↓v↑，w↓——强调横向扫描，完备性↑，启发性↓第三节启发式搜索3、评价函数的启发能力384、示例——重排九宫问题。用全局择优搜索法求解2831476512384765初始状态目标状态解：定义生成器函数：纸牌移入空格的次序是从空格的左边开始，顺时针方向移动，不允许斜向移动，不允许返回定义评价函数：E(x)=d(x)+h(x)d(x)——节点x的深度h(x)——节点x的格局与目标格局不符合的牌数第三节启发式搜索4、示例——重排九宫问题。用全局择优搜索法求解2833928314765283147652318476528314765283164755354483214765283714655623184765231847654612384765412384765123784654628328323283240第四节与/或树图搜索一、与/或树图搜索法的概念根节点——初试问题状态有解的叶节点——终止节点可解节点：终止节点是可解节点当且仅当其子节点中至少有一个是可解节点时，“或”节点是可解节点当且仅当其子节点都是可解节点时，“与”节点是可解节点不可解节点没有子节点的非终止节点是不可解节点当且仅当其全部子节点都是不可解节点时，“或”节点是不可解节点当且仅当其子节点中至少有一个是不可解节点时，“与”节点是不可解节点第四节与/或树图搜索一、与/或树图搜索法的概念41第四节与/或树图搜索可解过程——标记可解节点（●）的过程，若根节点可解，搜索成功不可解过程——标记不可解节点（×）的过程，若根节点不可解，搜索失败解树——由导致根节点为可解节点的有关可解节点及“树枝”所组成的子树第四节与/或树图搜索可解过程——标记可解节点（●）的过程，42第四节与/或树图搜索二、与/或树图搜索法的流程（1）将初始问题设置为根节点（2）扩展初始节点，扩展深度可以大于1（3）设置返回指针（4）反复执行（2）、（3），直到：根节点可以标记为可解节点，搜索成功根节点可以标记为不可解节点，搜索失败第四节与/或树图搜索二、与/或树图搜索法的流程43第四节与/或树图搜索三、解树代价的计算1、“与”节点代价计算法（1）最大代价法（2）代价和法xh(x)x1h(

x1)x2h(

x2)x3h(

x3)c(x,x1)c(x,x3)c(x,x2)第四节与/或树图搜索三、解树代价的计算（2）代价和法xh44第四节与/或树图搜索2、“或”节点代价计算法xh(x)x1h(

x1)x2h(

x2)x3h(

x3)c(x,x1)c(x,x3)c(x,x2)3、叶节点代价的定义可解叶节点（终止节点）——h(x)=0不可解叶节点——h(x)=∞4、解树的总代价——从终止节点出发，通过解树，逐级回溯，向上计算根节点的代价第四节与/或树图搜索2、“或”节点代价计算法xh(x)x45第四节与/或树图搜索5、示例——设问题的与/或树如图所示，计算解树的总代价×××4456244324573Sa1a2a3a4a5a6b1b2b3b4b5第四节与/或树图搜索5、示例——设问题的与/或树如图所示，46第四节与/或树图搜索四、与/或树最好优先搜索法1、概念引入启发信息估计节点x的代价h(x)由h(x)估计最优解树的近根部分——希望解树τ0希望解树的定义：初始节点在希望解树中若或节点x在希望解树中，则其子节点集中，具有最小代价的子节点应在希望解树中若与节点x在希望解树中，则其子节点集中具有最大代价的子节点应在希望解树中（最大代价法）其全部子节点均在希望解树中（代价和法）第四节与/或树图搜索四、与/或树最好优先搜索法若与节点x在472、流程启动S0放入OPEN表，估计h(S0)从OPEN表依次选出τ0的端节点N放入CLOSED表，顺序编号N是终止节点N可扩展否由h(x)估计τ0标记N为不可解节点，对τ0应用不可解过程否S0不可解从OPEN表中除去有不可解父节点的节点失败标记N为可解节点，对τ0应用可解过程S0可解从OPEN表中除去有可解父节点的节点成功是是否否扩展N，子节点依次放入OPEN表，配以指向N的返回指针，估计子节点及其先辈节点的h(x)是是2、流程启动S0放入OPEN表，估计h(S0)从OPEN表依48第四节与/或树图搜索3、示例——应用最好优先搜索法求与/或树的最小代价树。设每条树枝的代价均为1，每次扩展深度为2解：SABCDEF3323322276700222630052293887129第四节与/或树图搜索3、示例——应用最好优先搜索法求与/或49第五节博弈树图搜索一、概念1、二人零和、全信息、非偶然2、博弈树——双方轮流扩展，是特殊的与/或树第五节博弈树图搜索一、概念2、博弈树——双方轮流扩展，是特50第五节博弈树图搜索二、特点1、“与”节点、“或”节点逐级交替出现2、从我方看，所有敌方的节点都是“与”节点3、从我方看，所有我方的节点都是“或”节点4、所有能使我方获胜的终局，其相应的端节点都是可解节点，得分为正所有使敌方获胜的终局，对我方而言，是不可解节点，得分为负5、先走一方的初始状态相应于根节点第五节博弈树图搜索二、特点51第五节博弈树图搜索三、极大极小分析法1、基本思想评价函数：E(x)=φ1(x)双方根据“极大、极小”原则，选取对自己最有利的棋步我方最优：max[E(x)]——扩展“或”节点敌方最优：min[E(x)]——扩展“与”节点从端节点的得分估计值出发，倒推根节点的得分，选取我方得分极大，敌方得分极小的最优棋步，逐级搜索，求解博弈问题第五节博弈树图搜索三、极大极小分析法52第五节博弈树图搜索2、示例maxmaxmaxminmin2931-1-13-168203-574-26-1-18-1032-1-16-10-5-2-1-1-1260-1-12-12第五节博弈树图搜索2、示例maxmaxmaxminmin253第五节博弈树图搜索3、实际应用以一定的深度生成博弈树，应用启发性信息估计各端节点的估值用极大极小分析法倒推根节点的估值，选取当前的最优棋步以当前最优棋步为初始状态，按一定的深度生成搜索树，得下一个最优棋步逐级搜索，达到终局为止第五节博弈树图搜索3、实际应用54第五节博弈树图搜索示例——一字棋博弈，用极大极小分析法求双方的最优棋步解：扩展深度为2，估值函数h(x)=我方路数—对方路数×××○×○×○×○×○××○○××○○×○×○×○×2-1=13-2=12-2=02-3=-12-2=03-2=13-1=21-2=-11-3=-22-3=-12-2=01-1=0-11-21第五节博弈树图搜索示例——一字棋博弈，用极大极小分析法求双55第五节博弈树图搜索3、“α—β”剪枝法272≥2SABCDEF1≤1=2第五节博弈树图搜索3、“α—β”剪枝法272≥2SABCD56第五节博弈树图搜索（1）α、β值的定义或节点x的α值——x倒推估计值b(x)的下界,b(x)≥α与节点y的β值——y倒推估计值b(y)的上界,b(y)≤β（2）规则α剪枝——若与节点的β值，不能使其父节点的α值升高，则该与节点以下的分枝可以剪掉Β煎枝——若或节点的α值，不能使其父节点的β值降低，则该或节点以下的分枝可以剪掉第五节博弈树图搜索（1）α、β值的定义57第五节博弈树图搜索（3）示例2931-1-13-168203-574-26-1-18-1032≤160≥2≤-1=2≤2≥6=2≥2≥0≤-5=0≤0=2α剪α剪β剪α剪α剪α剪第五节博弈树图搜索（3）示例2931-1-13-1682058第一节知识推理的概念和类型第二节基本搜索策略第三节启发式搜索策略第四节与/或树图搜索第五节博弈树图搜索第三章知识的推理技术第一节知识推理的概念和类型第三章知识的推理技术59第一节知识推理的概念和类型一、知识推理的概念1、知识推理——运用知识求解问题2、知识推理技术——是问题从初始状态转移到目标状态的方法和途径3、知识推理技术的研究目标——寻找从初始状态沿着最优或最经济的途径转移到目标状态的智能操作序列，实现问题求解过程的计算机化第一节知识推理的概念和类型一、知识推理的概念60二、知识推理的分类1、根据知识表达方式图搜索法——如广度优先法、深度优先法逻辑论证法——如王浩命题逻辑算法、鲁滨逊谓词逻辑算法2、根据推理过程的完备性推理算法——完备的推理过程，如广度优先法推理步骤——不完备的推理过程，如深度优先法3、根据推理过程是否运用启发性知识启发推理——运用启发性知识，提高搜索效率，如全局择优法、局部择优法非启发推理——效率较低，如广度优先法第一节知识推理的概念和类型二、知识推理的分类第一节知识推理的概念和类型61三、符号模式匹配1、概念符号模式——用于知识表达的各种符号表达式匹配——比较和选配符号模式匹配——将一个符号表达式与另一个符号表达式进行比较和选配，判断它们是否可以相互匹配事实模式目标模式——目标模式的各分量都可被事实模式匹配，称目标模式可匹配第一节知识推理的概念和类型三、符号模式匹配第一节知识推理的概念和类型622、示例例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的匹配过程第一节知识推理的概念和类型2、示例第一节知识推理的概念和类型63例3——设一个产生式系统包含一条如下规则IF((>animal)isa(>type))∧((<animal)isaparentof(>child))THEN(<child)isa(<type)事实库中有如下事实：bozoisacheetahbozoisaparentofbillybozoisaparentofsugarsweekumsisapenguinkingisaparentofrex检查规则的前提部分能否被事实库匹配第一节知识推理的概念和类型例3——设一个产生式系统包含一条如下规则第一节知识推理的概64四、图搜索的基本概念1、状态图搜索树巡回推销员问题——假设一个推销员要到4个城市去访问，然后回家，不走回头路。问题是寻找一条最短的路径，使得推销员访问过每个城市后回到出发地。ABCD47106105第一节知识推理的概念和类型AABACADABCABDACBACDADBADCABCDABDCACBDACDBADBCADCBABCDA26ABDCA25ACBDA33ACDBE25ADBCA33ADCBA264610710751055510107710610446四、图搜索的基本概念ABCD47106105第一节知识推理652、存储方式显式存储——存储全部状态空间隐式存储——只存储与问题有关的部分知识3、隐式图搜索方法运用叙述性知识，给出问题的部分状态描述运用过程性知识，给出生成器函数G(x)——父节点生成子节点的规则运用控制性知识，给出评价函数E(x)——评价新生成的节点，控制继续搜索的方向第一节知识推理的概念和类型2、存储方式第一节知识推理的概念和类型664、隐式图搜索的基本过程（1）给定初始状态S0（2）用生成器函数G(x)，由S0出发生成其子节点，检查是否出现目标状态Sg，若出现，则成功（3）若未出现，继续搜索，用评价E(x)对各子节点进行评价，选取最有希望的节点，再用G(x)生成其子节点，再检查是否出现Sg（4）如此逐步搜索，直到找到Sg为止第一节知识推理的概念和类型4、隐式图搜索的基本过程第一节知识推理的概念和类型675、搜索过程的完备性搜索过程是完备的——给定一类可解的状态空间<S,F,G>和一个搜索过程A，如对任一S0∈S，搜索过程A总可以发现一条从S0到达Sg∈G的通路，则称搜索过程A对问题类<S,F,G>是完备的。搜索过程是可采纳的——若A找到的总是最佳解，则称它是可采纳的，记为A*6、启发式与非启发式搜索过程如果在估计函数E(x)中包含有关于待求解问题的某些先验知识，如解的特性、解的分布规律等，那么搜索过程就能有选择地朝目标节点有效地推进，这时就称该搜索过程A为关于问题类<S,F,G>的启发式搜索过程，反之称为非启发式搜索过程第一节知识推理的概念和类型5、搜索过程的完备性第一节知识推理的概念和类型68第二节基本搜索策略一、广度优先搜索法1、概念由上到下，逐级生成从左到右，横扫各个节点评价函数E(x)=d(x)——节点x的深度是搜索算法，并且是可采纳的第二节基本搜索策略一、广度优先搜索法69第二节基本搜索策略2、流程启动S0放入OPEN表OPEN表=NIL取OPEN表中最前的节点N放入CLOSED表冠以顺序nN=SgN可扩展扩展N,将其子节点依次放入OPEN表末尾,配以指向N的返回指针失败成功是否是否是否第二节基本搜索策略2、流程启动S0放入OPEN表OPEN表703、示例——重排九宫问题。在3*3的方格棋盘上放置1~8八个数字，其中有一个方格是空的。只允许把空格上、下、左、右的纸牌移入空格，而空格移至该纸牌原来的位置。要求寻找从初始状态到目标状态的最短途径。2831476512384765初始状态目标状态解：定义生成器函数G(x)——纸牌移入空格的次序是从空格的左边开始，顺时针方向移动，不允许斜向移动，不允许返回第二节基本搜索策略3、示例——重排九宫问题。在3*3的方格棋盘上放置1~8八个71第二节基本搜索策略2831476528314765231847652831476528316475832147652837146523184765231847652814376528314576283164752831647583214765283714651238476523418765281437652831457628364175283167548321476581324765283746152837146512384765123456789101112131415161718192021222324250第二节基本搜索策略283283272第二节基本搜索策略二、深度优先搜索法1、概念由上到下，逐级生成同一级节点，最晚生成，优先扩展评价函数E(x)=N(x)——节点x生成的先后顺序不是搜索算法，是搜索步骤目标节点在最晚分支中，效率较高第二节基本搜索策略二、深度优先搜索法73第二节基本搜索策略2、流程启动S0放入OPEN表OPEN表=NIL取OPEN表中最后的节点N放入CLOSED表冠以顺序nN=SgN可扩展扩展N,将其子节点依次放入OPEN表末尾,配以指向N的返回指针失败成功是否是否是否第二节基本搜索策略2、流程启动S0放入OPEN表OPEN表743、示例——重排九宫问题。在3*3的方格棋盘上放置1~8八个数字，其中有一个方格是空的。只允许把空格上、下、左、右的纸牌移入空格，而空格移至该纸牌原来的位置。要求寻找从初始状态到目标状态的最短途径。2831476512384765初始状态目标状态解：定义生成器函数——纸牌移入空格的次序是从空格的左边开始，顺时针方向移动，不允许斜向移动，不允许返回第二节基本搜索策略3、示例——重排九宫问题。在3*3的方格棋盘上放置1~8八个75283147652831476523184765283147652831647528316475283164752831675412302831675428163754428163754528328323283276第二节基本搜索策略三、有界深度优先搜索法1、概念深度优先搜索法的缺陷引入搜索深度限制：d≤dmdm≥dg，一定可以找到Sg若dm选取不合适dm<dg，搜索失败dm>>dg，搜索效率降低第二节基本搜索策略三、有界深度优先搜索法772、流程启动S0放入OPEN表，d(s0)=0OPEN表=NIL取OPEN表中最后的节点N放入CLOSED表冠以顺序nN=SgN可扩展扩展N,将其子节点依次放入OPEN表末尾,配以指向N的返回指针，d(N’)=d(N)+1失败成功是否是否是否d(N)=dm否是2、流程启动S0放入OPEN表，d(s0)=0OPEN表=N783、示例——重排九宫问题。设深度限制dm=4，用有界深度优先搜索法求解2831476512384765初始状态目标状态解：定义生成器函数——纸牌移入空格的次序是从空格的左边开始，顺时针方向移动，不允许斜向移动，不允许返回第二节基本搜索策略3、示例——重排九宫问题。设深度限制dm=4，用有界深度优先792831476528314765231847652831476528316475283164752831647528316754162302831675428163754542836417578326417528364175981028143765283145762831457615111228314576283157461413281437651628143765248137651817231847652318476523418765242021234187652341857623221238476525123847651237846527261928328323283280第二节基本搜索策略4、变界深度优先搜索法将深度限制的固定值改为可变值，先取较小的dm，若未搜索到目标节点，则加大dm值，再搜索，逐步加大dm值，逐步搜索，当dm=dg时，一定可以搜索到目标节点可找到目标节点，但不一定是最短路径再改进：d（Sgm)

=min1≤i≤n

(d（Sgi))改进后成为搜索算法，而且是可采纳的第二节基本搜索策略4、变界深度优先搜索法81第二节基本搜索策略四、代价驱动搜索法1、概念代价——从一个节点经过一条支路，转移到另一个节点所需要支付的时间或费用等代价树——在问题树上标明代价所形成的赋值问题树代价驱动搜索法——根据“代价最小”原则，优选最小代价的搜索路径第二节基本搜索策略四、代价驱动搜索法82第二节基本搜索策略2、代价驱动广度优先搜索法在广度优先法的基础上，令E(x)=C(x)——从初始节点到节点x所支付的代价代价最小优先扩展择优比较在所有新生成的节点间进行第二节基本搜索策略2、代价驱动广度优先搜索法83流程：启动S0放入OPEN表，C(S0)=0OPEN表=NIL取OPEN表中最前的节点N放入CLOSED表冠以顺序nN=SgN可扩展扩展N，将其子节点依次放入OPEN表，配以指向N的返回指针，对OPEN表中所有节点按C(x)的大小排序（小在前）失败成功是否是是否否流程：启动S0放入OPEN表，C(S0)=0OPEN表=NI84示例——最小费用路线问题。设各城市之间的交通线路如图，出发地为A城，目的地为E城，各支路的交通费用如图，寻找从A城到E城的最小费用交通路线ABDEC321054347解：定义生成器函数G(x)——节点x的子节点取交通图中与x有直接联系的节点（但其父节点除外）第二节基本搜索策略示例——最小费用路线问题。设各城市之间的交通线路如图，出发地85ABDEC321054347ABCDCDDEE273434105CEE4510BDE3410DE54BE45BCE445ABDEC321054347ABCDCDDEE273434186第二节基本搜索策略3、代价驱动深度优先搜索法类似深度优先搜索法，择优比较在当前节点的子节点间进行代价最小优先扩展不一定能找到最优解为避免进入无穷分支，可设置代价限制，当C(N)>Cm时，转其他路径第二节基本搜索策略3、代价驱动深度优先搜索法87流程：启动S0放入OPEN表，C(S0)=0OPEN表=NIL取OPEN表中最前的节点N放入CLOSED表冠以顺序nN=SgN可扩展扩展N，将其子节点配以指向N的返回指针，并将子节点按C(x)的大小排序（小在前）依次放入OPEN表失败成功是否是是否否流程：启动S0放入OPEN表，C(S0)=0OPEN表=NI88ABDEC321054347ABCDCDDEE273434105示例ABDEC321054347ABCDCDDEE273434189第三节启发式搜索一、局部择优搜索法1、概念启发式搜索方法，是深度优先搜索法的改进启发性信息包含在E(x)中当一个节点被扩展时后，用E(x)对它的每一个子节点进行计算，从中找出E(x)最小的那个节点，作为下一次要扩展的节点是小范围的局部择优，又称“瞎子爬山法”深度优先搜索法和代价树的深度优先搜索法是其特例优点——方法简便，搜索速度快缺点——只适合单极值问题，是不完备的搜索步骤第三节启发式搜索一、局部择优搜索法902、流程启动S0放入OPEN表OPEN表=NIL取OPEN表中最前的节点N放入CLOSED表冠以顺序nN=SgN可扩展扩展N，计算每个子节点的E(x)，按E(x)大小将子节点依次放入OPEN表前面，小的在前，为每个子节点配以指向N的返回指针失败成功是否是否是否第三节启发式搜索2、流程启动S0放入OPEN表OPEN表=NIL取OPEN表913、示例——重排九宫问题。用局部择优搜索法求解2831647512384765初始状态目标状态解：定义生成器函数——纸牌移入空格的次序是从空格的左边开始，顺时针方向移动，不允许斜向移动，不允许返回定义评价函数E(x)=h(x)，节点x的格局与目标格局不符合的牌数第三节启发式搜索3、示例——重排九宫问题。用局部择优搜索法求解283922831647528316475283147652831647554352831476523184765283147654338321476528371465438321476538321476581324765348132476544313824765813724654210281324765381324765813264751382476513824765123847652832832832835493第三节启发式搜索二、全局择优搜索法1、概念启发式搜索方法，弥补了局部优先搜索法的局限性择优比较不仅仅在新生成的子节点中进行，而是在所有子节点中进行又称“最好优先搜索法”广度优先搜索法和代价驱动的广度优先搜索法是其特例第三节启发式搜索二、全局择优搜索法942、流程启动S0放入OPEN表OPEN表=NIL取OPEN表中最前的节点N放入CLOSED表冠以顺序nN=SgN可扩展扩展N，为每个子节点配以指向N的返回指针，计算每个子节点的E(x)，将子节点依次放入OPEN表，对OPEN表中全部节点按E(x)从小到大排序，小的在前，失败成功是否是否是否第三节启发式搜索2、流程启动S0放入OPEN表OPEN表=NIL取OPEN表95第三节启发式搜索3、评价函数的启发能力E(x)的启发能力——E(x)所包含的启发信息量的大小E(x)=v·g(x)+w·h(x)g(x)——已付出的价值，是历史信息h(x)——将要付出的价值，是启发信息w↑，v↓——强调纵向深入搜索，启发性↑，完备性↓v↑，w↓——强调横向扫描，完备性↑，启发性↓第三节启发式搜索3、评价函数的启发能力964、示例——重排九宫问题。用全局择优搜索法求解2831476512384765初始状态目标状态解：定义生成器函数：纸牌移入空格的次序是从空格的左边开始，顺时针方向移动，不允许斜向移动，不允许返回定义评价函数：E(x)=d(x)+h(x)d(x)——节点x的深度h(x)——节点x的格局与目标格局不符合的牌数第三节启发式搜索4、示例——重排九宫问题。用全局择优搜索法求解2839728314765283147652318476528314765283164755354483214765283714655623184765231847654612384765412384765123784654628328323283298第四节与/或树图搜索一、与/或树图搜索法的概念根节点——初试问题状态有解的叶节点——终止节点可解节点：终止节点是可解节点当且仅当其子节点中至少有一个是可解节点时，“或”节点是可解节点当且仅当其子节点都是可解节点时，“与”节点是可解节点不可解节点没有子节点的非终止节点是不可解节点当且仅当其全部子节点都是不可解节点时，“或”节点是不可解节点当且仅当其子节点中至少有一个是不可解节点时，“与”节点是不可解节点第四节与/或树图搜索一、与/或树图搜索法的概念99第四节与/或树图搜索可解过程——标记可解节点（●）的过程，若根节点可解，搜索成功不可解过程——标记不可解节点（×）的过程，若根节点不可解，搜索失败解树——由导致根节点为可解节点的有关可解节点及“树枝”所组成的子树第四节与/或树图搜索可解过程——标记可解节点（●）的过程，100第四节与/或树图搜索二、与/或树图搜索法的流程（1）将初始问题设置为根节点（2）扩展初始节点，扩展深度可以大于1（3）设置返回指针（4）反复执行（2）、（3），直到：根节点可以标记为可解节点，搜索成功根节点可以标记为不可解节点，搜索失败第四节与/或树图搜索二、与/或树图搜索法的流程101第四节与/或树图搜索三、解树代价的计算1、“与”节点代价计算法（1）最大代价法（2）代价和法xh(x)x1h(

x1)x2h(

x2)x3h(

x3)c(x,x1)c(x,x3)c(x,x2)第四节与/或树图搜索三、解树代价的计算（2）代价和法xh102第四节与/或树图搜索2、“或