人工智能课件 －－02.知识的表示与推理-1.ppt

第第2 2章章 知识的表示与推理知识的表示与推理(1)(1) 以符号和逻辑为基础的传统人工智能问题求解是通过知识表示和知识推理来实现的 每种以知识和符号操作为基础的智能系统，其问题求解方法都需要对某种解答空间的搜索 知识表示空间搜索第一节第一节 知识表示的一般方法知识表示的一般方法l 状态空间法l 问题归约法l 谓词逻辑法l 产生式表示法l 语义网络法l 框架表示法l 脚本表示法l 过程表示法l Petri表示法l 面向对象表示法知识表示的常用方法：知识表示的常用方法：问题状态的描述问题状态的描述问题状态的描述问题状态的描述第一节第一节 知识表示的一般方法知识表示的一般方法一、状态空间法一、状态空间法状态状态状态状态算符算符算符算符状态空间状态空间状态空间状态空间 是为描述某类问题不同事物间的差别而引入的一组最少变量的有序集合 其矢量形式为： Q = [ q0,q1,…,qn ]T 其中，每个元素qi为集合的分量，称为状态变量 每个分量的一组值就得到一个具体状态 使问题从一种状态变化为另一种状态的手段称为算符、操作符或运算符 由问题的全部可能状态及其关系所构成的集合。

状态空间一般表示为：(S,F,G)其中，S是初始状态； F是算符；G是目标状态 状态空间的图示形式称为状态空间图第一节第一节 知识表示的一般方法知识表示的一般方法BACDE 路程或费用 A B C D EA 7 6 10 13B 7 10 10C 5 9 D 6例例1 1：推销员问题：推销员问题第一节第一节 知识表示的一般方法知识表示的一般方法起始节点AABACADAEACBACDACE问题：如何进行有效搜索？问题：如何进行有效搜索？第一节第一节 知识表示的一般方法知识表示的一般方法例例2 2：猴子和香蕉问题：猴子和香蕉问题香蕉箱子猴子acb第一节第一节 知识表示的一般方法知识表示的一般方法 用一个四元表列(W,x,Y,z)表示该问题的状态，其中，W 表示猴子的位置x 表示猴子在箱子顶上时取x=1；否则x=0Y 表示箱子的水平位置z 表示猴子摘到香蕉时取z=1;否则z=0 定义该问题中的算符如下：定义该问题中的算符如下：定义该问题中的算符如下：定义该问题中的算符如下： (1) goto(U) 猴子走到水平位置U (2) pushbox(V) 猴子把箱子推到水平位置V (3) Climbbox 猴子爬到箱子顶上 (4) Grasp 猴子摘到香蕉第一节第一节 知识表示的一般方法知识表示的一般方法V=c,pushbox(a,0,b,0)(U,0,b,0)(V,0,V,0)(b,1,b,0)(c,1,c,0)(U,0,V,0)(c,1,c,1)goto(U)U=bU=b,climbboxgraspgoto(U) 把该问题从初始状态变换为目标状态的操作系列为： {Goto(b),pushbox(c),climbbox,grasp}第一节第一节 知识表示的一般方法知识表示的一般方法ü首先必须定义状态的描述形式，通过使用这种描述形式把问题的一切状态全部表示出来。

ü其次，定义一组算子，通过算子可以把问题从一种状态变换为另一种状态ü问题求解的过程是一个不断把算子作用于状态的过程如果在使用某个算子后，得到的状态是目标状态，则得到了问题的解 使用算子最少的解是最优解使用算子最少的解是最优解使用算子最少的解是最优解使用算子最少的解是最优解ü对任何一个状态，可使用的算子可能不止一个，因此，可产生的后续状态就可能有多个用状态空间法解决问题时的几点说明用状态空间法解决问题时的几点说明用状态空间法解决问题时的几点说明用状态空间法解决问题时的几点说明第一节第一节 知识表示的一般方法知识表示的一般方法二、问题归约法二、问题归约法 问题归约是另一种问题描述与求解方法它由目标出发，逆向推理，通过一系列变换把初始问题变换为子问题集合和子子问题集合，直到最后规约为一个平凡的本原问题 变换的一般过程分解 等价变换 把一个复杂问题分解为若干个较为简单的子问题，每个子问题继续分解，直到不需要分解为止 分解得到的是与树 利用同构或同态的等价变换，把问题变换为若干个较易解决的问题 等价变换得到的是或树第一节第一节 知识表示的一般方法知识表示的一般方法PP1P2P3PP1P2P3第一节第一节 知识表示的一般方法知识表示的一般方法l本原问题本原问题本原问题本原问题 不能再分解或变换，而且是直接可解的子问题。

l端节点与终止节点端节点与终止节点端节点与终止节点端节点与终止节点 在与或树中，没有子节点的节点称为端节点；本原问题对应的节点称为终止节点l可解节点、不可解节点、解树可解节点、不可解节点、解树可解节点、不可解节点、解树可解节点、不可解节点、解树一些概念一些概念一些概念一些概念第一节第一节 知识表示的一般方法知识表示的一般方法例、三阶梵塔问题例、三阶梵塔问题例、三阶梵塔问题例、三阶梵塔问题123ABC初始情况123ABC目标情况用三元组(CBA)表示三个圆盘所在的柱子解决的问题：解决的问题：解决的问题：解决的问题：(111)=>(333)(111)=>(333)(111)=>(333)(111)=>(333)第一节第一节 知识表示的一般方法知识表示的一般方法123ABC123(111)(122)123(122)123(322)123(322)123(333)①移动A和B到2②移动C到3③移动A和B到3第一节第一节 知识表示的一般方法知识表示的一般方法(111)=>(333)(111)=>(122)(122)=>(322)(322)=>(333)(111)=>(113) (113)=>(123) (123)=>(122)(322)=>(321) (321)=>(331) (331)=>(333)第一节第一节 知识表示的一般方法知识表示的一般方法三、谓词表示法三、谓词表示法1 1、复习、复习( (命题逻辑与谓词逻辑命题逻辑与谓词逻辑) )(1) (1) 命题命题 定义：命题是具有真假意义的语句。

