状态空间搜索策略84179.pptx

《状态空间搜索策略84179.pptx》由会员分享，可在线阅读，更多相关《状态空间搜索策略84179.pptx（46页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、三、搜索策略三、搜索策略3.1 图搜索策略3.2 盲目搜索3.3 启发式搜索 从问题表示到问题的解决，有一个求解的过程。常见的AI问题求解技术有两种，即“搜索”（Search）和“推理”（Reasoning）方法。逻辑推理，是通过构造一个逻辑系统，由它可以从已有的断言（公理）推导出新的断言。并用逻辑形式语言描述的一组公理来表达问题域。用这种方法来解决问题就是通过推理来积聚越来越多的断言，直到获得问题的解答。虽然问题求解可通过搜索方法，也可用逻辑推理，但二者的侧重点是不一样的。前者着重于寻求问题解答的过程，而后者强调前提（初始）问题空间（公理集合）与问题解答间连接的逻辑正确性。或者简单地讲，搜索

2、着重于发现（Discovery），而推理强调证明（Proof）。搜索在状态图中寻找目标或路径的基本方法从初始节点，沿着与之相连的边，寻找目标节点的过程搜索树搜索过程中经过的节点和边，按照原图的连接关系，便形成一个树形的有向图盲目搜索无向导搜索/穷举式搜索从初始节点，沿连接边逐一考察各个节点，或反向进行启发式(heuristic)搜索利用“启发性信息”引导的搜索启发式信息是与问题有关的有利于尽快找到问题解的信息或知识3.1 图搜索策略 图（状态图）搜索控制策略一种在图中寻找路径的方法。图中每个节点对应一个状态，每条连线对应一个操作符。这些节点和连线(即状态与操作符)又分别由产生式系统的数据库和规

3、则来标记。求得把一个数据库变换为另一数据库的规则序列问题就等价于求得图中的一条路径问题。图组成节点有向边图分类或图（直接图、状态图）与或图图搜索过程图图（状态图）搜索策略CLOSED 表：用来记录考察过的节点对树形搜索，存储的是搜索树对线式搜索，存储的是折线OPEN表：记录待考察的节点排序方式不同，对应的搜索算法不同节点父节点编号编号节点父节点编号CLOSED表OPEN表开始把S放入OPEN表OPEN表为空表？把第一个节点(n)从OPEN表移至CLOSED表n为目标节点吗？把n的后继节点放入OPEN表的末端，提供返回节点n的指针修改指针方向重排OPEN表失败成功图3.1 图搜索过程框图是是否否

4、3.2 盲目搜索 特点：不需重排OPEN表种类：宽度优先、深度优先、等代价搜索等。3.2.1 宽度优先搜索v 定义 以接近起始节点的程度逐层扩展节点的搜索方法。v 特点：一种高代价搜索，但若有解存在，则必能找到它。v 算法广度（宽度）优先搜索广度（宽度）优先搜索 (Breadth-first search,BFS)优先在同一级节点中考察，只有当同一级节点考察完毕之后，才考察下一级节点自顶向下一层一层逐渐生成的宽度优先搜索算法宽度优先搜索算法步1：把初始节点So放入OPEN表中。步2：若OPEN表为空,则搜索失败,退出。步3：取OPEN表中前面第一个节点N放在CLOSED表中,并冠以顺序编号n。

5、步4：若目标节点Sg=N,则搜索成功,结束。步5：若N不可扩展,则转步2。步6：扩展N,将mj子节点配上指向N的指针依次放入OPEN表尾部,转步2。注解注解：1.OPEN表是一个队列2.CLOSED表是一个顺序表，表中各节点按顺序标号，正在被考察的节点在表中编号最大3.如果问题有解，目标点Sg必出现在OPEN表中，算法结束4.根据返回指针，在CLOSED表中回溯，得到求解路径开始把S放入OPEN表OPEN表为空表？把第一个节点(n)从OPEN表移至CLOSED表是否有后继节点为目标节点？扩展n，把n的后继节点放入OPEN表的末端，提供返回节点n的指针失败成功图3.2 宽度优先算法框图是否是否

6、例子八数码难题（8-puzzle problem）1238456712384567（目标状态）规定：将牌移入空格的顺序为：从空格左边开始顺时针旋转。不许斜向移动，也不返回先辈节点。从图可见，要扩展26个节点，共生成46个节点之后才求得解（目标节点）。1238456712384123845674123856712 38412384567123845671238456767891011121312384567567567112384567123845671238456712384567234513456123845671238456712384567123845671 23845672324252

7、6271236782212384567123845671 238456712 384567123845671238456712384567141516171819202112384567图3.4 八数码难题的宽度优先搜索树宽度优先搜索算法宽度优先搜索算法宽度优先/横向搜索优点策略是完备的如果有解，肯定找到解，且找到的解是最优解(最短路径)缺点效率低节点深度：根节点深度=0其它节点深度=父节点深度+13.2.2 深度优先搜索3.2.2 深度优先搜索v 定义 首先扩展最新产生的(即最深的)节点。v 算法 防止搜索过程沿着无益的路径扩展下去，往往给出一个节点扩展的最大深度深度界限。与宽度优先搜索算法

