•另外，可能存在多条线路都可实现对问题的求解，这就又出现按哪一条线路进行求解以获得较高的运行效率的问题。像这样根据问题的实际情况不断寻找可利用的知识，从而构造一条代价较少的推理路线，使问题得到圆满解决的过程称为搜索。2.搜索分类搜索分为盲目搜索和启发式搜索。盲目搜索——按预定的控制策略进行搜索，在搜索过程中获得的中间信息不用来改进控制策略。这种搜索具有盲目性，效率不高，不便于复杂问题的求解。启发式搜索——在搜索中加入了与问题有关的启发性信息，用以指导搜索朝着最有希望的方向前进，加速问题的求解过程并找到最优解。5.2求解问题的表示方法用搜索策略求解问题，首先要解决的问题也是：用什么样的形式把问题表示出来.一般来说，有两种方法：状态空间表示法；与/或树表示法；1.状态空间表示法状态空间表示法是用来表示问题及其搜索过程的一种方法，它是人工智能中最基本的形式化方法。状态空间表示法是用“状态”和“算符”来表示问题的一种方法。其中，“状态”——用以描述问题求解过程中不同时刻的状况；“算符”——表示对状态的操作，算符的每一次使用就使问题由一种状态变换为另一种状态;解——当到达目标状态时，由初始状态到目标状态所用算符的序列就是问题的一个解。Ⅰ.状态状态是描述问题求解过程中任一时刻状况的数据结构，一般用一组变量的有序组合表示：SK＝(SK0,SK1,…)当给每一个分量以确定的值时，就得到了一个具体的状态。Ⅱ.算符引起状态中某些分量发生变化，从而使问题由一个状态变为另一个状态的操作称为算符。在产生式系统中，每一条产生式规则就是一个算符。Ⅲ.状态空间由问题的全部状态及一切可用算符所构成的集合称为问题的状态空间，—般用—个三元组表示：(S，F，G)其中,S是问题的所有初始状态构成的集合；F是算符的集合；G是目标状态的集合。状态空间的图示形式称为状态空间图。其中，节点表示状态；有向边(弧)表示算符。例1：钱币翻转问题，如图所示。设有三个钱币，起初是状态为（反正反），允许每次翻转一个钱币（只反一个，也必反一个），连反三次，问是否可达到目标状态？（正正正）或（反反反）？上述问题的状态空间“三元组”为：（{S5},{f1,f2,f3},{s0,s7}）相应的状态空间图：2.与/或树表示法与/或树是用于表示问题及其求解过程的又一种形式化方法，通常用于表示比较复杂问题的求解。对于一个复杂问题，直接求解往往比较困难。此时，可通过下述方法进行简化：(1)分解：“与”树把一个复杂问题分解为若干个较为简单的子问题，然后对每个子问题分别进行求解，最后把各子问题的解复合起来就得到了原问题的解。这是“与”的问题。与/或树：将上述两种方法也可结合起来使用，此时的图称为“与/或树”，其中既有“与”节点，也有“或”节点。在此统称为子节点。Ⅲ.可解节点在与/或树中，满足下列条件之一者，称为可解节点：•它是一个终止节点。•它是一个“或”节点，且其子节点中至少有一个是可解节点。•它是一个“与”节点，且其子节点全部是可解节点。Ⅳ.不可解节点关于可解节点的三个条件全部不满足的节点称为不可解节点。Ⅴ.解树由可解节点所构成，并且由这些可解节点可推出初始节点(它对应于原始问题)为可解节点的子树称为解树。在解树中一定包含初始节点。例如：t标出的节点是终止节点，根据可解节点的定义，原始问题P是可解的。例：三阶汉诺塔问题。设有A，B，C三个金片以及三根钢针，三个金片按自上而下从小到大的顺序穿在1号钢针上，要求把它们全部移到3号钢针上，而且每次只能移动一个金片，任何时刻都不能把大的金片压在小的金片上面，如图所示。为了用与/或树把问题的分解过程表示出来，先要定义问题的形式化表示方法。设仍用状态表示问题在任一时刻的状况；用三元组(i，j，k)表示状态：i代表金片C所在的钢针号；j代表金片B所在的钢针号;k代表金片A所在的钢针号。用“”表示状态的变换；这样原始问题就可表示为：(1,1,1)(3，3，3)用与/或树把分解过程表示出来。5.3状态空间搜索策略1.概述(1)显式图与隐式图为了求解问题，需要把知识存储在计算机的知识库中，有下列两种存储方式：显式存储：把与问题有关的全部状态空间图，即相应的全部知识（事实性知识、过程性知识，控制性知识）都直接存入知识库，称为“显式存储”或“显式图”。隐式存储：只存储与问题有关的部分知识，在求解过程中，又初始状态出发，运用相应的知识，逐步生成所需的部分状态空间图，通过搜索推理，找到所求目标。这样只需在知识库中存储局部状态空间图，称为“隐式图”。通常，为了节约计算机的存储容量，提高搜索推理效率，采用隐