状态空间搜索策略

状态空间搜索策略第1页，共45页，2023年，2月20日，星期日

从问题表示到问题的解决，有一个求解的过程。常见的AI问题求解技术有两种，即“搜索”（Search）和“推理”（Reasoning）方法。

逻辑推理，是通过构造一个逻辑系统，由它可以从已有的断言（公理）推导出新的断言。并用逻辑形式语言描述的一组公理来表达问题域。用这种方法来解决问题就是通过推理来积聚越来越多的断言，直到获得问题的解答。虽然问题求解可通过搜索方法，也可用逻辑推理，但二者的侧重点是不一样的。前者着重于寻求问题解答的过程，而后者强调前提（初始）问题空间（公理集合）与问题解答间连接的逻辑正确性。或者简单地讲，搜索着重于发现（Discovery），而推理强调证明（Proof）。第2页，共45页，2023年，2月20日，星期日搜索在状态图中寻找目标或路径的基本方法从初始节点，沿着与之相连的边，寻找目标节点的过程搜索树搜索过程中经过的节点和边，按照原图的连接关系，便形成一个树形的有向图第3页，共45页，2023年，2月20日，星期日盲目搜索无向导搜索/穷举式搜索从初始节点，沿连接边逐一考察各个节点，或反向进行启发式(heuristic)搜索利用“启发性信息”引导的搜索启发式信息是与问题有关的有利于尽快找到问题解的信息或知识第4页，共45页，2023年，2月20日，星期日3.1

图搜索策略图（状态图）搜索控制策略

一种在图中寻找路径的方法。

图中每个节点对应一个状态，每条连线对应一个操作符。这些节点和连线(即状态与操作符)又分别由产生式系统的数据库和规则来标记。求得把一个数据库变换为另一数据库的规则序列问题就等价于求得图中的一条路径问题。第5页，共45页，2023年，2月20日，星期日图组成节点有向边图分类或图（直接图、状态图）与或图图搜索过程图第6页，共45页，2023年，2月20日，星期日图（状态图）搜索策略CLOSED表：用来记录考察过的节点对树形搜索，存储的是搜索树对线式搜索，存储的是折线OPEN表：记录待考察的节点排序方式不同，对应的搜索算法不同节点父节点编号编号节点父节点编号CLOSED表OPEN表第7页，共45页，2023年，2月20日，星期日开始把S放入OPEN表OPEN表为空表？把第一个节点(n)从OPEN表移至CLOSED表n为目标节点吗？把n的后继节点放入OPEN表的末端，提供返回节点n的指针修改指针方向重排OPEN表失败成功图3.1

图搜索过程框图是是否否第8页，共45页，2023年，2月20日，星期日3.2

盲目搜索特点：不需重排OPEN表种类：宽度优先、深度优先、等代价搜索等。3.2.1

宽度优先搜索

定义

以接近起始节点的程度逐层扩展节点的搜索方法。特点：一种高代价搜索，但若有解存在，则必能找到它。

算法第9页，共45页，2023年，2月20日，星期日广度（宽度）优先搜索

(Breadth-firstsearch,BFS)优先在同一级节点中考察，只有当同一级节点考察完毕之后，才考察下一级节点自顶向下一层一层逐渐生成的第10页，共45页，2023年，2月20日，星期日宽度优先搜索算法步1：把初始节点So放入OPEN表中。步2：若OPEN表为空,则搜索失败,退出。步3：取OPEN表中前面第一个节点N放在CLOSED表中,并冠以顺序编号n。步4：若目标节点Sg=N,则搜索成功,结束。步5：若N不可扩展,则转步2。步6：扩展N,将mj子节点配上指向N的指针依次放入OPEN表尾部,转步2。注解：OPEN表是一个队列CLOSED表是一个顺序表，表中各节点按顺序标号，正在被考察的节点在表中编号最大如果问题有解，目标点Sg必出现在OPEN表中，算法结束根据返回指针，在CLOSED表中回溯，得到求解路径第11页，共45页，2023年，2月20日，星期日开始把S放入OPEN表OPEN表为空表？把第一个节点(n)从OPEN表移至CLOSED表是否有后继节点为目标节点？扩展n，把n的后继节点放入OPEN表的末端，提供返回节点n的指针失败成功图3.2宽度优先算法框图是否是否第12页，共45页，2023年，2月20日，星期日

例子

八数码难题（8-puzzleproblem）