定义：命题是具有真假意义的语句 命题代表人们进行思维的一种判断，或者为肯定，或者为否定 在命题逻辑中，通常用大写的英文字母表示例如，可用英文字母P表示“西安是个古老的城市”这个命题第一节第一节 知识表示的一般方法知识表示的一般方法(2)(2)谓词谓词 在谓词逻辑中，命题用谓词来表示 谓词的一般形式：谓词的一般形式：P(xP(x1 1,x,x2 2,…,x,…,xn n) )其中P是谓词名，xi是个体个体可以是变量、常量或函数 在P(x1,x2,…,xn)中，如果xi是变量、常量或函数,则称为一阶谓词；如果xi本身又是一个一阶谓词，则称为二阶谓词第一节第一节 知识表示的一般方法知识表示的一般方法个体域：个体域：个体变元的取值范围 例如，用I(x)表示“x是整数”，则个体域是所有整数，且是无限的谓词公式：谓词公式：①① 连接词连接词• ¬ : 否定• ٧ : 析取• ٨ : 合取• →: 蕴含• : 双条件第一节第一节 知识表示的一般方法知识表示的一般方法②②②② 量词量词量词量词• ∀ : 全称量词• ∃ : 存在量词③③③③ 谓词公式谓词公式谓词公式谓词公式 定义：按下列规则得到的谓词演算称为合式公式：• 单个谓词公式是合式公式，称为原子谓词公式；• 若A是合式公式，则¬A也是合式公式；• 若A、B都是合式公式，则A ٧ B、A ٨ B、A→B、A B也都是合式公式。

•若 A是合式公式，x是任一个个体变元，则(∃x、) A(∀x)A也都是合式公式第一节第一节 知识表示的一般方法知识表示的一般方法④④④④ 谓词公式的解释谓词公式的解释谓词公式的解释谓词公式的解释 在命题逻辑中，对命题公式中各个变元的一次真值指派，称为命题公式的一个解释⑤⑤⑤⑤ 谓词公式的永真性、可满足性、不可满足性谓词公式的永真性、可满足性、不可满足性谓词公式的永真性、可满足性、不可满足性谓词公式的永真性、可满足性、不可满足性 如果谓词公式P对个体域D上的任何一个解释都取真值T，则称P在D上永真的 对于谓词公式P，如果至少存在一个解释使得公式P为真值T,则称公式P是可满足的 如果谓词公式P对于个体域D上的任何一个解释都取真值 F，则称P在D上是不可满足的，或永假的第一节第一节 知识表示的一般方法知识表示的一般方法⑥⑥⑥⑥ 谓词公式的等价性和永真蕴含谓词公式的等价性和永真蕴含谓词公式的等价性和永真蕴含谓词公式的等价性和永真蕴含 各类等价公式 对于谓词公式P和Q，如果P→Q永真，则称P永真蕴含Q，且称 Q为P的逻辑结论，称P为Q的前提，即，P=>Q 常用的永真蕴含公式：• 化简式 P ٨ Q =>P, P ٨ Q =>Q• 附加式 P=>P ٧ Q• 析取三段论 ¬P, P ٧ Q =>Q第一节第一节 知识表示的一般方法知识表示的一般方法• 假言推理 P, P → Q =>Q• 拒取式 ¬Q, P→Q=> ¬P• 假言三段论 P→Q, Q→R => P→R• 二难推论 P ٧ Q, P → R, Q → R => R• 全称固化 (∀x) P(x) => p(y) 其中,y是个体域中的任一个体。

第一节第一节 知识表示的一般方法知识表示的一般方法• 存在固化 (∃x) P(x) => p(y) 其中,y是个体域中某个可使p(y)为真的个体重要的推理规则：重要的推理规则：重要的推理规则：重要的推理规则：l P规则：在推理的任何步骤上都可引入前提l T规则：推理时，如果前面的步骤中有一个或多个公式永真蕴含公式S，则可把S加入推理过程中l CP规则：如果能从R和前提规则集合中推出S，则可从前提集合中推出 R→S第一节第一节 知识表示的一般方法知识表示的一般方法l 反证法：P=>Q，当且仅当P ٨ ¬Q <=> F即，Q是P的逻辑结论，当且仅当P ٨ ¬Q是不可满足的 重要定理： Q为P1,P2,…,Pn的逻辑结论，当且仅当 （P1 ٨ P2 ٨ … ٨ Pn） ٨ ¬Q是不可满足的第一节第一节 知识表示的一般方法知识表示的一般方法2 2、一阶谓词表示法、一阶谓词表示法(1) (1) 表示知识的方法表示知识的方法 谓词逻辑适合于表示事物的状态、属性、概念等事实性知识，也可以表示事物之间的因果关系，即，规则 事实通常用谓词公式的与/或形表示，规则用蕴含式表示。

用谓词表示知识前，要首先定义谓词，指出每个谓词的确切含义，然后再用连接词把相关的谓词连接起来，形成一个有完整意义的谓词公式第一节第一节 知识表示的一般方法知识表示的一般方法例1，设有如下知识： 刘欢比他父亲出名 高扬是计算机系的一名学生，但他不喜欢编程 人人爱劳动定义谓词： Bigger(x,y): x比y 出名； Computer(x):x是计算机系的学生; Like(x,y): x喜欢y; Love(x,y):x爱y; Man(x): x是人第一节第一节 知识表示的一般方法知识表示的一般方法则上述知识可表示为：则上述知识可表示为：则上述知识可表示为：则上述知识可表示为： Bigger(liuhuan, father(liuhuan) ) Computer(Gaoyang)٨¬ Like(Gaoyang,programming) (∀x) ( Man(x) → Love(x,Labour) )第一节第一节 知识表示的一般方法知识表示的一般方法例2，设在房内c处有一个机器人，在a,b处各有一张桌子，a上有一个盒子让机器人从c处出发把盒子从a处拿到b处，然后再回到c处。

用一阶谓词描述机器人的行动过程abc机器人行动规划第一节第一节 知识表示的一般方法知识表示的一般方法定义谓词：定义谓词：定义谓词：定义谓词： Table(x)：x是桌子 Empty(y)：y手中是空的 At(y,z)：y在z的附近Holds(y,w)：y拿着w On(w,x)：w在x的上面则，个体域， x∈{a,b}, y∈{robot}, z∈{a,b,c}, w∈{box}第一节第一节 知识表示的一般方法知识表示的一般方法问题的初始状态：问题的初始状态：问题的初始状态：问题的初始状态： At(robot,c), Empty(robot), On(box,a) Table(a), Table(b)问题的目标状态：问题的目标状态：问题的目标状态：问题的目标状态： At(robot,c), Empty(robot), On(box,b) Table(a), Table(b)定义操作算子：定义操作算子：定义操作算子：定义操作算子： Goto(x,y): 从x处走到y处 Pick-up(x): 在x处拿起盒子 Set-Down(x):在x处放下盒子通过搜索状态空间即可得到机器人的行动过程。

