人工智能3.1引言搜索算法的输入是给定的问题，输出时表示为动作序列的方案。一旦有了方案，就可以执行该方案所给出的动作了。（执行阶段）求解问题包括：目标表示搜索执行给定问题就是确定该问题的基本信息:（1）初始状态集合：定义了问题的初始状态。（2）操作符集合：把一个问题从一个状态变换为另一个状态的动作集合。（3）目标检测函数：用来确定一个状态是不是目标。（4）路径费用函数：对每条路径赋予一定费用的函数。搜索问题包括：搜索什么(目标)在哪里搜索(搜索空间)和通常的搜索空间不同，人工智能中大多数问题的状态空间在问题求解之前不是全部知道的。搜索分成：状态空间的生成阶段在该状态空间中对所求问题状态的搜索搜索可以根据是否使用启发式信息分为盲目搜索启发式搜索盲目搜索只是可以区分出哪个是目标状态。一般是按预定的搜索策略进行搜索。没有考虑到问题本身的特性，这种搜索具有很大的盲目性，效率不高，不便于复杂问题的求解。根据问题的表示方式分为状态空间搜索与或树搜索搜索策略评价标准:完备性：如果存在一个解答，该策略是否保证能够找到？时间复杂性：需要多长时间可以找到解答？空间复杂性：执行搜索需要多少存储空间？最优性：如果存在不同的几个解答，该策略是否可以发现最高质量的解答？考虑一个问题的状态空间为一棵树的形式。宽度优先搜索深度优先搜索3.2盲目搜索方法对于给定问题，如何生成新状态呢？3.2.1宽度优先搜索ProcedureBreadth-first-searchBegin把初始节点放入队列；Repeat取得队列最前面的元素为current;Ifcurrent=goal成功返回并结束；ElsedoBegin如果current有子女，则current的子女以任意次序添加到队列的尾部；EndUntil队列为空End搜索最优策略的比较宽度优先搜索是一种盲目搜索，时间和空间复杂度都比较高，当目标节点距离初始节点较远时会产生许多无用的节点，搜索效率低。宽度优先搜索中，时间需求是一个很大的问题，特别是当搜索的深度比较大时，尤为严重，但是空间需求是比执行时间更严重的问题。3.2.2深度优先搜索ProcedureDepthFirstSearchBegin把初始节点压入栈，并设置栈顶指针；While栈不空doBegin弹出栈顶元素；If栈顶元素=goal，成功返回并结束；Else以任意次序把栈顶元素的子女压入栈中；EndWhileEnd初始节点放到栈中，栈指针指向栈的最上边的元素。为了对该节点进行检测，需要从栈中弹出该节点，如果是目标，该算法结束，否则把其子节点以任何顺序压入栈中。该过程直到栈变成为空。遍历一棵树的过程（下图）。3.2.3迭代加深搜索策略说明:改进方法：（迭代加深搜索）先任意给定一个较小的数作为dm，然后按有界深度算法搜索，若在此深度限制内找到了解，则算法结束；如在此限制内没有找到问题的解，则增大深度限制dm，继续搜索。迭代加深搜索，试图尝试所有可能的深度限制：首先深度为0，然后深度为1，然后为2，等等。如果初始深度为0，则该算法只生成根节点，并检测它。如果根节点不是目标，则深度加1，通过典型的深度优先算法，生成深度为1的树。当深度限制为m时，树的深度为m。搜索最优策略的比较3.3启发式搜索3.3.1启发性信息和评估函数g(x)——从初始节点S0到节点x的实际代价；h(x)——从x到目标节点Sg的最优路径的评估代价，它体现了问题的启发式信息，其形式要根据问题的特性确定，h(x)称为启发式函数。评估函数：f(x)=d(x)+w(x)d(x)表示节点在x搜索树中的深度，w(x)表示节点x中不在目标状态中相应位置的数码个数，w(x)就包含了问题的启发式信息。一般来说某节点的w(x)越大，即“不在目标位”的数码个数越多，说明它离目标节点越远。对初始节点S0，由于d(S0)=0，w(S0)=5，因此f(S0)=5。在搜索过程中除了需要计算初始节点的评估函数外，更多的是需要计算新生节点的评估函数。3.3.2最好优先搜索算法3.3.3通用图搜索算法可以给出两个数据结构OPEN和CLOSED表，分别存放了Open节点和Closed节点。节点x总的费用函数f(x)是g(x)和h(x)之和。生成费用g(x)可以比较容易地得到，如，如果节点x是从初始节点经过m步得到，则g(x)应该和m成正比（或者就是m）。h(x)只是一个预测值。上述图搜索算法生成一个明确的图G（称为搜索图）和一个G的子集T（称为搜索树），图G中的每一个节点也在树T上。搜索树是由返回指