1238456712384567（目标状态）规定：将牌移入空格的顺序为：从空格左边开始顺时针旋转。不许斜向移动，也不返回先辈节点。从图可见，要扩展26个节点，共生成46个节点之后才求得解（目标节点）。第13页，共45页，2023年，2月20日，星期日123845671238412384567412385671238412384567123845671238456767891011121312384567567567112384567123845671238456712384567234513456123845671238456712384567123845671238456723242526271236782212384567123845671238456712384567123845671238456712384567141516171819202112384567图3.4八数码难题的宽度优先搜索树第14页，共45页，2023年，2月20日，星期日宽度优先搜索算法宽度优先/横向搜索优点策略是完备的如果有解，肯定找到解，且找到的解是最优解(最短路径)缺点效率低第15页，共45页，2023年，2月20日，星期日节点深度：根节点深度=0其它节点深度=父节点深度+13.2.2

深度优先搜索第16页，共45页，2023年，2月20日，星期日3.2.2

深度优先搜索

定义

首先扩展最新产生的(即最深的)节点。

算法

防止搜索过程沿着无益的路径扩展下去，往往给出一个节点扩展的最大深度——深度界限。与宽度优先搜索算法最根本的不同在于：将扩展的后继节点放在OPEN表的前端。（算法框图见教材）第17页，共45页，2023年，2月20日，星期日深度优先搜索（Depth-firstsearch，DFS）在搜索树的每一层始终只扩展一个子结点，不断地向纵深前进直到不能再前进（到达叶子结点或深度限制），才从当前节点返回上一级节点，沿另一方向又继续前进从树根开始一枝一枝逐渐生成的第18页，共45页，2023年，2月20日，星期日路径节点序列为(n0,n1,…,nk)对于i=1,…,k，若节点ni-1具有一个后继节点ni，该序列称为从n0到nk的路径n0nkn1nk-1n3n2第19页，共45页，2023年，2月20日，星期日深度优先搜索算法纵向搜索缺点如果一个有解的问题树可能有无穷分支，如果误入无穷分支（即深度无限），则不可能找到目标节点策略不是完备的找到的解是不一定最优解最短路径)第20页，共45页，2023年，2月20日，星期日3.2.3

等代价搜索

定义

是宽度优先搜索的一种推广，不是沿着等长度路径断层进行扩展，而是沿着等代价路径断层进行扩展。搜索树中每条连接弧线上的有关代价,表示时间、距离等花费。

算法

若所有连接弧线具有相等代价，则简化为宽度优先搜索算法。第21页，共45页，2023年，2月20日，星期日开始把S放入OPEN表OPEN表为空表？把具有最小g(i)值的节点i从OPEN表移至CLOSED表是否有后继节点为目标节点？失败成功图3.2等代价搜索算法框图是否是否S是否目标节点？是成功扩展i，计算其后继节点j的g(j)，并把后继节点放入OPEN表否令g(s)=0第22页，共45页，2023年，2月20日，星期日国际象棋对弈程序:深蓝开发者:IBM的MurryCampbell,Feng-HsiungHsu和JosephHoane采用30个IBMRS/6000处理器来运行软件搜索使用480个定制VLSI国际象棋处理器执行生成行棋的功能﹑树的最后几层的”硬件搜索”以及对叶节点的评价.每秒平均搜索12.6亿种走法，峰值时每秒钟搜索33亿个节点.每走一步至多能够预先计算300亿种个棋局,常规搜索深度是14步.机器的核心算法是使用调换表的标准迭代深入α-β搜索,而且对关键的点具备产生超越搜索深度的扩展能力,在某些情况下可以达到40层的深度.评价函数采用了超过8000个特征;使用一本有4000个棋局的”开局手册”以及一个存有70万个大师级比赛棋谱的数据库;使用一个大型残局数据库保存已解决的棋局.第23页，共45页，2023年，2月20日，星期日Video/v_show/id_XMzk1MzQ0ODYw.htmlDeepBlue15years/v_show/id_XMTEyOTU5MjQ0.html

卡斯帕罗夫/v_show/id_XMzU4NzY0NzE2.htmlWindows8/v_show/id_XMzE4MzM5OTA0.htmlKinect第24页，共45页，2023年，2月20日，星期日问题的提出穷举算法可以解决状态空间很小的简单问题大空间无法胜任：组合爆炸组合爆炸64阶梵塔：节点：364=0.94*1030理论最短路径：264-1=2*1019博弈一字棋：9！=3.6*105西洋棋：1078国际象棋：10120（极限并行速度10-104秒/步，需1016年）围棋：107613.3

