《3知情搜索概要》由会员分享，可在线阅读，更多相关《3知情搜索概要（31页珍藏版）》请在金锄头文库上搜索。
1、搜索：知情搜索,概要,知情搜索与启发方式 第一种尝试：最佳优先贪婪搜索 A*算法 最佳性 启发函数的条件 完全性 局限性、空间复杂性等议题 扩展,再看搜索,评价函数f(s)：经由s的最廉价路径的估计代价 最佳优先搜索：选择f值最小的结点来优先扩展 算法： 对每个状态s，储存一个值f(s)。 选择f最低的状态做下一步扩展。 插入它的后续态。 如果仔细地选择f，则可以最终找到最低代价序列。,实例： UCS(等代价搜索)：f(A)=g(A)=当前从START到A的最短路径的总代价。 把等待扩展的状态存储在一个优先队列中，以便有效地查询f的最小值。 最佳就是保证找到最小代价序列。,问题：对于任何给定状
2、态离终态有多远，无指导。 解决：设计一个估计某一状态与终态之间距离的函数。,最乐观的猜测：如果A比B更接近于GOAL，则它是一个更有希望的扩展状态。,启发函数,对该搜索问题，h是一个启发函数。 h(s)=从s到GOAL的最短路径的代价估值。 仅通过当前问题中的状态及转换，是不能计算出h的。如果可能的话，则已经知道最佳路径了。 h是建立在关于该问题的外部知识上的。因此，称为知情搜索。 问题： h的典型实例？ 怎么使用h？ 什么是h的必要性质？,启发函数实例,h(s)=到GOAL的直线距离。 从s出发的直线距离比从s出发的短。因此，s成为最佳路径的机会更大。,终点,起点,启发函数实例,怎样来定义h
3、(s)?,1,5,3,2,6,4,8,7,1,2,4,7,5,3,6,8,起点,终点,第一种尝试：最佳优先贪婪搜索（GBFS）,最简单的启发函数：总是选择h最小的结点来扩展，即f(s)=h(s)。 初始化PQ 插入(START, h(START)偶对到PQ中 while (PQ不空，且不包含终态) 从PQ中弹出h值最小的状态s 对在succs(s)中的所有s 如果s 不在PQ中，且未访问过 插入(s, h(s )偶对到PQ中,问题,在该场合下，能找到的答案是什么？ 虽然采用合理的启发函数，但贪婪搜索不是最佳的。,解决问题的尝试,g(s)仅是从START到s的代价。 h(s)估算从s到GOAL得
4、代价。 关键点：g(s)+h(s)估算从START经由s到达GOAL的最廉价路径的总代价。 A*算法,A*能解决该问题吗？,(START,4) (A,5) (f(A)=h(A)+g(A)=3+g(START)+cost(START,A)=3+0+2) (B,5),(C,7)（C与返回指针A,START被放在队列中） (f(B)=h(B)+g(B)=2+g(A)+cost(A,B)=2+2+1) (f(C)=h(C)+g(C)=1+g(A)+cost(A,C)=1+2+4) (C,5)（发现f(C)的一个较低值及返回指针B,A,START） (f(C)=h(C)+g(C)=1+g(B)+cost
5、(B,C)=1+3+1) (GOAL,6),与A*有关的议题,终止条件 状态重访 算法 最佳性 避免状态重访 选择好的启发式方法 降低空间开销,A*终止条件,当GOAL从队列中弹出时，就停止！,队列： (B,4),(A,8) (C,4),(A,8) (D,4),(A,8) (A,8),(GOAL,10),在访问经由A的路径前，就已遇上GOAL。出现此问题是由于每步利用的仅是到达目标的路径代价的一个估值,重访状态,队列： (START,8) (B,4),(A,8) (A,8),(C,10) (C,9.5)重访,在PQ中 (D,3.5) (GOAL,9.5),重访一个已扩展状态。 怎样更新它的优先
6、级？,重访状态,队列： (START,8) (B,4),(A,8) (C,4),(A,8) (D,4),(A,8) (A,8),(GOAL,10) (C,3.5),(GOAL,10)重访 (D,3.5),(GOAL,10)重访 (GOAL,9.5)重访,在PQ中,重访一个已扩展状态。 （另一个例子）,从队列中弹出f(s)值最小的状态s if s=GOAL return SUCCESS else 扩展s： 对在succs(s)中的所有s： f=g(s )+h(s )=g(s)+cost(s,s )+h(s ) if (s 之前没见到过 or s 之前以f(s )f 被扩展过 or s 在PQ中，
7、且f(s )f ) 升级或插入(s, 新的代价f )偶对到PQ previous(s )s else 不处理s（这是因为它已被访问过， 并且它的当前路径代价f(s )仍是START 到s 路径代价的最低值）,A*算法中的内循环体,什么条件下A*是最佳的？,问题：h(.)是到终态路径代价的一个差的估计。,(START,6) (GOAL,3),(A,8) 最终路径： START,GOAL，并且代价为3。,允许的启发方式,定义h*(s)=从s到目标的真实最小代价。 如果h(s)h*(s)对所有状态s成立，则h是允许的。 也即，一个允许的启发方式决不高估到达目标的代价，而是乐观地估计到目标的代价。 A
8、*保证找到最佳路径，如果h是允许的。,一致（单调）启发方式,h(s)cost(s,s)+h(s) 这类三角形不等式表明：路径代价总是增加的，因此仅需要扩展结点一次。,(s,h(s) (GOAL, cost(s,GOAL), (s, cost(s,s)+h(s) 最终路径： s,GOAL,从队列中弹出f(s)值最小的状态s if s=GOAL return SUCCESS else 扩展s： 对在succs(s)中的所有s： f=g(s)+h(s)=g(s)+cost(s,s)+h(s) if (s 之前没见到过 or s 之前以f(s)f 被扩展过 or 如果h是一致性的 s 在PQ中，且f(
9、s)f ) 升级或插入(s, 新的代价f )偶对到PQ previous(s)s else 不处理s（这是因为它已被访问过， 并且它的当前路径代价f(s)仍是START 到s 路径代价的最低值）,A*算法中的内循环体,实例,机器人导航问题：最短路径的长度至少是s到GOAL的距离。因此，直线距离是一个允许的启发方式。 拼图怎样处理？,终点,起点,终点,h(s)?,h1=错放的拼块数： h1(s)=7 h2=Manhattan距离： h2(s)=4+2+2+2+2+0+3+3=18,5,4,2,1,3,8,6,7,2,3,1,6,4,8,7,5,起点,终点,启发方式比较,h1=错放的拼块数 h2=
10、Manhattan距离,IDS有重复扩展状态的倾向。因此，比较而言，会高估A*的性能。 已扩展状态数没有包括访问队列所需的log()时间。,启发方式比较,h1(s)=7 h2(s)= 4+2+2+2+2+0+3+3=18 h2比h1大，同时，采用h2的A*似乎更有效。 在这两个观察之间存在一种联系吗？ 如果对所有的s，有h2(s)h1(s)，则h2支配h1。 对任何两个启发方式h2与h1： 如果h2支配h1，则采用h2的A*更有效（扩展状态更少）。 因为hh*，所以较大的h应是对真实路径代价的一个更好的近似。,起点,终点,实例,最大的h（=h*）： (B,10),(A,11),(C,12) (
11、GOAL,10),(A,11),(C,12) 最终路径： START,B,GOAL,较小的h： (B,2),(A,3),(C,12) (A,3),(C,12),(GOAL,10) (GOAL,10),(C,12) 最终路径： START,B,GOAL,实例,最小的h（UCS搜索）： (A,1),(B,1),(C,1) (B,1),(C,1),(GOAL,11) (C,1),(GOAL,10) (GOAL,10) 最终路径： START,B,GOAL,A*最佳解的性质: 以f(s) = g(s) + h(s)为次序来扩展状态。 C*为最佳路径的代价，A*搜索： 将扩展f(s) C*的任何结点 特
12、例： h(s) = 0，f(s) = g(s) UCS搜索，需扩展所有当前态的后续态 h(s) = h*(s)，f(s) = g(s) + h*(s)，只扩展一个当前态的最佳后续态,局限性,计算：在最坏的场合，可能需要检测所有的状态，即O(N)。 好消息：A*是最有效的。即，对一个给定的h，不存在扩展结点较少的其它最佳算法。 坏消息：存储也可能会较大，即O(N)。,迭代加深搜索（IDS）,需要使DFS最佳。 IDS： 执行DFS来搜索长度仅为1的路径（如果路径长度1，则DFS停止）。 如果该搜索无答案，则重新执行DFS来搜索长度2的路径。 如果该搜索无答案，则重新执行DFS来搜索长度3的路径。
13、 继续直到找到一个答案为止。,实例： 迭代加深A*（IDA*）,与迭代加深DFS相同的思路。不同之处是，用f(s)而不是转换次数来控制搜索的深度。 实例，假设整数代价： 执行DFS，在f(s)0的s状态处停止。如果已到达目标，则停止。 执行DFS，在f(s)1的s状态处停止。如果已到达目标，则停止。 执行DFS，在f(s)2的s状态处停止。如果已到达目标，则停止。 每次对f的限制递增1来继续执行。 完全（假设采用能避免循环的DFS）。 最佳。 在计算代价上，比A*较昂贵。 与DFS类似，存储为L级。,总结,知情搜索与启发方式 第一种尝试：最佳优先贪婪搜索 A*算法 最佳性 启发函数的条件 完全性 局限性、空间复杂性等议题 扩展,
