状态空间搜索策略

三、搜索策略3.1图搜索策略3.2盲目搜索3.3启发式搜索从问题表示到问题的解决，有一个求解的过程。常见的AI问题求解技术有两种，即“搜索”（Search）和“推理”（Reasoning）方法。逻辑推理，是通过构造一个逻辑系统，由它可以从已有的断言（公理）推导出新的断言。并用逻辑形式语言描述的一组公理来表达问题域。用这种方法来解决问题就是通过推理来积聚越来越多的断言，直到获得问题的解答。虽然问题求解可通过搜索方法，也可用逻辑推理，但二者的侧重点是不一样的。前者着重于寻求问题解答的过程，而后者强调前提（初始）问题空间（公理集合）与问题解答间连接的逻辑正确性。或者简单地讲，搜索着重于发现（Discovery），而推理强调证明（Proof）。•搜索–在状态图中寻找目标或路径的基本方法–从初始节点，沿着与之相连的边，寻找目标节点的过程•搜索树–搜索过程中经过的节点和边，按照原图的连接关系，便形成一个树形的有向图•盲目搜索–无向导搜索/穷举式搜索–从初始节点，沿连接边逐一考察各个节点，或反向进行•启发式(heuristic)搜索–利用“启发性信息”引导的搜索–启发式信息是与问题有关的有利于尽快找到问题解的信息或知识3.1图搜索策略•图（状态图）搜索控制策略一种在图中寻找路径的方法。图中每个节点对应一个状态，每条连线对应一个操作符。这些节点和连线(即状态与操作符)又分别由产生式系统的数据库和规则来标记。求得把一个数据库变换为另一数据库的规则序列问题就等价于求得图中的一条路径问题。•图组成–节点–有向边•图分类–或图（直接图、状态图）–与或图图搜索过程图•图（状态图）搜索策略–CLOSED表：用来记录考察过的节点•对树形搜索，存储的是搜索树•对线式搜索，存储的是折线–OPEN表：记录待考察的节点•排序方式不同，对应的搜索算法不同节点父节点编号编号节点父节点编号CLOSED表OPEN表开始把S放入OPEN表OPEN表为空表？把第一个节点(n)从OPEN表移至CLOSED表n为目标节点吗？把n的后继节点放入OPEN表的末端，提供返回节点n的指针修改指针方向重排OPEN表失败成功图3.1图搜索过程框图是是否否3.2盲目搜索•特点：不需重排OPEN表•种类：宽度优先、深度优先、等代价搜索等。3.2.1宽度优先搜索定义以接近起始节点的程度逐层扩展节点的搜索方法。特点：一种高代价搜索，但若有解存在，则必能找到它。算法•广度（宽度）优先搜索(Breadth-firstsearch,BFS)–优先在同一级节点中考察，只有当同一级节点考察完毕之后，才考察下一级节点–自顶向下一层一层逐渐生成的•宽度优先搜索算法步1：把初始节点So放入OPEN表中。步2：若OPEN表为空,则搜索失败,退出。步3：取OPEN表中前面第一个节点N放在CLOSED表中,并冠以顺序编号n。步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宽度优先算法框图是否是否•例子八数码难题（8-puzzleproblem）1238456712384567（目标状态）规定：将牌移入空格的顺序为：从空格左边开始顺时针旋转。不许斜向移动，也不返回先辈节点。从图可见，要扩展26个节点，共生成46个节点之后才求得解（目标节点）。123845671238412384567412385671238412384567123845671238456767891011121312384567567567112384567123845671238456712384567234513456123845671238456712384567123845671238456723242526271236782212384567123845671238456712384567123845671238456712384567141516171819202112384567图3.4八数码难题的宽度优先搜索树•宽度优先搜索算法–宽度优先/横向搜索–优点•策略是完备的•如果有解，肯定找到解，且找到的解是最优解(最短路径)–缺点•效率低•节点深度：–根节点深度=0–其它节点深度=父节点深度+13.2.2深度优先搜索3.2.2深度优先搜索定义首先扩展最新产生的(即最深的)节点。算法防止搜索过程沿着无益的路径扩展下去，往往给出一个节点扩展的最大深度——深度界限。与宽度优先搜索算法最根本的不同在于：将扩展的后继节点放在OPEN表的前端。（算法框图见教材）•深度优先搜索（Depth-firstsearch，DFS）–在搜索树的每一层始终只扩展一个子结点，不断地向纵深前进–直到不能再前进（到达叶子结点或深度限制），才从当前节点返回上一级节点，沿另一方向又继续前进–从树根开始一枝一枝逐渐生成的•路径–节点序列为(n0,n1,…,nk)–对于i=1,…,k，若节点ni-1具有一个后继节点ni，–该序列称为从n0到nk的路径n0nkn1nk-1n3n2•深度优先搜索算法–纵向搜索–缺点•如果一个有解的问题树可能有无穷分支，如果误入无穷分支（即深度无限），则不可能找到目标节点•策略不是完备的•找到的解是不一定最优解最短路径)3.2.3等代价搜索定义是宽度优先搜索的一种推广，不是沿着等长度路径断层进行扩展，而是沿着等代价路径断层进行扩展。搜索树中每条连接弧线上的有关代价,表示时间、距离等花费。算法若所有连接弧线具有相等代价，则简化为宽度优先搜索算法。开始把S放入OPEN表OPEN表为空表？把具有最小g(i)值的节点i从OPEN表移至CLOSED表是否有后继节点为目标节点？失败成功图3.2等代价搜索算法框图是否是否S是否目标节点？是成功扩展i，计算其后继节点j的g(j)，并把后继节点放入OPEN表否令g(s)=0国际象棋对弈程序:深蓝开发者:IBM的MurryCampbell,Feng-HsiungHsu和JosephHoane•采用30个IBMRS/6000处理器来运行软件搜索•使用480个定制VLSI国际象棋处理器执行生成行棋的功能﹑树的最后几层的”硬件搜索”以及对叶节点的评价.•每秒平均搜索12.6亿种走法，峰值时每秒钟搜索33亿个节点.每走一步至多能够预先计算300亿种个棋局,常规搜索深度是14步.•机器的核心算法是使用调换表的标准迭代深入α-β搜索,而且对关键的点具备产生超越搜索深度的扩展能力,在某些情况下可以达到40层的深度.•评价函数采用了超过8000个特征;使用一本有4000个棋局的”开局手册”以及一个存有70万个大师级比赛棋谱的数据库;使用一个大型残局数据库保存已解决的棋局.Video••卡斯帕罗夫••问题的提出•穷举算法•可以解决状态空间很小的简单问题•大空间无法胜任：组合爆炸•组合爆炸•64阶梵塔：–节点：364=0.94*1030–理论最短路径：264-1=2*1019•博弈–一字棋：9！=3.6*105–西洋棋：1078–国际象棋：10120（极限并行速度10-104秒/步，需1016年）–围棋：107613.3启发式搜索启发性信息•按其用途划分,启发性信息可分为以下三类：–用于扩展节点的选择,即用于决定应先扩展哪一个节点,以免盲目扩展。–用于生成节点的选择,即用于决定应生成哪些后续节点,以免盲目地生成过多无用节点。–用于删除节点的选择,即用于决定应删除哪些无用节点,以免造成进一步的时空浪费。3.3启发式搜索•特点：重排OPEN表，选择最有希望的节点加以扩展•种类：有序搜索、A*算法等3.3.1启发式搜索策略和估价函数盲目搜索可能带来组合爆炸启发式信息用来加速搜索过程的有关问题领域的特征信息。•启发函数–启发函数是用来估计搜索树上节点x与目标节点Sg接近程度的一种函数,通常记为h(x)–定义•一个节点到目标节点的某种距离或差异的度量•一个节点处于最佳路径上的概率•根据经验的主观打分•估价函数为获得某些节点“希望”的启发信息，提供一个评定侯选扩展节点的方法，以便确定哪个节点最有可能在通向目标的最佳路径上。f(n)——表示节点n的估价函数值•应用节点“希望”程度（估价函数值）重排OPEN表3.3.2有序搜索实质选择OPEN表上具有最小f值的节点作为下一个要扩展的节点。开始把S放入OPEN表，计算估价函数f(s)OPEN表为空表？选取OPEN表中f值最小的节点i放入CLOSED表i为目标节点吗？扩展i，得后继节点j，计算f(j)，提供返回节点i的指针，利用f(j)对OPEN表重新排序，调整亲子关系及指针失败成功图3.9有序搜索算法框图是否是否算法•例子八数码难题（8-puzzleproblem）12384567（目标状态）12384567（初始状态）八数码难题的有序搜索树见下图：123845671238456712384567（4）（6）（6）123845671238456712384567（6）（5）（5）1238456712384567（5）（7）1238456712384567（6）（7）12384567（5）8132456712384567（5）（7）图3.10八数码难题的有序搜索树123846（4）7•启发式搜索–利用问题拥有的启发信息来引导搜索，达到减少搜索范围，降低问题复杂度的目的–在保证找到最佳解的情况下，尽可能减少搜索范围，提高搜索效率•启发信息–强•降低搜索工作量，但可能导致找不到最优解–弱•产生式系统在找到一条路径之前将扩展过多的节点，一般导致工作量加大•极限情况下盲目搜索，但可能可以找到最优解3.3.3A*算法A*算法•评价函数f(n)=g(n)+h(n)–n是被评价的结点–f(n)•评价函数•从s经过n到g的路径的耗散值–g(n)•代价函数•从s到n的路径的耗散值–h(n)•启发函数•从n到g的路径的耗散值3.3.3A*算法•估价函数的定义：对节点n定义f*(n)=g*(n)+h*(n),表示从S开始约束通过节点n的一条最佳路径的代价。希望估价函数f定义为：f(n)=g(n)+h(n)——g是g*的估计，h是h*的估计•A*算法的定义：定义1在GRAPHSEARCH过程中，如果第8步的重排OPEN表是依据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*算法。当h=0时，A*算法就变为有序搜索算法。•评价函数的计算–g（n）•根据已搜索的结果，按照从初始结点s到结点n的路径，计算其耗散值即可•g(n)对g*(n)作出估计，有g(n)≥g*(n)–h(n)•依赖于启发信息，称为启发函数•对未来扩展的方向作出估计–f(n)•按f(n)递增的顺序来排列OPEN表的节点，优先扩展f(n)值小的节点，体现了好的优先搜索思想3.3.3A*算法•八数码2831647512384