第三章 - 12
内容
启发式搜索
3.0 简介 3.1 启发式搜索算法
3.1.0 局部择优搜索 3.1.1 全局择优搜索（A算法） 3.1.2 A*算法 3.1.3 其它启发式搜索算法 3.2 应用举例
2
第三章 - 13
启发式搜索
3.1.0 局部择优搜索
（1）把初始节点S0放入 Open表中，f(S0)=g(S0)+h(S0) ; （2）如果Open表为空，则问题无解，失败退出； （3）把Open表的第一个节点取出放入Closed表，并记该节点
2.A*算法的性质 3.启发函数h（n）的评价方法 4.A*算法复杂性 5.A*算法的改进
第三章 - 35
1.A*算法定义
启发式搜索
如果A算法使用的评估函数h（n）满足： h（n）≤h*（n）
那么该算法称为A*算法。
例如： 8数码问题 h1(n) = “不在位”的将牌数 h2(n) = 将牌“不在位”的距离和
第三章 - 8
3.0 简介
启发式搜索
顶角方格有三种 胜利路线
中央方格有四种 胜利路线
边方格有两种 胜利路线
第三章 - 9
3.0 简介
启发式搜索
启发式搜索基本思想：
定义一个评价函数f，对当前的搜索状态进行评估， 找出一个最有希望的节点来扩展。
第三章 - 10
3.0 简介
启发式搜索
评价函数 f(n) = g(n) + h(n)
第三章 - 18
内容
启发式搜索
3.0 简介 3.1 启发式搜索算法
3.1.0 局部择优搜索 3.1.1 全局择优搜索（A算法） 3.1.2 A*算法 3.1.3 其它启发式搜索算法 3.2 应用举例
3
第三章 - 19
3.1.1 A算法
A算法也称为最佳优先搜索 (best-first search)
Zerind(374)
第三章 - 16
启发式搜索
3.1.0 局部择优搜索
Sibiu
Arad
Arad (366)
Fagaras Oradea (176) (380)
Sibiu
Rimnicu Vilcea (193)
Arad
Fagaras
Sibiu (253)
Bucharest (0)
Yet not optimal (see Arad, Sibiu, Rimnicu Vilcea, Pitesti)
启发式搜索
2. A*算法的性质—定理1
定理1
对有限图，如果从初始节点s到目标节点t有路径存 在，则算法A一定成功结束。
引理1.2 A*结束前，OPEN表中必存在f(n)≤f*(s)。
存在一个节点n，n在最佳路径上。 f(n) = g(n) + h(n)
为n； （4）考察节点n是否为目标节点。若是，则找到了问题的解，
成功退出； （5）若节点n不可扩展，则转第（2）步； （6）扩展节点n，生成其子节点ni(i=1，2，…)，计算每一个
子节点的估价值f（ni）（i=1，2，…），并按估价值 从小到大的顺序依次放入Open表的首部，并为每一个子 节点设置指向父节点的指针，然后转第（2）步。
Open表中；
（7）根据各节点的估价函数值，对Onen表中的全部节点按从
小到大的顺序重新进行排序；
（8）转第（2）步。
第三章 - 21
3.1.1 A算法
启发式搜索
分析：
如果取估价函数f(n)=g（n），则它将退化为代价树 的广度优先搜索。
如果取估价函数f(n)=d（n），则它将退化为广度优 先搜索。
弱： 一般导致工作量加大，极限情况下变为盲目搜索，但可 能可以找到最优解。
第三章 - 5
【例1】
3.0 简介
启发式搜索
第三章 - 6
3.0 简介
启发式搜索
【例2】 通过对称抵消后的九宫游戏状态空间的前三层
对一个假象状态空间的启发式搜索
1
第三章 - 7
3.0 简介
启发式搜索
假定采用如下“启发”裁减九宫游戏状态空间。 移动到×方胜利路线最多的状态
f(n)：评价函数 h(n)：启发函数
符号的意义 f*(n)=g*(n)+h*(n)
f*(n)：从s经过n到g的最短路径的耗散值。 g*(n)：从s到n的最短路径的耗散值。 h*(n)：从n到g的最短路径的耗散值。
注意： g(n)、h(n)、f(n)分别是g*(n)、h*(n)、f*(n)的估 计值。
4
第三章 - 25
3.1.1 A算法
【例2】八数码问题。
定义评价函数：f(n) = g(n) + h(n)
启发式搜索
第三章 - 26
3.1.1 A算法
启发式搜索
启发1： 数出每个状态与目标状态相比错位的牌数。
启发2： 对错位的牌必须要移动的距离求和。
启发3： 对每个“直接颠倒”乘以一个小的数字。
对于一个处于有限资源下的系统来说，智能 体现在明智地选择下一步该做什么………
第三章 - 3
内容
启发式搜索
3.0 简介 3.1 启发式搜索算法
3.1.0 局部择优搜索 3.1.1 全局择优搜索（A算法） 3.1.2 A*算法 3.1.3 其它启发式搜索算法 3.2 应用举例
第三章 - 17
启发式搜索
3.1.0 局部择优搜索
分析：
深度优先搜索、代价树的深度优先搜索以及局部优 先搜索都是以子节点作为考察范围，但选择节点的 标准不一样。
对于局部择优搜索算法：
如果取估价函数f（ n）= g（n），则它将退化为代价 树的深度优先搜索。
如果取估价函数f（n）= d（n），则它将退化为深度优 先搜索。 因此，深度优先搜索和代价树的深度优先搜索是局部择优 搜索的两个特例。
3 n:=FIRST(OPEN);
4 IF GOAL(n) THEN EXIT(SUCCESS);
5 REMOVE(n, OPEN), ADD(n, CLOSED);
6 EXPAND(n) → {mi},
计算f(n, mi):=g(n, mi)+h(mi);
① ADD(mj, OPEN), 标记mj到n的指针； ② IF f(n, mk)<f(mk) THEN f(mk):=f(n, mk),
第三章 - 2
启发式搜索
——纽厄尔和西蒙（Newell and Simon) ，1976年度ACM
图灵奖获奖演说
当问题和问题空间确定后，符号系统所要解决 的任务就是如何使用有限的处理资源来产生可能 解，直到发现一个可以通过（问题所定义）检验 的解。
如果符号系统可以对可能解的产生顺序进行 某种控制，并对这个产生顺序加以组织以使高可 能性的解出现，那么这是非常理想的。如果符号 系统成功地做到了这一点，那么它便展示出了智 能。
启发式搜索
2. A*算法的性质—定理1
定理1
对有限图，如果从初始节点s到目标节点t有路径存 在，则算法A一定成功结束。
引理1.1
对无限图，若有从初始节点s到目标节点t的路径， 则A*不结束时，在OPEN表中即使最小的一个f值也将 增到任意大，或有f(n)>f*(s)。第三章 - 396源自11B(5)
A(1)
8
G 目标
OPEN表
s(10) A(7) B(8) C(9) B(8) C(9) G(14) A(5) C(9) G(14) C(9) G(12) B(7) G(12) A(4) G(12) G(11)
CLOSED表
s(10) A(7) s(10)
B(8) s(10) A(5) B(8) s(10) C(9) A(5) s(10) B(7) C(9) s(10) A(4) B(7) C(9) s(10)
问题状态：
用列表L指示，L的元素就是皇后在棋盘中的位置 ij(1≤i，j≤4)；
按自上而下的次序在棋盘的4行中放置皇后；
空表L指示初始状态；当表L包含4个满足约束的皇后位 置时，到达目标状态；
当皇后位置发生冲突时，意味着进入不合法状态（失败 状态）。
第三章 - 32
思考题
设计四皇后问题的启发函数h(n)
第三章 - 11
3.0 简介
启发式搜索
对启发式搜索算法，可根据搜索过程中选择扩展 节点的范围，将其分为： 局部择优搜索算法
局部最佳优先搜索算法（Local-Best-First-Search） 全局择优搜索算法
最佳优先搜索算法（Best-First-Search） A算法 A*算法
搜索的每一步都利用估价 函数f（n）对Open表中的 所有节点进行排序。 f（n）=g（n）＋h（n）
启发式搜索
第三章 - 20
3.1.1 A算法
启发式搜索
（1）把初始节点S0放入Open表中，f(S0)=g（S0）＋h（S0）；
对
（2）如果Open表为空，则问题无解，失败退出；
一
（3）把Open表的第一个节点取出放入Closed表，并记该节点
因此，广度优先搜索和代价树的广度优先搜索是全局择 优搜索的两个特例。
第三章 - 22
3.1.1 A算法
回顾一般图搜索
启发式搜索
n
a
…...
…...
…... b
mk
mj
ml
…...
…...
第三章 - 23
3.1.1 A算法
1 OPEN:=(s), f(s):=g(s)+h(s);