1、搜 索 策 略问题求解过程的形式表示搜索策略概述Nilsson说，搜索是人工智能中的一个基本问题。说，搜索是人工智能中的一个基本问题。人工智能的研究对象主要是那些没有成熟方法可依的问题领域，也人工智能的研究对象主要是那些没有成熟方法可依的问题领域，也就是说没有直接方法可以把有关问题解出来，而是必须一步步地去就是说没有直接方法可以把有关问题解出来，而是必须一步步地去摸索求解，这种问题求解过程就是搜索技术。根据问题的实际情况，摸索求解，这种问题求解过程就是搜索技术。根据问题的实际情况，按照一定的策略或规则，从知识库中寻找可利用的知识，从而构造按照一定的策略或规则，从知识库中寻找可利用的知识，从而构
2、造出一条使问题获得解决的推理路线的过程称为搜索。出一条使问题获得解决的推理路线的过程称为搜索。问题求解过程的形式表示状态空间表示法【例3-1】15-数码问题在一个4*4的16宫格棋盘上，摆放有15个将牌，每一个都刻有1-15中的某一个数码。棋盘中留有一个空格，允许其周围的某一个将牌向空格移动，这样通过移动将牌就可以不断改变将牌的布局。所要求解的问题：是给定一种初始布局(初始状态)和一个目标布局(目标状态)，问如何移动数码实现从初始状态到目标状态的转变，如图3-1所示。数码移动的状态空间图状态空间图的盲目搜索回溯策略回溯策略的定义是从初始状态出发，不停地、试探性地寻找路径，回溯策略的定义是从初始
3、状态出发，不停地、试探性地寻找路径，直到它到达目的或直到它到达目的或“不可解结点不可解结点”，即，即“死胡同死胡同”为止。若它遇到为止。若它遇到不可解结点就回溯到路径中最近的父结点上，查看该结点是否还有不可解结点就回溯到路径中最近的父结点上，查看该结点是否还有其他的子结点未被扩展。若有，则沿这些子结点继续搜索；如果找其他的子结点未被扩展。若有，则沿这些子结点继续搜索；如果找到目标，就成功退出搜索，返回解题路径。到目标，就成功退出搜索，返回解题路径。【例3-3】皇后问题4-QueenProblem在4*4的棋盘上，安排4个Queen，使其互不干扰，即，行、列、斜线上没有其他棋子，如图所示。4*4
4、棋盘皇后问题示意图皇后问题回溯搜索过程图回溯搜索算法：BACKTRACK（DATA）DATA:当前状态返回值：从当前状态到目标状态的路径（以规则表的形式表示）或FAIL。BACKTRACK（i:integer）在棋盘上的前i-1行上已安置的各个棋子互不冲突。本过程从第i行起为各棋子安排合适的位置。当in时，表示已求得一个棋盘的合法布局，则输出结果IF in THEN 输出棋盘的当前布局ELSE FOR j:=1 TO n DO 在第i行j列上安放一个棋子；IF当前布局合法 THEN BACKTRACK（i+1）；移走第i行j列的棋子递归过程BACKTRACK（DATA）广度优先搜索策略如果搜索
5、是以接近起始点的程度依次扩展节点的，那么这种搜索就叫做广度优先搜索（breadth-first search）。1.广度优先搜索2.代价树广度优先搜索策略在实际问题中，将一个状态变换成另一个状态的代价（或费用）是不一样的，也就是状态空间图中各有向边的代价是不一样的，把有向边上标有代价的搜索树称为代价搜索树，简称代价树。在代价树中，把从节点i到其后继节点j的连线之代价记为C(i,j)，而把从初始节点S0到任意节点x的路径代价记为g(x)，则g(j)=g(i)+C(i,j)代价树广度优先搜索的基本思想，每次从OPEN表中选择一个代价最小的节点移入CLOSED表，因此每当一节点扩展后，就要计算它的所
6、有后继节点的代价，并将它们与OPEN表中已有的待扩展节点按代价的大小从小到大依次排序，而从OPEN表选择被扩展节点时即选择排在最前面的节点。算法如下：1 G:=G0(G0=s),OPEN:=(s),CLOSED:=();2 LOOP:IF OPEN=()THEN EXIT(FAIL);3 n:=FIRST(OPEN);4 IF GOAL(n)THEN EXIT(SUCCESS);5 REMOVE(n,OPEN),ADD(n,CLOSED);6 EXPAND(n)mi,G:=ADD(mi,G);7 IF 目标在mi中 THEN EXIT(SUCCESS);8 g(j)=g(i)+C(i,j),A
7、DD(OPEN,mj),并标记mj到n的指针,对OPEN按g()进行排序;9 GO LOOP;广度优先搜索策略深度优先搜索策略深度优先搜索（depth-first search）中，首先扩展最新产生的（即最深的）点，只有当搜索到达一个没有后裔的状态时，才考虑另一条替代路径。状态空间图的启发式搜索策略理论上，如果计算机可以使用的时间和空间是无限的，则仅有盲目搜索算法就已经够用了，但是实际上并非如此。启发式算法的本质是部分的放弃算法“一般化、通用化”的盖面，认为有关具体问题领域的信息可以用来引导搜索，以达到减少搜索范围，减低问题复杂度的目的。可以用于指导搜索过程，并且与具体问题求解有关的信息叫做启
8、发式信息，并把利用启发信息的搜索方法叫做启发式搜索方法（heuristically search）或信息搜索（informed search）。启发式搜索的原理是，对于每个在搜索过程中遇到的新状态，计算一个估计值，根据估计值的大小，确定下一步将从哪一个状态开始继续前进。一般以估计值小者为较优的状态，以此实行最佳优先搜索。而启发信息的强度强时，会降低搜索工作量，但是可能导致找不到最优解，如果强度弱时，一般导致工作量加大，极限情况下变为盲目搜索，但是可能可以找到最优解。启发信息可以分为三类，第一类是用于决定要扩展的下一个节点，以免像在广度优先搜索或者深度优先搜索中那样盲目的扩展，第二类是在扩展一个
9、节点的过程中，用于决定要生成哪一个或者哪几个后继节点，以免盲目的同时生成搜索可能的节点，第三种是用于决定某些应该从搜索树中抛弃或修剪的节点。估价函数估价函数f是对当前的搜索状态进行估价，找出一个最优希望的节点来进行扩展，f(n)表示节点n的估价函数值。估价函数的格式为：f(n)=g(n)+h(n)，其中f(n)为估价函数，h(n)为启发函数，g(n)为从初始节点到n已经付出的代价，h(n)是从节点n到目标节点的最优路径的估计代价，它体现了问题的启发性信息，其形式要根据问题的特性确定，如，可以是节点n到目标节点的距离，也可以是节点n处于最优路径的概率等等。估价函数f(n)表示从初始节点n到达目标
10、节点的最优路径的代价的估计值，它的作用是评价OPEN表中各节点的重要程度，决定它们在OPEN表中的次序，其中g(n)指出了搜索的横向趋势，它有利于搜索的完备性，但影响搜索的效率。如果只关心到达目标节点的路径，并且希望有较高的搜索效率，则g(n)可以忽略，但是此时会影响搜索的完备性，因此要综合考虑，使g(n)、h(n)各占适当的比重。估价函数与择优搜索【例3-6】设有如下结构的移动将牌游戏，其中B代表黑色的将牌，W代表白色的将牌，E代表该位置为空，玩法是：当一个将牌移入相邻的空位置时，费用为一个单位；一个将牌至多可跳过两个将牌进入空位置，其费用等于跳过的将牌数加1；要求把所有的B移至所有的W的右
11、边，设计估价函数中的h(n)BBBWWWE根据要求可知，W左边的B越少越接近目标，因此可以用W左边的B的个数作为h(n)，即h(n)=3*(每个W左边B的个数的总和)，乘以3是为了扩大h(n)在f(n)中的比重，如对于BEBWWBW则有h(n)=3*(2+2+3)=21择优搜索有序搜索(Ordered Search)又称为最好优先搜索(Best-First search)，总是选择最有希望的节点作为下一个要扩展的节点。有序搜索算法ORDERDSEARCH1 G=G0(G0=s),OPEN:=(s)，计算f(s);2 CLOSED:=();3 LOOP:IF OPEN=()THEN EXIT(F
12、AIL);4 n:=MIN_VALUE_F(OPEN),REMOVE(n,OPEN),ADD(n,CLOSED);5 IF GOAL(n)THEN EXIT(SUCCESS);6 EXPAND(n)mi,G:=ADD(mi,G);7 标记和修改指针：计算f(mi)若mi不在OPEN也不在CLOSED，ADD(n,OPEN),标记指向n的指针；若mi记在OPEN或CLOSED上，比较f值，若新计算的f较小，则以新值取代旧值，mi指向n；若mi记在CLOSED，REMOVE(mi,CLOSED),ADD(mi,OPEN)8 OPEN中节点按由小到大排序9 GO LOOP局部择优搜索是一种启发式搜索
13、方法，是对深度优先搜索方法的一种改进，它的基本思想是当一个节点被扩展后，按f(n)对每一个子节点计算估价值，并选择最小者作为下一个要考察的节点，由于每次都只在子节点范围内选择下一个要考察的节点，范围比较窄，所以称为局部择优。算法：1 把初始节点S0放入OPEN表，计算f(S0)2 LOOP:IF EMPTY(OPEN)THEN EXIT(FAIL)3 n:=FIRST(OPEN);REMOVE(n,OPEN),ADD(n,CLOSED);4 IF GOAL(n)THEN EXIT(SUCCESS);5 若n不可扩展，GO LOOP6 EXPAND(n)，计算每个子节点的f，将子节点按f由小到大
14、的顺序加入OPEN表的首部，将每个子节点指向n；GO LOOP择优搜索全局择优搜索是在搜索中每次从OPEN表的全体节点中先择一个估价值最小的节点。算法如下：1把初始节点S0放入OPEN表，计算f(S0)2 LOOP:IF EMPTY(OPEN)THEN EXIT(FAIL)3 n:=FIRST(OPEN);REMOVE(n,OPEN),ADD(n,CLOSED);4 IF GOAL(n)THEN EXIT(SUCCESS);5若n不可扩展，GO LOOP6 EXPAND(n)，计算每个子节点的f，使每个子节点指向n，将每个子节点加入OPEN表中，对OPEN表中的全部节点按估价值由小到大的顺序进
15、行排序7 GO LOOP启发式搜索A算法首先介绍一下H*算法估值函数f的含义是f在某个节点处的值估计了从根节点开始，到达目标节点，并且经过该节点n的一条代价为最小的路径的代价。H*算法：令g(n)为对g*(n)的估计：g(n)0令h(n)为对h*(n)的估计：h(n)0令f(n)=g(n)+h(n)为每个节点n处的估值函数使用如此选定的估值函数f的有序搜索算法即为H*算法其中，g*(n)是从s到n的最短路径的代价值，h*(n)从n到g的最短路径的代价值，f*(n)=g*(n)+h*(n)是从s到g的最短路径的代价值，g(n)、h(n)、f(n)分别是g*(n)、h*(n)、f*(n)的估计值。
16、启发式搜索A算法A算法：1 OPEN:=(s),f(s):=g(s)+h(s)2 LOOP IF OPEN=()THEN EXIT(FAIL)3 n:=FIRST(OPEN);4 IF GOAL(n)THEN EXIT(SUCCESS);5 REMOVE(n,OPEN),ADD(n,CLOSED);6 EXPAND(n)mi,计算f(n,mi):=g(n,mi)+h(mi)ADD(mj,OPEN),标记mj到n的指针 IF f(n,mk)f(mk)THEN f(mk):=f(n,mk),标记mk到n的指针 IF f(n,ml)f(ml)THEN f(ml):=f(n,ml),标记ml到n的指针
17、,ADD(ml,OPEN)7 OPEN中的节点按f值由小到大排序8 GO LOOPA*算法1.定义在A算法中，如果满足条件h(n)h*(n)，则A算法称为A*算法，其中，h(n)称为h*(n)的下界，它表示某种偏于保守的估计，当h=0时，A*算法就变为有序搜索算法。在A*算法中，g(n)比较容易求得，它实际上就是从初始节点S0到节点n的路径代价，恒有g(n)g*(n)，而且在算法执行过程中，随着更多搜索信息的获得，g(n)的值呈下降的趋势。h(n)的确定依赖于具体问题领域的启发性信息，其中h(n)h*(n)是十分重要的，它可保证A*算法能找到最优解。【例3-8】在图中，从节点S0开始景扩展得到
18、x1和x2，且g(x1)=3,g(x2)=7,对x1扩展后得到x2与x3，此时g(x2)=6，,g(x3)=5，显然，后来算出的,g(x2)比先前算出的小。A*算法2.A*算法性质3.A*算法的可采纳性4.A*算法的最优性5.A*的复杂性6.h(n)的单调性限制与或树的搜索策略与或图表示1.分解2.等价变换3.与或图的基本概念与或树的盲目搜索1.广度优先搜索广度优先搜索步骤如下：(1)把初始节点S0放入OPEN表。(2)LOOP:取出OPEN表第一个节点n放入CLOSED表。(3)若n可扩展扩展n，将其子节点放入OPEN表尾部，并为每个子节点配置指向父节点的指针，以备标示过程使用调用可解节点标
19、示过程GO LOOP(4)若n不可扩展标识n为不可解节点调用不可解节点标识过程GO LOOP2.深度优先搜索深度优先搜索步骤如下：(1)把初始节点S0放入OPEN表。(2)LOOP:取出OPEN表第一个节点n放入CLOSED表。(3)若节点n的深度大于深度界限GO STEP5(4)若n可扩展扩展n，将其子节点放入OPEN表首部，并为每个子节点配置指向父节点的指针，以备标示过程使用调用可解节点标示过程GO LOOP(5)若n不可扩展标识n为不可解节点调用不可解节点标识过程GO LOOP与或树的启发式搜索1.解树的代价2.希望树3.与或树的有序搜索算法博弈树的启发式搜索1.博弈举例【例3-16】剪
20、刀、石头、布游戏甲乙两个人用剪刀石头布来决定谁休息，谁找水。乙甲石头剪刀布石头未定、未定休息、找水找水、休息剪刀找水、休息未定、未定休息、找水布休息、找水找水、休息未定、未定博弈树的启发式搜索2.博弈要素(1)参与者（Player）：参与者的标志是他是否是博弈的利害关系者；(2)规则（Rule）：对博弈作出具体规定的集合，如参与者行动的顺序、行动时知道的信息、可选择的行动、行动后会得到的结果；(3)结果（Outcome）：所有参与者每一个可能行动的结果；(4)收益（Payoff）：在每一个可能的结果上参与者的得失3.博弈树4.博弈树方法(1)极小极大分析(2)-剪枝(1)极小极大分析极小极大分
21、析基本思想为，设博弈双方一方为A一方为B，极小极大分析方是为其中一方如A来寻找一个最优行动方案的方法；为了找到当前的最优行动方案，需要对各个方案可能产生的后果进行比较，考虑每个方案实施后对手可能采取的行动，并计算可能的得分；为计算得分，需根据问题的特性信息定义一个估价函数，用来估算当前博弈树端节点的得分，此时计算出的得分称为静态估值；当端节点估值计算出后，再推算父节点的得分，称为倒推值。推算方法是：对于“或”节点，选其子节点中一个最大的得分作为父节点得分，对“与”节点，选其子节点中最小的得分作为父节点得分；如果一个行动方案能获得较大的倒推值，它就是当前最好的行动方案。极小极大过程如图所示：(2
22、)-剪枝-剪枝的原理为，在极小极大过程中，总是先生成一定深度的博弈树，然后对端节点进行估值，再计算上层节点的倒推值，效率较低，博弈树具有“与”节点与“或”节点逐层交替出现的特点，如果能边生成节点，边计算估值及倒推值，就可能删去一些不必要的节点，从而减少不必要的工作量，例如，在图中，由S3与S4的估值计算的S1的倒推值为3，这表示S0的倒推值最小为3；另外由S5的估值得到S2的倒推值最大为2，因此S0的倒推值为3，此时S6的值对上层的计算没有影响，可以从博弈树中剪去。对于“与”节点，取当前子节点中最小倒推值作为倒推值的上界，称为，值永不增加；对于“或”节点，取当前子节点中最大倒推值作为倒推值的下
23、界，称为，值永不减少。剪枝的条件：后辈节点的值祖先节点的值时，剪枝后辈节点的值祖先节点的值时，剪枝简记为：极小极大，剪枝极大极小，剪枝本章小结本章介绍了多种搜索策略。盲目搜索包括广度优先搜索、深度优先搜索等。启发式搜索主要讨论了A*算法，与盲目搜索不同的是，启发式搜索运用启发信息，引用某些准则或者经验来重新排列OPEN表中节点的顺序，使得搜索沿着某个被认为是最有希望的方向扩展。本章还介绍了与或树等知识，使得读者对于搜索策略有全面的了解。思考与小结(1)深度优先搜索和广度优先搜索有什么区别？(2)如何证明一个算法是A*算法？A*算法的可采纳性如何证明？(3)用与或图表示“猴子和香蕉”问题。一只猴子位于水平位置a处，香蕉挂在水平位置c处的上方，猴子想吃香蕉，但高度不够，够不着。恰好在b处有可移动的台子，若猴子站在台子上，就可以够到香蕉。问题是判定猴子的行动计划，使它能够到香蕉。(4)一博弈树如下图所示，回答如下问题：1）计算各结点的倒推估值 2）画出-剪枝的结果