8、最根本的不同在于：将扩展的后继节点放在OPEN表的前端。（算法框图见教材）深度优先搜索深度优先搜索（Depth-first search，DFS）在搜索树的每一层始终只扩展一个子结点，不断地向纵深前进直到不能再前进（到达叶子结点或深度限制），才从当前节点返回上一级节点，沿另一方向又继续前进从树根开始一枝一枝逐渐生成的路径节点序列为(n0,n1,nk)对于i=1,k，若节点ni-1具有一个后继节点ni，该序列称为从n0到nk的路径n0nkn1nk-1n3n2深度优先搜索算法深度优先搜索算法纵向搜索缺点如果一个有解的问题树可能有无穷分支，如果误入无穷分支（即深度无限），则不可能找到目标节点策略不是

9、完备的找到的解是不一定最优解最短路径)3.2.3 等代价搜索v 定义 是宽度优先搜索的一种推广，不是沿着等长度路径断层进行扩展，而是沿着等代价路径断层进行扩展。搜索树中每条连接弧线上的有关代价,表示时间、距离等花费。v 算法 若所有连接弧线具有相等代价，则简化为宽度优先搜索算法。开始把S放入OPEN表OPEN表为空表？把具有最小g(i)值的节点i从OPEN表移至CLOSED表是否有后继节点为目标节点？失败成功图3.2 等代价搜索算法框图是否是否S是否目标节点？是成功扩展i，计算其后继节点j的g(j)，并把后继节点放入OPEN表否令g(s)=0国际象棋对弈程序国际象棋对弈程序:深蓝深蓝开发者开发

10、者:IBM:IBM 的的Murry Campbell,Feng-Hsiung Hsu Murry Campbell,Feng-Hsiung Hsu 和和Joseph HoaneJoseph Hoane采用采用3030个个IBM RS/6000IBM RS/6000处理器来运行软件搜索处理器来运行软件搜索使用使用480480个定制个定制VLSIVLSI国际象棋处理器执行生成行棋的功能国际象棋处理器执行生成行棋的功能树的最后几层的树的最后几层的”硬件搜索硬件搜索”以及对叶节点的评价以及对叶节点的评价.每秒平均搜索每秒平均搜索12.612.6亿种走法，峰值时每秒钟搜索亿种走法，峰值时每秒钟搜索333

11、3亿个节点亿个节点.每走一步至多每走一步至多能够预先计算能够预先计算300300亿种个棋局亿种个棋局,常规搜索深度是常规搜索深度是1414步步.机器的核心算法是使用调换表的标准迭代深入机器的核心算法是使用调换表的标准迭代深入-搜索搜索,而且对关键的点具而且对关键的点具备产生超越搜索深度的扩展能力备产生超越搜索深度的扩展能力,在某些情况下可以达到在某些情况下可以达到4040层的深度层的深度.评价函数采用了超过评价函数采用了超过80008000个特征个特征;使用一本有使用一本有40004000个棋局的个棋局的”开局手册开局手册”以及以及一个存有一个存有7070万个大师级比赛棋谱的数据库万个大师级比

12、赛棋谱的数据库;使用一个大型残局数据库保存已使用一个大型残局数据库保存已解决的棋局解决的棋局.Videohttp:/ Deep Blue 15 yearshttp:/ 卡斯帕罗夫http:/ Windows 8http:/ Kinect问题的提出问题的提出穷举算法可以解决状态空间很小的简单问题大空间无法胜任：组合爆炸组合爆炸64阶梵塔：节点：364=0.94*1030理论最短路径：264-1=2*1019博弈一字棋：9！=3.6*105西洋棋：1078国际象棋：10120（极限并行速度10-104秒/步，需1016年）围棋：107613.3 启发式搜索启发性信息启发性信息按其用途划分,启发性信

13、息可分为以下三类：用于扩展节点的选择,即用于决定应先扩展哪一个节点,以免盲目扩展。用于生成节点的选择,即用于决定应生成哪些后续节点,以免盲目地生成过多无用节点。用于删除节点的选择,即用于决定应删除哪些无用节点,以免造成进一步的时空浪费。3.3 启发式搜索特点：重排OPEN表，选择最有希望的节点加以扩展种类：有序搜索、A*算法等3.3.1 启发式搜索策略和估价函数v盲目搜索可能带来组合爆炸v启发式信息 用来加速搜索过程的有关问题领域的特征信息。启发函数启发函数启发函数是用来估计搜索树上节点x与目标节点Sg接近程度的一种函数,通常记为h(x)定义一个节点到目标节点的某种距离或差异的度量一个节点处于