第一节第一节 知识表示的一般方法知识表示的一般方法(2)(2)一阶谓词表示法的特点一阶谓词表示法的特点• 自然性• 精确性• 严密性• 容易实现(3)(3)一阶谓词表示法的局限性一阶谓词表示法的局限性• 不能表示不确定性知识• 组合爆炸• 效率低第一节第一节 知识表示的一般方法知识表示的一般方法四、产生式表示法四、产生式表示法(产生式规则产生式规则) 产生式的基本形式 IF P Then Q 或 P → Q例如， IF 动物会飞 and 会下蛋 Then 该动物是鸟注意：蕴含式和产生式的区别注意：蕴含式和产生式的区别(1) 产生式可以表示不确定知识；(2) 产生式的条件匹配可以是不精确的第一节第一节 知识表示的一般方法知识表示的一般方法五、框架表示法五、框架表示法 1975年明斯基提出了框架理论，该理论认为，人们对现实世界的认识都是以一种类似于框架的结构存储在记忆中的，当面临一个新问题时，就从记忆中找出一个合适的框架，并根据实际情况对其细节进行修改、补充，从而形成对当前事物的认识第一节第一节 知识表示的一般方法知识表示的一般方法1 1、框架、框架 框架是描述所论对象属性的数据结构。

在框架理论中，将框架视其为表示知识的基本单位 一个框架由若干个“槽”组成，每一个槽根据实际情况又由若干个“侧面”组成 一个“槽”描述所论对象某一方面的属性，一个“侧面”用于描述相应属性的一个方面 槽和侧面所具有的值分别称为槽值和侧面值 框架名、槽名、侧面名第一节第一节 知识表示的一般方法知识表示的一般方法<框架名>槽名1: 侧面名1: 值1,值2,…,值p1 侧面名2: 值1,值2,…,值p2 ……. ……………… 侧面名m1: 值1,值2,…,值pm………………..槽名n: 侧面名1: 值1,值2,…,值p1 ……. ……………… 侧面名m1: 值1,值2,…,值pm约束： 约束条件1 ………….. 约束条件n第一节第一节 知识表示的一般方法知识表示的一般方法例例例例1 1、一个描述教师的通用框架、一个描述教师的通用框架、一个描述教师的通用框架、一个描述教师的通用框架 框架名：<教师> 姓名：单位(姓、名) 年龄：单位(岁) 性别：范围(男、女) 缺省：男 职称：范围(教授、副教授、讲师、助教) 缺省：讲师 部门：单位（系、教研室） 住址：<住址框架> 工资：<工资框架>第一节第一节 知识表示的一般方法知识表示的一般方法一个具体教师的框架一个具体教师的框架一个具体教师的框架一个具体教师的框架：： 框架名：<教师-1> 姓名：张三 年龄：36 性别：女 职称：教授 部门：计算机软件教研室 住址：< addr-1> 工资：第一节第一节 知识表示的一般方法知识表示的一般方法例例例例2 2 2 2、一个描述假冒伪劣商品的通用框架、一个描述假冒伪劣商品的通用框架、一个描述假冒伪劣商品的通用框架、一个描述假冒伪劣商品的通用框架 框架名：<假冒伪劣商品> 商品名称： 生成厂家： 销售商店： 处 罚：处理方式： 处罚依据： 处罚时间： 经办部门：第一节第一节 知识表示的一般方法知识表示的一般方法2 2、框架网络、框架网络 由于框架中的槽值和侧面值都可以是另一个框架的名字，因此就在框架之间建立了联系，通过一个框架可以找到另一个框架。

例如、张三框架中的住址、工资横向联系) 框架间除横向联系外，还可以建立纵向联系第一节第一节 知识表示的一般方法知识表示的一般方法师生员工框架教职工框架学生框架教师框架工人框架教师-1教师-N电子系学生框架 机械系学生框架框架的一个重要特性：继承性框架的一个重要特性：继承性第一节第一节 知识表示的一般方法知识表示的一般方法3 3 3 3、框架中槽的设置、框架中槽的设置、框架中槽的设置、框架中槽的设置(1) 充分表达事物各有关方面的属性(2) 充分表达相关事物间的各种联系(3) 系统预定义的一些槽名• ISA• AKO• Subclass• Instace• Part-of• infer• Passible-Reason第一节第一节 知识表示的一般方法知识表示的一般方法(4) (4) 系统预定义的附加过程系统预定义的附加过程系统预定义的附加过程系统预定义的附加过程 ①.if_needed过程：当需要槽值，但值不存在，且缺省值也没有设定时，执行该过程 ②.if_added过程：当需要在槽中增加槽值时，执行该过程 ③.if_removal过程：当要从槽中删除槽值时，执行该过程。

第一节第一节 知识表示的一般方法知识表示的一般方法4 4 4 4、框架系统中求解问题的基本过程、框架系统中求解问题的基本过程、框架系统中求解问题的基本过程、框架系统中求解问题的基本过程 (1)把问题用一个框架表示出来； (2)通过与知识库中已有的框架进行匹配，找出一个或几个可匹配的预选框架作为初步假设，并在此假设的引导下收集进一步的信息； (3)用某种评价方法对预选框架进行评价，决定是否接受第一节第一节 知识表示的一般方法知识表示的一般方法例、今天一次强度为里氏级的强烈地震袭击了下斯洛文尼亚地区，造成25人死亡和5亿美元的财产损失如需了解详细情况，可查询网站： 用框架表示该新闻用框架表示该新闻用框架表示该新闻用框架表示该新闻第一节第一节 知识表示的一般方法知识表示的一般方法框架名：<新闻-1> 新闻类型：自然灾害 新闻内容：<地震-1>框架名：<地震-1> 发生地区：下斯洛文尼亚 发生日期：今天 地震强度： 死亡人数：25 财产损失：5 详细情况：if_needed: Procedure Search_ 第一节第一节 知识表示的一般方法知识表示的一般方法六、语义网络六、语义网络1 1、语义网络的概念、语义网络的概念 语义网络是通过概念及其语义关系来表达知识的一种网络图。

