15
2.4 A*算法
3、启发式搜索策略 有关具体问题领域的信息常常可以用来简化搜索。 一个比较灵活(但代价也较大)的利用启发信息的方法 是应用某些准则来重新排列每一步OPEN表中所有节 点的顺序。然后，搜索就可能沿着某个被认为是最 有希望的边缘区段向外扩展。应用这种排序过程， 需要某些估算节点“希望”的量度，这种量度叫做 估价函数(evalution function)。
2020/5/10
10
2.1 知识表示的一般方法
过程 问题求解的算法 过程式表示就是将有关某一问题领域的知 识，连同如何使用这些知识的方法，均隐式 地表达为一个求解问题的过程。它所给出的 是事物的一些客观规律，表达的是如何求解 问题。知识的描述形式就是程序，所有信息 均隐含在程序之中。
参见本科人工智能教材
11
2.2 图搜索策略
图搜索控制策略 一种在图中寻找路径的方法。 图中每个节点对应一个状态，每条连线对应 一个操作符。这些节点和连线(即状态与操 作符)又分别由产生式系统的数据库和规则 来标记。求得把一个数据库变换为另一数据 库的规则序列问题就等价于求得图中的一条 路径问题。
图搜索过程图
12
2.2 图 搜 索 策 略
第二章 知识表示与推理
2.1 知识表示的一般方法 2.2 图搜索策略 2.3 一般搜索与推理技术 2.4 A*算法 2.5 消解原理 2.6 规则演义系统 2.7 产生式系统 2.8 系统组织技术
2.1 知识表示的一般方法
一般计算机科学 数据结构 + 算法
人工智能 (知识表示+搜索) + 推理
4
2.1 知识表示的一般方法
状态空间表示举例 猴子与香蕉的问题
5
2.1 知识表示的一般方法
状态空间表示举例 猴子与香蕉的问题 状态空间表示 用四元组（W，X，Y，Z）
其中：
W-猴子的水平位置； X－当猴子在箱子顶上时取X=1；否则取X=0； Y－箱子的水平位置； Z-当猴子摘到香蕉时取Z=1；否则取z=0。
启发式搜索
特点：重排OPEN表，选择最有希望的节点加 以扩展；估价函数
种类：有序搜索、A*算法、 AO*算法等
14
2.4 A*算法
1、为什么需要启发式搜索 盲目搜索效率低，耗费过多的计算空间与时间， 这是组合爆炸的一种表现形式。
2、定义 进行搜索技术一般需要某些有关具体问题领域 的特性的信息，把此种信息叫做启发信息。 利用启发信息的搜索方法叫做启发式搜索方 法。
件发生的前提条件。 (2)角色 用来表示在剧本所描述的事
件中可能出现的有关人物的一些槽。 (3)道具 这是用来表示在剧本所描述
的事件中可能出现的有关物体的一些槽。 (4)场景 描述事件发生的真实顺序，
可以由多个场景组成，每个场景又可以是 其它的剧本。
(5)结果 给出在剧本所描述的事件发 生以后通常所产生的结果。
算符
(1) goto(U)猴子走到水平位置U； (2) pushbox(V)猴子把箱子推到水平位置V； (3) climbbox猴子爬上箱顶； (4) grasp猴子摘到香蕉。
6
2.1 知识表示的一般方法
问题规约法 大问题化为若干小问题 本原问题
梵塔难题 归约过程 例如3个盘子： （1）圆盘1和2移动至柱子B的双圆盘难题； （2）圆盘3移动至柱子C的单圆盘难题； （3）圆盘1和2移动至柱子C的双圆盘难题。
开始
把S放入OPEN表
是 OPEN表为空表？
否 把第一个节点(n)从OPEN表移至CLOSED表
失败
n为目标节点吗？
是
否
把n的后继节点放入OPEN表中， 提供返回节点n的指针
成功
非n的祖先
修改指针方向
重排OPEN表
已经在OPEN表或 者CLOSED表
13
2.3 一般搜索与推理技术
盲目搜索
特点：不需重排OPEN表 种类：宽度优先、深度优先、等代价搜索等。
2020/5/10
7
2.1 知识表示的一般方法
谓词逻辑法 合式公式 消解算法(归结)
8
2.1 知识表示的一般方法
语义网络法 结点表示概念 弧表示关系
框架法 槽、侧面层次结构 框架可以嵌套框架
9
2.1 知识表示的一般方法
剧本 场景 角色 事件
一个剧本一般由以下各部分组成： (1)开场条件 给出在剧本中描述的事
是依据f(x)=g(x)+h(x)进行的，则称该过程为A算法。
定义2 在A算法中，如果对所有的x存在h(x)≤h*(x),则称h(x)为
h*(x)的下界，它表示某种偏于保守的估计。
定义3 采用h*(x)的下界h(x)为启发函数的A算法，称为A*算法。
当g=0时，A*算法就变为有序搜索算法；h=0时，A*算法就变为 等代价搜索算法。
17
2.4 A*算法
估价函数的定义：
对节点n定义f*(n)=g*(n)+h*(n) ,表示从S开始约束通过 节点n的一条最佳路径的代价。 希望估价函数f 定义为：f(n)=g(n)+h(n)
—— g是g*的估计 ，h是h*的估计Fra bibliotek A*算法的定义：
定义1 在GRAPHSEARCH过程中，如果第8步的重排OPEN表
2020/5/10
2
2.1 知识表示的一般方法
问题求解：规约、推断、决策、规划、 常识推理、定理证明等等
问题求解技术主要是两个方面： 问题的表示：数据结构。同一个问题 可以有不同的表示。 求解的方法：算法。不同的算法可以 得出不同的结果。
2020/5/10
3
2.1 知识表示的一般方法
状态空间法 一组状态（state）： {S1, S2,…,Sn} 一套算符（operator）：fk : Si→Sj 开始状态和结束状态：S0，{Se} 一组状态：各种棋局 一套算符：走棋规则 开始棋局和结束棋局
16
2.4 A*算法
4、估价函数 为获得某些节点“希望”的启发信息，提供一个评定侯
选扩展节点的方法，以便确定哪个节点最有可能在通 向目标的最佳路径上 。
f(n)——表示节点n的估价函数值 建立估价函数的一般方法：试图确定一个处在最佳路径
上的节点的概率；提出任意节点与目标集之间的距离 量度或差别量度；或者在棋盘式的博弈和难题中根据 棋局的某些特点来决定棋局的得分数。这些特点被认 为与向目标节点前进一步的希望程度有关。