- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
2.3 应用智能的搜索
2.3.2 登山法和最佳优先搜索 算法5 登山法 第1步: 设初始节点为n; 第2步: 如果节点n为目标节点，则求解成功; 第3步: 扩展节点n得到子节点的集合; 第4步: 从予节点的集合中，选取h(n’)为最小的节点 n’ 。如果h(n) < h(n’) ，则求解以失败告终; 第5步: 设n’为新的n ，返回第2步。
基于搜索问题的求解(2) 第二讲 基于搜索问题的求解
华北电力大学控制科学与工程学院 白 焰
2.3 应用智能的搜索
2.3.1启发式搜索
思考： 数码和15数码魔方 思考：在8 数码和 数码魔方 中，各存在着多少种 不同的状态？ 不同的状态？ 回答： 回答： 9!= 362880； ； 16！=20922789888000 ！ 问题：空间巨大、 问题：空间巨大、难以求解 方法： 方法：启发式搜索
2.3 应用智能的搜索
2.3.1启发式搜索 不过，这种启发式的方法， 虽然在多数情况下是有用的， 但是未必都是正确的。例如在 右图所示的迷宫中，对节点G 4 进行扩展时。存在着两个可以 进行扩展的候选节点，即 E=(1,1)和H=(3,0)。这时， h(E) = |3–1|+|3–1|=4； h(H) = |3– 3|+|3–0|=3 ，虽然可以说H一 1 方离目标节点近，但这却不是 F 正确的选择 。 A 1 C 1 E 1 G 2 H D 2 2 B
2.3.2 登山法和最佳优先搜索 (1) F O:{[G,5]} C:{F} G (3) O:{[E,4]} C:{F,G,H} (2) O:{[H,3],[E,4]} C:{F,G} E
A 2 B 1 4 C 2 D 1 E 1 F 1 G 2 H
H
(4) O:{ [A,2],[C,3],[D,3]} C:{F,G,H,E} (5) O:{ [B,0],[C,3],[D,3]} C:{F,G,H,E,A} (6) O:{ [C,3],[D,3]} C:{F,G,H,E,A}
2.3 应用智能的搜索
2.3.2 登山法和最佳优先搜索 在这个算法中，如果把h(n)看作是到达山顶(目标节 点)的距离。则因为h(n)的值是向着减小的方向进行搜索。 所以看起来恰似进行登山时的情况。不过当这样的节点 不再存在时，就会以失败而告终。即当登山途中遇到小 的山峰时，就会产生不能由此继续完成原来进程的问题。 在图2-9中的节点G以后，若选择H，则此后就会发生走 投无路的情况。这种情况可以说与前面介绍过的随机搜 索中产生的问题是相同的。因此，人们试探地构成了加 进OPEN表和CLOSED表的算法。这里对于前面的算法4， 可以只根据g(n)的替代量h(n)的值，对OPEN表进行分类。 这时的搜索过程如下图所示。
2.3.3 A*算法
为什么用最佳优先搜索算法不能得到最优解呢?当考 虑这个问题时，我们发现，这是因为忽略了始于初始节 点的代价造成的。因此，节点n的评价值可以定义如下: f(n)=g(n)+h(n) 这里， g(n)是从初始节点到节点n的路径代价的估计值， h(n)是从节点n到目标节点的路径代价的估计值。设f(n)为 评价函数，则能满足h(n)的估计值是实际的最优值h*(n)的 下界函数（估计值小于实际最优值）这一条件的搜索算 法，称为A*算法 。
2.4 博弈树的搜索
A B (a) C B (b) C A (e) C A B (h)
B A B A C C (c) (d) (f) (g) (i) (j)
2.4 博弈树的搜索
在图中所示的博弈树 中，棋手在这时的最好棋 a 0 步可以判断如下。图中a， c，d，f，g，i，j 为 MAX 节 点 ， b，e，h 为 MIN 节 b －∞ e －∞ h 0 点。对于节点b，棋手选 b 择d(评估值为－∞ )，对于 c d f g i j 节点e，选择节点g（评估 0 0 －∞ 2 －∞ 2 值为－∞ )。对于节点h， 选择节点j(评估值为0)。 因此，对于节点a，显然 选择h(评估值为0)是最好 的棋步。
2.3.3 A*算法 算法6 A *算法 第1步: 将初始节点ni和它的代价f(ni)=g(ni)放入OPEN表中; 第2步: 把OPEN表申最前面的节点取出来，并设其为n。如 果OPEN表是空的，则求解以失败告终； 第3步: 扩展节点，得到子节点的集合，把n放入CLOSED表; 第4步: 对于子节点的集合中不包含在CLOSED表中的节点n‘ ， 配置指向n的指针。计算g(n’)= g(n)+c(n, n‘) ，并且 放 入OPEN表中。但是在n已经放入OPEN表的情况下， 当新的g(n’)比估的值小时，则应予以更新，指针也 应 予以更换。在n‘己经放入CLOSED表中的情况下，当 新的g(n’)比估的值小时，则应从CLOSED表中取出， 放入OPEN表，并且更换指针。对于OPEN表， 按照 评价值递增的顺序进行分类; 第5步: 返回到第2步
2.3.3 A*算法
(1) F O:{[G,6]} C:{F} (2) G O:{[E,6],[H,6]} C:{F,G} E (3) (4) O:{[H,6],[C,6],[A,8]} H O:{ [C,6],[A,8]} C:{F,G,E} C:{F,G,E,H} A A 2 B 1 4 C 2 D 1 E 1 F 1 G 2 H
能否获得最优解 能 不能 能
8 6 7
注*：在A*算法中， h(n)≤h*(n)是能够获得最优解 的必要条件。不能满足这个条件的算法称为A算法。
2.4 博弈树的搜索
在象棋和国际象棋等这些由两人进行的比赛中，两个 棋手通过交替地走棋，进行比赛。在这种2人比赛中，确定 下一步的走棋问题。也可以用图搜索的方法进行处理。虽 然2人比赛的最终结果。可能是赢、输和平局中的一种，但 是作为棋手，当然要选择自己能够取胜的棋术。另一方面， 对于下一步的棋局，对手要选择使我方变成输局的棋术， 对于对手的这种选择，我方棋手是无法干预的，这也是2人 比赛的一种特征。
A
B
2.3.2 登山法和最佳优先搜索
这种算法称为最佳优先搜索。最佳优先搜索不必担 心以前的代价，只需选择能使将来的代价预测值变成最 小的路径。这种算法可以保证能够找到解，而且它可以 在许多场合中高效地运行。如果把这种搜索与均一代价 搜索进行比较。则可知节点C和D此时不会被扩展，而且 显然只通过6次扩展就可以求出解来。不过由这个结果也 可以发现，,6],[D,8]} O:{ [B,6],[D,8]} C:{F,G,E,H,C} C:{F,G,E,H,C,A} D B (7) O:{[D,8]} C:{F,G,E,H,C,A}
C
2.3.3 A*算法 均一代价搜索、最佳优先搜索与A*算法的比较
扩展次数 均一代价搜索 最佳优先搜索 A*算法
2.3 应用智能的搜索
2.3.1启发式搜索 因此，尽可能地减小搜索范围的方法变得越来越重要。 为此，出现了应用启发式(应用已有知识)的方法。这种搜 索方法被称为启发式搜索。例如在迷宫问题中，如果知道 目标状态的位置，那么就应该考虑采取尽可能靠近该位置 的搜索策略。针对该问题的一种方法，是当设定目标节点 的坐标为(xg, yg)时。利用从节点 n= (x, y)到目标节点的曼哈 顿距离h(n) = |xg–x|+|yg–y|，对能使这个距离值变小的那种 节点进行扩展。
2.4 博弈树的搜索
α-β方法 (5,∞) A (－∞,5) B (－∞, 2) C j M 1 N ? O ?
(5,∞) c (6,∞) d (2,∞) i H 3 I 5 J 6 K ? L 2
计算机战胜国际象棋世界冠军
1981年，贝尔研究所的两位研究人员开发出了名人级的计 算机，进而于1988年，卡内基梅隆大学的五位研究生开发出了 作为"DeepBlue"前身的"DeepThough" 。这种计算机达到了超大 规模名人(仅次于世界冠军的名人)级水平。"DeepThought"1989 年时向世界冠军卡斯帕洛夫进行过挑战。那时该计算机取得了 0胜2负的战绩，从而以完败告终。而作为它的后继者的 “DeepBlue”机，于1996年2月在美国费城，再次向卡斯帕洛夫 发起挑战，并进行了6盘比赛。在这次比赛中，DeepBlue初战 告捷，但是最终卡斯帕洛夫反败为胜，结果DeepBlue以“1胜3 负2平”的战绩败下阵来。然而1997年5月在纽约曼哈顿的世界 贸易中心，又进行了第三次比赛，DeepBlue终于以2胜1负3平 的结果赢得了对卡斯帕洛夫的胜利。这次比赛的详情，可以从 下列网站中查到: http://www.research.ibm·com/deepblue·
