第五章 状态空间搜索策略
搜索是人工智能的一个基本问题，是推理不可分割的一部分。搜索是求解问题的一种方法，是根据问题的实际情况，按照一定的策略或规则，从知识库中寻找可利用的知识，从而构造出一条使问题获得解决的推理路线的过程。搜索包含两层含义：一层含义是要找到从初始事实到问题最终答案的一条推理路线；另一层含义是找到的这条路线是时间和空间复杂度最小的求解路线。搜索可分为盲目搜索和启发式搜索两种。 1．1 盲目搜索策略 1．状态空间图的搜索策略
为了利用搜索的方法求解问题，首先必须将被求解的问题用某种形式表示出来。一般情况下，不同的知识表示对应着不同的求解方法。状态空间表示法是一种用“状态”和“算符”表示问题的方法。状态空间可由一个三元组表示(S0，F，Sg)。
利用搜索方法求解问题的基本思想是：首先将问题的初始状态(即状态空间图中的初始节点)当作当前状态，选择一适当的算符作用于当前状态，生成一组后继状态(或称后继节点)，然后检查这组后继状态中有没有目标状态。如果有，则说明搜索成功，从初始状态到目标状态的一系列算符即是问题的解；若没有，则按照某种控制策略从已生成的状态中再选一个状态作为当前状态，重复上述过程，直到目标状态出现或不再有可供操作的状态及算符时为止。
算法5．1 状态空间图的一般搜索算法
①建立一个只含有初始节点S0的搜索图G，把S0放入OPEN表中。 ②建立CLOSED表，且置为空表。
③判断OPEN表是否为空表，若为空，则问题无解，退出。
④选择OPEN表中的第一个节点，把它从OPEN表移出，并放入CLOSED表中，将此节点记为节点n。
⑤考察节点n是否为目标节点，若是，则问题有解，并成功退出。问题的解即可从图G中沿着指针从n到S0的这条路径得到。
⑥扩展节点n生成一组不是n的祖先的后继节点，并将它们记作集合M，将M中的这些节点作为n的后继节点加入图G中。
⑦对那些未曾在G中出现过的(即未曾在OPEN表上或CLOSED表上出现过的)M中的节点，设置一个指向父节点(即节点n)的指针，并把这些节点加入OPEN表中；对于已在G中出现过的M中的那些节点，确定是否需要修改指向父节点(n节点)的指针；对于那些先前已在G中出现并且已在COLSED表中的M中的节点，确定是否需要修改通向它们后继节点的指针。
⑧按某一任意方式或按某种策略重排OPEN表中节点的顺序。 ⑨转第③步。 2．宽度优先搜索策略
宽度优先搜索是一种盲目搜索策略。其基本思想是，从初始节点开始，逐层对节点进行依次扩展，并考察它是否为目标节点，在对下层节点进行扩展(或搜索)之前，必须完成对当前层的所有节点的扩展(或搜索)。在搜索过程中，未扩展节点表OPEN中的节点排序准则是：先进入的节点排在前面，后进入的节点排在后面(即将扩展得到的后继节点放于OPEN表的末端)。
宽度优先搜索的盲目性较大，搜索效率低，这是它的缺点。但宽度优先搜索策略是完备的，即只要问题有解，用宽度优先搜索总可以找到它的解。 3．深度优先搜索
深度优先搜索也是一种盲目搜索策略，其基本思想是：首先扩展最新产生的
(即最深的)节点，即从初始节点S0开始，在其后继节点中选择一个节点，对其进行考察，若它不是目标节点，则对该节点进行扩展，并再从它的后继节点中选择一个节点进行考察。依此类推，一直搜索下去，当到达某个既非目标节点又无法继续扩展的节点时，才选择其兄弟节点进行考察。
深度优先搜索与宽度优先搜索的区别就在于：在对节点n进行扩展时，其后继节点在OPEN表中的存放位置。宽度优先搜索是将后继节点放入OPEN表的末端，而深度优先搜索则是将后继节点放入OPEN表的前端。 4．有界深度优先搜索
对于许多问题，其状态空间搜索树的深度可能为无限深。为了避免搜索过程沿着无穷的路径搜索下去，往往对一个节点扩展的最大深度进行限制。任何节点如果达到了深度界限，就把它作为没有后继节点进行处理，即对另一个分支进行搜索。
在有界深度优先搜索算法中，深度界限的选择很重要。选择过大，可能会影响搜索的效率；选择的过小，有可能求不到解。有界深度优先搜索策略是不完备的。
5．代价树的宽度优先搜索
前面的搜索算法没有考虑搜索的代价问题，即假设状态空间图中各节点之间的有向边的代价是相同的。在实际问题求解中，往往是将一个状态变换成另一个状态时所付出的操作代价(或费用)是不一样的，即状态空间图中各有向边的代价是不一样的。把有向边上标有代价的搜索树称为代价搜索树，简称代价树。 代价树宽度优先搜索的基本思想是：每次从OPEN表中选择一个代价最小的节点，移入COLSED表。因此，每当对一节点扩展之后，就要计算它的所有后继节点的代价，并将它们与OPEN表中已有的待扩展的节点按代价的大小从小到大依次排序。而从OPEN表选择被扩展节点时即选择排在最前面的节点(代价最小)。代价树的宽度优先搜索算法是一个完备算法。
6．代价树的深度优先搜索
代价树的深度优先搜索和宽度优先搜索的区别是：宽度优先搜索法每次从OPEN表中的全体节点中选择代价最小的节点移入CLOSED表，并对这一节点进行扩展或判断(是否为目标节点)，而深度优先搜索法则是从刚刚扩展的节点之后继节点中选择一个代价最小的节点移入CLOSED表，并进行扩展或判断。代价树的深度优先搜索算法是不完备的算法，所求得的解不一定是最优解，甚至有可能进入无穷分支路径而搜索不到问题的解。 1．2 启发式搜索策略
利用问题自身特性信息，以提高搜索效率的搜索策略，称为启发式搜索或有信息搜索。
1．启发信息与估价函数
在搜索过程中，如果在确定要被考察的节点时，能够利用被求解问题的有关特性信息，估计出各节点的重要性，就可选择重要性较高的节点进行扩展，以便提高求解的效率。通常可以构造一个函数来表示节点的“希望”程度，称这种函数为估价函数。
估价函数f(x)可定义为从初始节点经过节点z到达目标节点的最小代价路径的代价估计值。它的一般形式为 f(x)=g(x)+h(x)
其中g(x)为初始节点S0到节点z已实际付出的代价；h(x)是从节点x到目标节点Sg的最优路径的估计代价，搜索的启发信息主要由h(x)来体现，故把h(x)称作启发函数。
估价函数是针对具体问题构造的，是与问题特性密切相关的。不同的问题，其估价函数可能不同。在构造估价函数时，依赖于问题特性的启发函数h(x)的构造尤为重要。
在构造启发函数时，还要考虑到两个方面因素的影响：一个是搜索工作量，一个是搜索代价。有些启发信息虽然能够大大减少搜索的工作量，但却不能保证求得最小代价的路径。而我们感兴趣的是，使问题求解的路径代价与为求此路径所花费的搜索代价的综合指标为最小。 2．最佳优先搜索
最佳优先搜索又称为有序搜索或择优搜索，它总是选择最有希望的节点作为下一个要扩展的节点，而这种最有希望的节点是按估价函数f(x)的值来挑选的，一般估价函数的值越小，它的希望程度越大。最佳优先搜索又分局部最佳优先搜索和全局最佳优先搜索。 (1)局部最佳优先搜索
局部最佳优先搜索的思想类似于深度优先搜索法，但由于使用了与问题特性相关的估价函数来确定下一个待扩展的节点，所以它是一种启发式搜索方法。其思想是：当对某一个节点扩展之后，对它的每一个后继节点计算估价函数f(x)的值，并在这些后继节点的范围内，选择一个f(x)的值最小的节点，作为下一个要考察的节点。由于它每次只在后继节点的范围内选择下一个要考察的节点，范围比较小，所以称为局部最佳优先搜索或局部择优搜索。
局部最佳优先搜索与深度优先搜索及代价树的深度优先搜索的区别，就在于在选择下一个节点时所用的标准不一样。局部最佳优先搜索是以估价函数值作为标准；深度优先搜索则是以后继节点的深度作为选择标准，后生成的节点先考察；而代价树深度优先则是以各后继节点到其前驱节点之间的代价作为选择标准。如果把层深函数d(x)就当作估价函数f(x)，或把代价函数g(x)当作估价函数f(x)，那么就可以把深度优先搜索和代价树深度优先搜索看作局部最佳优先搜索的两个特例。
(2)全局最佳优先搜索
全局最佳优先搜索也是一个有信息的启发式搜索，它的思想类似于宽度优先
搜索，所不同的是，在确定下一个扩展节点时，以与问题特性密切相关的估价函数f(x)作为标准，不过这种方法是在OPEN表中的全部节点中选择一个估价函数值f(x)最小的节点，作为下一个被考察的节点。正因为选择的范围是OPEN表中的全部节点，所以它称为全局最佳优先搜索或全局择优搜索。
全局最佳优先搜索实际是对宽度优先搜索和代价树的宽度优先搜索的扩展，而宽度优先搜索和代价树的宽度优先搜索则是它的两个特例(这时可分别令f(x)等于d(x)或g(x)，d(x)表示节点x的深度，而g(x)则表示初始节点S0到节点x的代价)。
在启发式搜索中，估价函数的定义是非常重要的，如果定义得不好，则上述的搜索算法不一定能找到问题的解，即便找到解，也不一定是最优解。所以，有必要讨论如何对估价函数进行限制或定义。
A*启发式搜索算法就使用了一种特殊定义的估价函数。 A*算法具有下列一些性质：
①可采纳性。所谓可采纳性是指对于可求解的状态空间图(即从状态空间图的初始节点到目标节点有路径存在)来说，如果一个搜索算法能在有限步内终止，并且能找到最优解，则称该算法是可采纳的。
②单调性。所谓单调性是指在A*算法中，如果对其估价函数中的h(x)部分即启发性函数，加以适当的单调性限制条件，就可以使它对所扩展的一系列节点的估价函数值单调递增(或非递减)，从而减少对OPEN表或CLOSED表的检查和调整，提高搜索效率。
③信息性(又称最优性)。A*算法的搜索效率主要取决于启发函数h(x)，在满足h(x)≤h*(x)的前提下，h(x)的值越大越好。h(x)的值越大，表明它携带的与求解问题相关的启发信息越多，搜索过程就会在启发信息指导下朝着目标节点前进，所走的弯路越少，搜索效率就会提高。
人工智能[第五章状态空间搜索策略]山东大学期末考试知识点复习