从图论的观点看，即是一个“带标识的有向图”其中，节点表示各种事物、概念、属性、动作、状态、情况；弧表示各种语义联系例如：例如：猎狗狗是一种第一节第一节 知识表示的一般方法知识表示的一般方法2、知识的语义网络表示、知识的语义网络表示 任何一种知识表示方法都应具备两种功能： ①表示事实；②表示事实间的有关联系1)(1)用语义网络表示事实用语义网络表示事实猎狗狗动物是一种是一种吃肉能狩猎身上有毛有尾巴有生命能运动会吃第一节第一节 知识表示的一般方法知识表示的一般方法一本书张三给李四主体客体-1客体-2用动作作为节点的语义网络第一节第一节 知识表示的一般方法知识表示的一般方法人与会者ABC与或或男女年老年轻 在一些较复杂的事实和知识表示中，可以使用“并且”及“或者”等连接词 例如、“与会者有男、有女、有老、有少”第一节第一节 知识表示的一般方法知识表示的一般方法例子、“小信使”这只鸽子从春天到秋天占有一个窝小信使鸽子鸟占有窝鸟窝春天秋天时间是一只是一种是一种是是占有物开始于结束于占有者第一节第一节 知识表示的一般方法知识表示的一般方法(2)(2)用语义网络表示事物之间的关系用语义网络表示事物之间的关系• 分类关系 分类关系指事物间的类属关系，下层节点除可以继承、细化、补充上层节点的属性外，还可能出现变异情况。

第一节第一节 知识表示的一般方法知识表示的一般方法动物鸟鱼鹦鹉鸵鸟鲨鱼草鱼是一种是一种是一种是一种是一种是一种有羽毛会飞生活在水中会游泳不会飞善奔走会学人语 善鸣吃肉吃草分类关系分类关系第一节第一节 知识表示的一般方法知识表示的一般方法• 聚集关系 下层节点是上层节点的一部分或一个方面教学学生教师课程部分部分部分聚集关系第一节第一节 知识表示的一般方法知识表示的一般方法饥饿需进食推出推论关系• 推论关系 由一个概念可以推出另一个概念第一节第一节 知识表示的一般方法知识表示的一般方法• 时间、位置等关系例如、 胡途是思源公司的经理 该公司位于朱雀大街上 胡途今年35岁朱雀大街思源公司胡途经理35岁位于工作在是年龄第一节第一节 知识表示的一般方法知识表示的一般方法该公司有两个胡途该公司有两个胡途胡途胡1胡235思源公司20被聘者经理朱雀大街姓名姓名是受聘者是年龄年龄工作在位于第一节第一节 知识表示的一般方法知识表示的一般方法• 多元关系 郑州位于北京和西安之间位置关系郑州西安北京边界1边界2居中第一节第一节 知识表示的一般方法知识表示的一般方法(3)(3)具有量词的语义网络具有量词的语义网络①.对存在量词的处理方法 直接用“是一个”、“是一种”等语义联系表示。

②.对全称量词的处理方法 采用网络分区技术 基本思想：基本思想：基本思想：基本思想：把一个表示复杂知识的命题划分为若干个子命题，每一个子命题用一个较简单的语义网络表示----子空间，多个子空间构成一个大空间每个子空间可以看作是大空间中的一个节点----超节点，子空间之间用弧互相连接第一节第一节 知识表示的一般方法知识表示的一般方法例1：每个学生都背诵了一首唐诗GSg学生背诵唐诗srp是主体客体是是∀整个空间代表子空间全称量词表示任一个学生变量，表示某一次背诵变量，表示某一首唐诗第一节第一节 知识表示的一般方法知识表示的一般方法例2：每个学生都背诵了“静夜思”这首唐诗GSg学生背诵唐诗sr静夜思是主体客体是是∀第一节第一节 知识表示的一般方法知识表示的一般方法3 3 常用的语义联系常用的语义联系• A-Member-of• Gomposed-of• Have• Before,After,At• Located-on• Similar-to第一节第一节 知识表示的一般方法知识表示的一般方法4 语义网络系统中求解问题的基本过程语义网络系统中求解问题的基本过程(1)根据待解决的问题构造一个网络片段，其中某些节点或弧的标识是空的；(2)根据此网络片段在知识库中寻找可匹配的网络，以找出所需的信息；(3)当匹配时，则与询问处匹配的事实即是问题的解。

第一节第一节 知识表示的一般方法知识表示的一般方法例、设有如下事实： 赵云是一个学生 他在东方大学主修计算机课程 他入校的时间是1990年则语义网络知识库为：学生赵云教育教育1计算机科学大学东方大学1990时间ISARecipientISAAgentISABeginISAMajorISA第一节第一节 知识表示的一般方法知识表示的一般方法问题：赵云主修的课程？根据该问题构造语义网络片段：赵云教育？RecipientISAMajor教育1 根据该语义网络片段与知识库的匹配可知，主修的课程是计算机第一节第一节 知识表示的一般方法知识表示的一般方法七、七、Petri网表示法网表示法 构成Petri网的基本要素：位置、转换、标记yjyktipkPj 如果用 Pj和Pk分别表示产生式的前提和结论，ti表示规则强度，则可用Petri网表示规则第一节第一节 知识表示的一般方法知识表示的一般方法例如、例如、R1: IF d1 then d2 ( CF=0.85 )R2: IF d2 then d3 ( CF=0.8 )R3: IF d2 then d4 ( CF=0.8 )R4: IF d4 then d5 ( CF=0.9 )R5: IF d1 then d6 ( CF=0.9 )R6: IF d6 then d9 ( CF=0.93 )R7: IF d1 and d8 then d7 ( CF=0.85 )R8: IF d7 then d4 ( CF=0.9 )第一节第一节 知识表示的一般方法知识表示的一般方法d1d6d9d2d3d4d8d7d50.90.930.80.80.90.90.90.85第一节第一节 知识表示的一般方法知识表示的一般方法八、过程表示法八、过程表示法 将知识溶入控制中，推理与知识不分离。

例如，一个规则为IF Brother(x,y) and Father(x,z) then Uncle(y,z)用过程表示时为： BR( Uncle ?y ?z ) Goal(Brother ?x y ) Goal(Father x z )第一节第一节 知识表示的一般方法知识表示的一般方法九、脚本表示法九、脚本表示法 依赖理论 类似于电影剧本十、面向对象表示法十、面向对象表示法 用类表示第二节第二节 搜索策略搜索策略一、基本概念一、基本概念什么是搜索？什么是搜索？什么是搜索？什么是搜索？ AI所要解决的问题大部分是不良结构或非结构化的问题，对这样的问题一般不存在成熟的求解算法，只能利用已有的知识一步步地摸索前进 根据问题的实际情况不断寻找可利用的知识，从而构造出一条代价较少的推理路线，使问题得到圆满解决的过程称为搜索（1）求任一解路径的搜索策略（2）求最佳解路径的搜索策略（3）求与或图的搜索策略搜索策略搜索策略搜索策略搜索策略第二节第二节 搜索策略搜索策略 问题求解问题求解→搜索问题搜索问题→组合爆炸。