启发式搜索第25页，共45页，2023年，2月20日，星期日启发性信息按其用途划分,启发性信息可分为以下三类：用于扩展节点的选择,即用于决定应先扩展哪一个节点,以免盲目扩展。用于生成节点的选择,即用于决定应生成哪些后续节点,以免盲目地生成过多无用节点。用于删除节点的选择,即用于决定应删除哪些无用节点,以免造成进一步的时空浪费。第26页，共45页，2023年，2月20日，星期日3.3

启发式搜索特点：重排OPEN表，选择最有希望的节点加以扩展种类：有序搜索、A*算法等3.3.1启发式搜索策略和估价函数盲目搜索可能带来组合爆炸启发式信息

用来加速搜索过程的有关问题领域的特征信息。第27页，共45页，2023年，2月20日，星期日启发函数启发函数是用来估计搜索树上节点x与目标节点Sg接近程度的一种函数,通常记为h(x)定义一个节点到目标节点的某种距离或差异的度量一个节点处于最佳路径上的概率根据经验的主观打分第28页，共45页，2023年，2月20日，星期日估价函数

为获得某些节点“希望”的启发信息，提供一个评定侯选扩展节点的方法，以便确定哪个节点最有可能在通向目标的最佳路径上。

f(n)——表示节点n的估价函数值应用节点“希望”程度（估价函数值）重排OPEN表3.3.2

有序搜索实质

选择OPEN表上具有最小f值的节点作为下一个要扩展的节点。第29页，共45页，2023年，2月20日，星期日开始把S放入OPEN表，计算估价函数f(s)OPEN表为空表？选取OPEN表中f值最小的节点i放入CLOSED表i为目标节点吗？扩展i，得后继节点j，计算f(j)，提供返回节点i的指针，利用f(j)对OPEN表重新排序，调整亲子关系及指针失败成功图3.9有序搜索算法框图是否是否算法第30页，共45页，2023年，2月20日，星期日

例子八数码难题（8-puzzleproblem）12384567（目标状态）12384567（初始状态）八数码难题的有序搜索树见下图：第31页，共45页，2023年，2月20日，星期日123845671238456712384567（4）（6）（6）123845671238456712384567（6）（5）（5）1238456712384567（5）（7）1238456712384567（6）（7）12384567（5）8132456712384567（5）（7）图3.10八数码难题的有序搜索树123846（4）7第32页，共45页，2023年，2月20日，星期日启发式搜索利用问题拥有的启发信息来引导搜索，达到减少搜索范围，降低问题复杂度的目的在保证找到最佳解的情况下，尽可能减少搜索范围，提高搜索效率启发信息强降低搜索工作量，但可能导致找不到最优解弱产生式系统在找到一条路径之前将扩展过多的节点，一般导致工作量加大极限情况下盲目搜索，但可能可以找到最优解3.3.3A*算法第33页，共45页，2023年，2月20日，星期日A*算法评价函数

f(n)=g(n)+h(n)n是被评价的结点f(n)评价函数从s经过n到g的路径的耗散值g(n)代价函数从s到n的路径的耗散值h(n)启发函数从n到g的路径的耗散值第34页，共45页，2023年，2月20日，星期日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*算法就变为有序搜索算法。

第35页，共45页，2023年，2月20日，星期日评价函数的计算g（n）根据已搜索的结果，按照从初始结点s到结点n的路径，计算其耗散值即可g(n)对g*(n)作出估计，有g(n)≥g*(n)h(n)依赖于启发信息，称为启发函数对未来扩展的方向作出估计f(n)按f(n)递增的顺序来排列OPEN表的节点，优先扩展f(n)值小的节点，体现了好的优先搜索思想3.3.3A*算法第36页，共45页，2023年，2月20日，星期日八数码2831647512384765初始状态第37页，共45页，2023年，2月20日，星期日八数码评价函数f(n)=g(n)+h(n)g(n)：从初始节点到当前节点的耗散值h(n)：当前节点“不在位”的将牌数2831647512345768h(n)=4第38页，共45页，2023年，2月20日，星期日2831647528314765283164752831647523184765283147652831476528371465832147652318476523184765123847651238476512378465S(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=5