14、最佳路径上的概率根据经验的主观打分估价函数 为获得某些节点“希望”的启发信息，提供一个评定侯选扩展节点的方法，以便确定哪个节点最有可能在通向目标的最佳路径上。f(n)表示节点n的估价函数值 应用节点“希望”程度（估价函数值）重排OPEN表3.3.2 有序搜索v实质 选择OPEN表上具有最小f值的节点作为下一个要扩展的节点。开始把S放入OPEN表，计算估价函数 f(s)OPEN表为空表？选取OPEN表中f值最小的节点i放入CLOSED表i为目标节点吗？扩展i，得后继节点j，计算f(j)，提供返回节点i的指针，利用f(j)对OPEN表重新排序，调整亲子关系及指针失败成功图3.9 有序搜索算法框图是

15、否是否v算法 例子八数码难题（8-puzzle problem）12384567（目标状态）12384567（初始状态）八数码难题的有序搜索树见下图：123845671238456712384567（4）（6）（6）123845671238456712384567（6）（5）（5）1238456712 384567（5）（7）1238456712384567（6）（7）12384567（5）813245671 2384567（5）（7）图3.10 八数码难题的有序搜索树123846（4）7启发式搜索利用问题拥有的启发信息来引导搜索，达到减少搜索范围，降低问题复杂度的目的在保证找到最佳解的情况下

16、，尽可能减少搜索范围，提高搜索效率启发信息强降低搜索工作量，但可能导致找不到最优解弱产生式系统在找到一条路径之前将扩展过多的节点，一般导致工作量加大极限情况下盲目搜索，但可能可以找到最优解3.3.3 A*算法A*算法评价函数评价函数 f(n)=g(n)+h(n)n是被评价的结点f(n)评价函数从s经过n到g的路径的耗散值g(n)代价函数从s到n的路径的耗散值h(n)启发函数从n到g的路径的耗散值3.3.3 A*算法估价函数的定义：对节点n定义f f*(n)=g*(n)+h*(n)(n)=g*(n)+h*(n),表示从S开始约束通过节点n的一条最佳路径的代价。希望估价函数f 定义为：f(n)=g

17、(n)+h(n)g是g*的估计，h是h*的估计A*算法的定义：定义定义1 1 在GRAPHSEARCH过程中，如果第8步的重排OPEN表是依据f(x)=g(x)+h(x)进行的，则称该过程为A算法。定定义义2 2 在A算法中，如果对所有的x存在h(x)h*(x),则称h(x)为h*(x)的下界，它表示某种偏于保守的估计。定定义义3 3 采用h*(x)的下界h(x)为启发函数的A算法，称为A*算法。当h=0时，A*算法就变为有序搜索算法。评价函数的计算g（n）根据已搜索的结果，按照从初始结点s到结点n的路径，计算其耗散值即可g(n)对g*(n)作出估计，有g(n)g*(n)h(n)依赖于启发信息

18、，称为启发函数启发函数对未来扩展的方向作出估计f(n)按f(n)递增的顺序来排列OPEN表的节点，优先扩展f(n)值小的节点，体现了好的优先搜索思想3.3.3 A*算法八数码2 8 31 6 47 51 2 38 47 6 5初始状态八数码八数码评价函数f(n)=g(n)+h(n)g(n)：从初始节点到当前节点的耗散值h(n)：当前节点“不在位”的将牌数2 8 31 6 47 51 2 3457 6 8h(n)=42 8 31 6 47 52 8 31 47 6 52 8 31 6 4 7 52 8 31 6 47 52 31 8 47 6 52 8 3 1 47 6 52 8 31 47 6

19、 52 8 37 1 4 6 5 8 32 1 47 6 5 2 31 8 47 6 52 31 8 47 6 51 2 3 8 47 6 51 2 38 47 6 51 2 37 8 4 6 5S(4)A(6)B(4)C(6)D(5)E(5)F(6)G(6)H(7)I(5)J(7)K(5)L(5)M(7)124356g=0h=4f=4g=1h=5f=6g=1h=3f=4g=1h=5f=6g=2h=3f=5g=2h=3f=5g=2h=4f=6g=3h=2f=5g=3h=4f=7g=3h=4f=7g=3h=3f=6g=4h=2f=6g=5h=0f=5g=5h=2f=77目标A*算法A*算法算法在

20、A算法中，如果满足条件h(n)h*(n)h*(n)是从节点n到目标节点g的最小代价最小代价,即最佳路径上的实际代价则A算法称为A*算法 A*算法h单调限制单调限制 一个启发函数h，如果对所有节点ni和nj,满足h(ni)-h(nj)c(ni,nj)h(g)=0则称h是单调单调的。其中:nj是ni的子节点g是目标节点h(ni)ninjh(nj)c(ni,nj)gA*算法h单调限制单调限制性质A*扩展了节点n之后，就已经找到了到达节点n的最佳路径。即：当A*选n扩展时，有g(n)=g*(n)由A*所扩展的节点序列其f值是非递减的 A*算法8数码问题：h为“不在位”的将牌数 1 不在位在位h(ni)-h(nj)=0 不在位不在位 -1 在位不在位h(g)=0c(ni,nj)=1 满足单调的条件。(nj为ni的后继节点)VideoA starhttp:/