组合爆炸回溯法爬山法宽度优先法深度优先法限定范围搜索法好的优先法大英博物馆法分枝界限法动态规划法最佳图搜索一般与或图搜索法极小极大法α-β剪枝法启发式剪枝法一、回溯策略一、回溯策略例子，n = 3 的 0-1背包问题设： 背包容量：C = 30 货物重量：W={16,15,15} 货物价值：P ={45,25,25} 解空间： { (0,0,0),(0,1,0),(0,0,1),(1,0,0), (0,1,1),(1,0,1),(1,1,0),(1,1,1) }一、回溯策略一、回溯策略ABCDEFGHIJKLMNO10000000111110-1背包问题的解空间背包剩余容量=14货物重量=15是不可解节点一、回溯策略一、回溯策略基本思想：基本思想：基本思想：基本思想： 在包含问题的所有解的解空间中，按照深度优先的策略，从根节点出发搜索解空间树，当搜索到任一个节点时，总是先判断该节点是否包含问题的解，如果不包含，则跳过对该节点子树的搜索，逐层向其祖先节点回溯；否则，继续按深度优先的策略搜索其子树 算法体现出了递归特性。

回溯法有“通用的解题法”之称，是一个既带有系统性又带有跳跃性的搜索算法，用它可以系统地搜索一个问题的所有解或任一解一、回溯策略一、回溯策略回溯的递归过程 BACKTRACK(DATA)① IF TERM(DATA), RETURN NIL;② IF DEADEND(DATA), RETURN FAIL;③ RULES :=APPRULES(DATA);④ LOOP: IF NULL(RULES),RETURN FAIL;⑤ R:=FIRST(RULES);⑥ RULES :=TAIL(RULES);⑦ RDATA :=GEN(R,DATA);⑧ PATH :=BACKTRACK(RDATA);找到目标找到目标, ,则返回空表则返回空表是死节点是死节点, ,则返回则返回FAIL.FAIL.必须回溯必须回溯! !计算计算DATADATA的可应用规则集的可应用规则集, ,并按某种策略排序并按某种策略排序规则用完规则用完, ,返回返回FAIL.FAIL.必须回溯必须回溯! !取第一条规则取第一条规则删去头条规则删去头条规则, ,减少规减少规则长度则长度规则应用于当前状态规则应用于当前状态产生新状态产生新状态对新状态递归对新状态递归调用本过程调用本过程一、回溯策略一、回溯策略⑨ IF PATH=FAIL,GO LOOP;⑩ RETURN CONS(R,PATH);递归调用失败递归调用失败, ,则转移调则转移调用另一个规则用另一个规则过程返回解路径规则表过程返回解路径规则表一、回溯策略一、回溯策略例子，四皇后问题例子，四皇后问题一、回溯策略一、回溯策略描述描述: 综合数据库:DATA = L(表), L的元素{ij},1≤i,j≤4;DATA非空时,其表元素表示棋子所在的行和列。

因只有四个棋子，所以表元素的个数最多为4L={12,24,31,43}一、回溯策略一、回溯策略规则集： if 1≤i≤4 and Length DATA = i – 1 then Append (DATA (ij) ); ( 1≤j≤4 )共16条规则，每条规则表示满足条件下，在ij处放一个棋子一、回溯策略一、回溯策略（0）（11）（12）（13）（14）（21）（22） （23） （24）（21）（22） （23） （24）（31）（32） （33） （34）一、回溯策略一、回溯策略说明：说明： 运行时可能出现重复状态，使过程陷入死循环 一种解决方法：设置深度范围，当达到设置的深度时，进行回溯二、图搜索策略二、图搜索策略概念概念概念概念节点深度节点深度节点深度节点深度路径路径路径路径路径耗散值路径耗散值路径耗散值路径耗散值扩展一个节点扩展一个节点扩展一个节点扩展一个节点根节点的深度为0，其他节点的深度规定为父节点的深度加1，即dn+1=dn+1设一节点序列为(n0,n1,…,nk)，对i=1,2,…k，若节点ni-1都具有一个后继节点ni,则该节点序列称为从节点n0到节点nk的长度为k的一条路径。

设C(ni,nj)是节点ni到nj的耗散值，一条路径上的耗散值等于连接这条路径各节点间耗散值的总和后继节点操作符作用到节点上，生成其所有后继节点，并给出连接弧线的耗散值，这个过程称为扩展一个节点二、图搜索策略二、图搜索策略搜索过程中用到的两个数据结构：状态节点父节点状态节点父节点编号Open表Close表 Open表用于存放刚生成的节点，对于不同搜索策略，节点在Open表中的排列顺序是不同的 Close表用于存放将要扩展或已扩展的节点一般搜索过程一般搜索过程一般搜索过程一般搜索过程二、图搜索策略二、图搜索策略(1)把起始节点S0放入Open表，并建立只包含S0的图G2)检查Open表是否为空，若为空，问题无解，退出3)把Open表的第一个节点取出放入Close表，并记该节点为n4)考察节点n是否为目标节点，是，则求得解，退出5)扩展节点n，生成一组节点把其中不是节点n先辈的那些子节点记做集合M,并把这些子节点作为节点n的子节点加入图G二、图搜索策略二、图搜索策略(6)针对M中子节点的不同情况，分别进行处理： ①对那些未曾在G中出现过的M成员设置一个指向父节点的指针，并放入Open表。

②对那些先前已在G中出现过的M成员，确定是否需要修改它指向父节点的指针 ③对那些先前已在G中出现并且已经扩展了的M成员，确定是否需要修改其后继节点指向父节点的指针7)按某种策略对Open表的节点进行排序8)转第(2)步二、图搜索策略二、图搜索策略说明：说明：说明：说明：（1）上述过程具有具有通用性，其他的一些搜索策略都是它的一个特例各种搜索策略的主要区别是对Open表中节点排序的准则不同2）一个节点经过一个算符操作后一般只生成一个节点，但适用于一个节点的算符可能是多个，此时会生成多个子节点，这些子节点中可能有些是当前节点的父节点或祖先节点，此时不能把这些先辈节点作为当前的扩展节点，余下的子节点记作集合M，并加入图中二、图搜索策略二、图搜索策略（3）一个新生成的节点，它可能是第一次被生成的节点，也可能是先前已作为其他节点的后继节点生成过，当前又作为另一个节点的后继节点被再次生成 此时，它究竟应作为哪个节点的后继节点？一般的做法是，由开始节点到该节点的路径耗散值来决定，哪条路径的耗散值小，相应的节点就作为它的父节点4）通过搜索得到的图称为搜索图，由搜索图中的所有节点及反向指针所构成的集合是一棵树，称为搜索树。

二、图搜索策略二、图搜索策略（5）在搜索过程中，一旦某个被考察的节点是目标节点就得到了一个解6）如果在搜索中一直找不到目标节点，而且Open表中不在有可供扩展的节点，则搜索失败三、无信息图搜索过程三、无信息图搜索过程盲目搜索广度优先搜索深度优先搜索三、无信息图搜索过程三、无信息图搜索过程1、广度优先搜索 基本思想基本思想: :从初始节点开始，逐层进行搜索 广度优先搜索是完备的 做法做法: :Open表中的节点按进入的先后顺序排列，先进入的节点排在前面，后进入的排在后面三、无信息图搜索过程三、无信息图搜索过程2、深度优先搜索 基本思想基本思想: :从初始节点开始，在其子节点中选择一个节点进行考察，若不是目标节点，则再在该子节点的子节点中进行考察，并如此向下搜索 深度优先搜索不是完备的 做法做法: :把新扩展的子节点放在Open表中的首部四、启发式图搜索过程四、启发式图搜索过程 启发式搜索是利用问题拥有的启发信息来引导搜索，达到减少搜索范围、降低问题复杂度的目的 这类和具体问题相关的信息称为启发信息四、启发式图搜索过程四、启发式图搜索过程一般形式为： f(x) = g(x)+h(x) 其中，g(x)是从初始节点到节点x的实际代价；h(x)是x到目标节点的代价估计。

启发式信息的评价（评价函数）启发式信息的评价（评价函数）四、启发式图搜索过程四、启发式图搜索过程例、设有如下结构的移动将牌游戏：黑 黑 黑 白 白 白 空游戏规则：①.当将牌移入相邻空位置时，费用为1个单位；②.一个将牌最多可跳过两个将牌进入空位置，其费用等于跳过的将牌数加1要求：把所有黑色将牌移动到白色将牌的右边四、启发式图搜索过程四、启发式图搜索过程评估函数的设计：评估函数的设计： 由于白色左边的黑色越少，则越接近目标，因此，可以用白色左边的黑色将牌个数作为h(x)即： h(x)=3×(每个白色将牌左边的黑色将牌个数的总和)四、启发式图搜索过程四、启发式图搜索过程1、启发式搜索算法A 利用评价函数f(x) = g(x)+h(x)来排序Open表中的节点顺序的图搜索算法称为算法A算法过程：算法过程：① Open :=(s), f(s) = g(s)+h(s)② Loop: IF Open=() Then Exit(FAIL)③ n: = First(Open);④ IF Goal(n) Then Exit(Success)⑤ Remove(n,Open), Add(n,Closed)四、启发式图搜索过程四、启发式图搜索过程⑥ Expand(n)→{mi}, 计算f(n,mi) = g(n,mi)+h(mi)。

g(n,mi)是从s通过n到mi的耗散值； f(n,mi)是从s通过n、mi到目标节点耗散值的估计n Add(mi,Open)，标记mi到n的指针n IF f(n,mk)

根据目标节点L返回到S的指针，可得到解路径： S(4),B(4),E(5),I(5),K(5),L(5)四、启发式图搜索过程四、启发式图搜索过程2、爬山法、爬山法算法过程：算法过程：① n :=s;② Loop: IF Goal(n) Then Exit(Success);③ Expand (n)→{mi},计算h(mi), Nextn := m(min h(mi)的节点);④ IF h(n)

动态规划原理指出：求s→t的最短路径，对某一个中间点I，只要考虑 s 到 I 中具有最小耗散值这一条路径即可，其余s 到 I 的路径是多余的，不必加以考虑四、启发式图搜索过程四、启发式图搜索过程算法过程：算法过程：① QUEUE :=(s-s),g(s)=0;② Loop: IF QUEUE=( ) Then Exit(Fail);③ Path :=First(QUEUE), n:=Last(Path);④ IF Goal(n) Then Exit(Success);⑤ Expand(n)→{mi},计算g(mi) = g(n,mi) Remove(s-n,QUEUE),Add(s-mi,QUEUE)；⑥ 若QUEUE中有多条到达某个公共节点的路径，则只保留耗散值最小的路径，并重新排序；⑦ Go Loop;用动态规划求解最短路问题用动态规划求解最短路问题开始： ( S(0) )Sg=01) ( A(3),D(4) )g=3g=4ADBDg=8g=72) ( D(4),B(7),D(8) )×2)‘ ( D(4),B(7) )AEg=9g=6×3) ( E(6),B(7) )BFg=11g=10×4) ( B(7),F(10) )CEg=11g=12×5) ( F(10),C(11) )Tg=136)( C(11),T(13) ) – 包含目标节点，结束四、启发式图搜索过程四、启发式图搜索过程5、最佳图搜索算法、最佳图搜索算法 A*在一般搜索算法中，如果满足下列限制： ①. Open表中的节点按f(x)排序； ②. g(x)是对g*(x)的估计,g(x)>0; ③. h(x)是h*(x)的下界，即有，h(x)≤h*(x)则称为A*算法。

其中，g*(x)是从节点S0到节点x的最小代价；h*(x)是从节点x到目标的路径代价，恒有g(x)≥g*(x)，而且在算法执行过程中随着更多信息的获得，g(x)的值呈下降趋势h(x)的确定依赖于具体问题领域的启发性信息，其中,h(x)≤h*(x)限制十分重要，它可保证A*算法能找到最优解四、启发式图搜索过程四、启发式图搜索过程 可纳性含义：对于可解状态空间图，如果一个搜索算法能在有限步内终止，并且能找到最优解，则称该搜索算法是可纳的A A* *算法的可纳性算法的可纳性四、启发式图搜索过程四、启发式图搜索过程 定理定理1：对有限图，如果从初始节点s到目标节点t有路径存在，则算法A一定成功结束 证明： ①. 因为图有解，则令 n0=s,n1,…,nk=t，表示某一解路径 ②. 从 nk 开始逆向逐个检测该序列的节点,找到出现在Open表中的节点ni,即ni∈Open， ni+1Open，（特别的，在开始时，n0=s）四、启发式图搜索过程四、启发式图搜索过程 ③. 由于ni在Open表中，则必定在第6步被扩展，且ni+1被加到Open表中，因此，在Open表空之前， ni+1被处理过。

④. 若ni+1是目标节点，则搜索成功，否则它被加入到Open表中，这两种情况都与搜索失败的假设矛盾 由于由于A*是是A的特例，因此它具有的特例，因此它具有A的所有性质的所有性质四、启发式图搜索过程四、启发式图搜索过程 引理引理1：：对无限图，若有从初始节点s到目标节点t的一条路径，则A*不结束时，在Open中即使最小的一个f值也将增到任意大，或有f(n)>f*(s) 证明： ①. 设 e 是A*生成的搜索图中各条边的最小耗散值，d*(xn)是从开始节点s到节点xn的最短路径长度，则有： g*(xn)≥ d*(xn)×e四、启发式图搜索过程四、启发式图搜索过程 ②. 因为，g(xn)≥ g*(xn) 所以，g(xn) ≥ d*(xn)×e 又因为，h(xn) ≥0，f(xn) ≥ g(xn) 故得到：f(xn) ≥ d*(xn)×e 由于A*算法不终止，随着搜索的进行d*(xn)会无限增大，从而f(xn)也无限增大 设 M = f*(s)/e，M是一个定数，所以搜索到一定程度时，会有d*(xn)>M，或d*(xn)/M >1，则 f(xn)≥ d*(xn)×e= d*(xn) × f*(s)/M > f*(s)。

四、启发式图搜索过程四、启发式图搜索过程引理引理2：A*结束前，Open表中必存在 f(n)≤f*(s)的节点定理定理2：：对无限图，如果从初始节点s到目标节点t有路径存在，则算法A*一定成功结束推论：推论：Open表上任一具有f(n)≤f*(s)的节点n，最终都将被A*选作为扩展的节点四、启发式图搜索过程四、启发式图搜索过程 定理定理3：：若存在开始节点s到目标节点t的路径，则A*必能找到最佳解结束 证明： ①.由定理1、2知A*一定会找到一个目标节点结束 ②.设找到的目标节点为t，而s→t不是最佳路径，即 f(t) = g(t) > f*(s) 而根据引理2知道，结束前Open表上有节点n，且处在最佳路径上，并有f(n)≤f*(s)

h(x)的值越大，表明它携带的启发信息越多，搜索时扩展的节点越少，搜索的效率越高A A* *算法的最优性算法的最优性四、启发式图搜索过程四、启发式图搜索过程定理定理4：：有两个A*算法A1和A2，如果A2比A1有较多的启发信息，则在具有一条从s到t的隐图上，搜索结束时，由A2所扩展的节点，也必定由A1所扩展，即A1所扩展的节点数至少和A2一样多四、启发式图搜索过程四、启发式图搜索过程7、、A*算法的改进算法的改进 在A*算法中，每当要扩展一个节点时，都要先检查其子节点是否已在Open表或Closed表中，有时还需要调整指向父节点的指针，这就增加了搜索的代价如果对启发函数h(x)加上单调性限制，就可减少检查和调整的工作量，从而减少搜索代价h(x)h(x)的单调性限制的单调性限制四、启发式图搜索过程四、启发式图搜索过程单调性：单调性： 如果h(x)满足下列两个条件： (1) h(Sg) = 0 (2) 设xj是节点xi的任意子节点，则有 h(xi) – h(xj) ≤C( xi, xj )其中， Sg 是目标节点； C( xi, xj )是节点 xi到其子节点 xj 代价。

四、启发式图搜索过程四、启发式图搜索过程 将，h(xi) – h(xj) ≤C( xi, xj ) 改为， h(xi) ≤ h(xj) + C( xi, xj )则说明：节点xi到目标节点最优费用的估计不会超过从xi 到其子节点 xj 的边代价加上从xj到目标节点最优代价的估计ijCijSgh(i)h(j)四、启发式图搜索过程四、启发式图搜索过程定理定理定理定理5 5：若h(n)满足单调性限制条件，则A*扩展了节点n之后，就已经找到了到达节点n的最佳路径即若A*选n来扩展，在单调限制条件下有，g(n) = g*(n)定理定理定理定理6 6：若h(n)满足单调性限制条件，则由A*所扩展的节点序列，其f值是非递减的 根据定理根据定理5，在应用，在应用A*算法时，在第算法时，在第6步可不步可不必进行节点的指针修正操作，因此改善了必进行节点的指针修正操作，因此改善了A*的搜的搜索效率四、启发式图搜索过程四、启发式图搜索过程8、A*算法应用举例A*算法的理论意义：算法的理论意义：给出了求解最佳解的条件h(x)≤h*(x)在实际应用中：在实际应用中： 对给定的问题如果有解，则函数h*(x)是客观存在的，但在问题的求解过程不可能明确知道，因此，对实际问题能不能使所定义的启发函数满足下界范围？如果困难很大，那么A*算法的应用就会受到限制。

四、启发式图搜索过程四、启发式图搜索过程例1、八数码问题28316475初始状态目标状态12384765四、启发式图搜索过程四、启发式图搜索过程 第一种启发函数：每个状态与目标状态相比错位的将牌个数 存在的问题：没有考虑从棋盘格局中可以得到的信息因为它没有把将牌必须要移动的距离纳入考虑 第二种启发函数：对错位的将牌必须要移动的距离求和每张牌移动一个方格为一个单位） 存在的问题：没有认识到颠倒牌的难度2 1 3847 5 6 第三种启发函数：对每个直接颠倒乘以一个小的数字2 8 31 6 47 62 8 3147 6 52 8 31 6 47 5560354600错位将牌错位将牌错位将牌错位将牌的距离和的距离和2×直接直接颠倒数颠倒数应用于八数码游戏的三种启发函数应用于八数码游戏的三种启发函数四、启发式图搜索过程四、启发式图搜索过程启发函数扩展节点数生成节点数h(n)=0h(n)=W(n)h(n)=P(n)2646136511 八数码问题没有启发信息和应用第一、二种启发信息后，A*算法求得最佳解时所扩展和生成的节点数据四、启发式图搜索过程四、启发式图搜索过程例2、迷宫问题入口入口出口出口(1,1)(4,4) 用平面坐标表示通路，即综合数据库定义为: (x,y)，1≤x,y ≤4问题归结为求(1,1)→(4,4)的最短路问题。

四、启发式图搜索过程四、启发式图搜索过程规则集： R1：if (x,y) then (x+1,y)；向右 R2：if (x,y) then (x,y-1)； 向下 R3：if (x,y) then (x-1,y)； 向左 R4：if (x,y) then (x,y+1)；向上(1,1)(1,2)(1,3)(2,3)(2,4)(1,4)(3,4)(3,3)(2,2)(3,2)(2,1)(3,1)(4,1)(4,2)(4,3)(4,4)状态空间图四、启发式图搜索过程四、启发式图搜索过程使用使用A*算法求最短路径算法求最短路径：设搜索一步的代价为1，则定义 h(n) = |Xg – xn|+ |Yg – yn|其中(Xg,Yg)为目标节点的坐标，(xn,yn)为节点n的坐标，显然有h(n)≤h*(n) 取g(n) = d(n)，则有f(n)=d(n)+h(n) 再设当Open表中f相等时，按深度优先排序(1,1)(2,3)(2,4)(2,2)(1,4)(3,4)(3,3)(4,3)(4,4)(3,2)(4,2)h=6f=6h=4f=8h=2f=6h=3f=8h=1f=6h=2f=8h=1f=8h=0f=8h=3f=10h=2f=10迷宫问题启发式搜索图迷宫问题启发式搜索图h=3f=6四、启发式图搜索过程四、启发式图搜索过程9、评价函数的启发能力(1) 启发能力越强，一般来说，搜索效率越高。

2) f(x) = g(x) + h(x)，关键是h(x)的设计 一般可以综合考虑各个因素，例如，对八数码问题：f(x) = g(x)+P(n)+3S(n)(3) 通过乘以一个系数加大h(x)在f(x)中的比例例如，在移动将牌游戏中黑 黑 黑 白 白 白 空h(x)=3×(每个白色将牌左边的黑色将牌个数的总和)四、启发式图搜索过程四、启发式图搜索过程启发式搜索的说明启发式搜索的说明：1.在启发式搜索中，最难的是启发函数的设计设计启发函数目的是使用从单一状态描述中可以得到有限信息来做出智能的决策2.要设计出好的启发式函数离不开经验、直觉和判断3.启发难免存在错误，所以搜索算法可能被误导到某个不能通往目标的路径五、搜索算法分析五、搜索算法分析1、弱方法 AI求解的问题是非结构化问题，一般无法用直接求解的方法找到答案，因此通常要借助于搜索技术 一些问题可能是NP问题，状态空间会出现组合爆炸，因此要使用问题相关的启发信息来指导搜索，以减少搜索空间的状态，但启发函数的设计是困难的，因此不能保证在一些情况下总可以找到解，或最优的解因此，称为“弱方法”如果引入极强的启发信息，则搜索效率会大幅提高。

例如，用黄金分割求函数的极值五、搜索算法分析五、搜索算法分析 问题：设状态是实数域[a,b]上的实连续函数f，f在该区间内是单极值函数，求该目标函数在何处取得极值及其大小 用黄金分割求解的基本思想：在区间[0,1]间，取两个点来考虑问题，如果f(0.382)较优，则剪去[0.618,1]区段； 若f(0.618)较优，则剪去[0,0.382]区段然后依新规则继续下去，直到函数在某一点取得极值算法过程算法过程(2) LOOP1: If x3 = x4 Then Exit(Success) If f(x3)>f(x4) Then Go Loop2; If f(x3)

五、搜索算法分析五、搜索算法分析2、搜索算法分析算法分析的目的执行效果如何？找到解的优劣如何？计算机科学中，主要强调对算计算机科学中，主要强调对算法进行数学分析，如果数学分法进行数学分析，如果数学分析遇到困难，则采取运行一组析遇到困难，则采取运行一组经过精心挑选的问题，再对根经过精心挑选的问题，再对根据结果对其进行统计分析据结果对其进行统计分析在人工智能中，由于解决的问题比较在人工智能中，由于解决的问题比较复杂，则通常采取的途径是，将算法复杂，则通常采取的途径是，将算法用某种语言实现，然后运行某个智能用某种语言实现，然后运行某个智能问题的典型实例，并观察其表现行为问题的典型实例，并观察其表现行为来进行分析比较来进行分析比较五、搜索算法分析五、搜索算法分析 搜索过程最基本的一个分析是对深度D,分支因数为B的一棵完全树的节点数(为BD)进行讨论 当搜索过程成指数增长时，则无实用意义基本指标：（1）外显率P = LT 其中，L为从初始节点到目标节点的路径长度；T为整个搜索过程中所生成的节点总数 显然P越小表示搜索过程中产生的无用节点越多，搜索效率越低五、搜索算法分析五、搜索算法分析(2)有效分支因数 有效分支因数定义为： B + B2 + …… + BL = T其中，B是有效分支因数，它表示在整个搜索过程中每个有效节点平均生成的子节点数目；L为路径长度；T为节点总数。

当 B = 1时，有 1 + 12 + …… + 1L = L = T此时所生成的节点最少，搜索效率最高五、搜索算法分析五、搜索算法分析 目前优于穷举法的若干方法的三种情况： (1) 能保证找到的解与穷举法所得的结果一样好，但耗时较少 (2)对问题的一些实例，耗费时间和穷举法一样，但对另一些实例则较穷举法好 (3)得到的解比穷举法的结果差问题是要在给定的时间内找到解，这个解与最佳解有多大的差距五、搜索算法分析五、搜索算法分析人工智能求解问题的一个途径：人工智能求解问题的一个途径：企图以多项式时间求解NP完全问题实现的两种选择寻求平均角度看执行效率较快的一些算法寻求近似算法，使能在可接受的时间内获得满意的解答五、搜索算法分析五、搜索算法分析对分枝界限法的评述：对分枝界限法的评述： (1)各种选择按完美排序进行时，最好情况下其性能有多好 (2)各种选择按不良排序进行时，最差情况下其性能有多好 (3)各种选择按某种随机过程的排序进行时，平均情况下其性能有多好 (4)各种选择按应用于一组特定问题的启发函数排序进行时，在实际中，平均角度看其性能如何。