要成功地求解只拥有隐式图的问题，初始存入的部分知识很重要，必须包含或覆盖全部要用到的知识，否则造成推理失败。此外还必须有一个产生新知识或生成状态空间的方法。在计算机中，利用有关知识逐步产生新的知识或状态空间，并检查问题是否解决的过程，叫隐式图搜索过程。这个问题和人解决问题的过程十分相似。如果计算机能按此过程工作，计算机也就有了一定的智慧。人工智能感兴趣的问题就是如何运用局部知识去解决给定的问题。
用隐式图搜索法求解问题的方法与过程如下： 搜索方法：
①运用叙述性知识，给出问题的部分状态描述，包括初始状态So、
目标状态Sg和某些中间状态Sh；
②运用过程性知识，给出“生成器”函数G（x）（Generator
Function），即由状态空间图的“父结点”生成“子结点”的操作或算子；
③运用控制性知识：给出评价函数E（x）（Evaluation Function），
用于评价新生成的结点，控制继续搜索的前进方向。
相应的过程：
①给定求解问题的初始状态（So、初始结点）；
②用生成器函数G（小），由So出发生成中间状态Sh（各子结点），
并检索每个中间状态是否为目标状态，若是则搜索成功。
③若目标状态Sg未出现，则继续搜索，用评价函数E（x）对Sh
的各节点进行评价，选取适当的或最有希望的结点，再用G（x）生成其子结点（状态S2），再检查是否为目标状态Sg。如此下去，直到找到目标状态Sg为止，若所有可生成的结点均已扩展，仍无Sg出现，则搜索失败。
第三节 广度优先搜索法
一．
广度优先搜索法的概念
所谓广度优先搜索法就是按“先产生的结点先扩展”的原则进行搜索。如下图所示。
2 1 3
8 9 10 4 5 6 7
在广度优先搜索法中，从初始结点So开始，按生成规则，G（x）逐步生成下一级各子点，并顺序检查是否出现目标状态Sg（现生成的子结点优先检查、优先扩展）。在该级全部结点中沿广度进行“横向”扫描，这里，评价函数E（x）=d（x）是结点x的深度（级数），即认为同一级各结点对问题求解的“价值”是同等的，只是按各结点生成的先后次序，先生成、先检查、先扩展，按广度遍历所有的结点，故称“广度优先搜索法”。
二． 广度优先搜索算法与流程
为了实现广度优先搜索算法，使得先生成的点先扩展，必须引入两张表即一个OPEN表和一个CLOSE表。
取出 OPEN表 CLOSE表
写入
状态结构 …….. 返回指针
编号 1 2 …… 写入
状态结构 ………. 返回指针 ………. ……..
图 开表和闭表结构
其中：开（OPEN）表是一个先进先出的结构表，专门登记新产生的结点，它们等待着被扩展；闭（CLOSE）表是一个专门登记已被扩展的结点的表，表中各节点按顺序编号。
广度优先搜索的实质是：如果在问题树种存在有目标结点。则它们一定是在树的某些有限级上，用广度优先搜索法就一定可以找到它们，所以说广度优先搜索过程是算法的。
广度优先搜索法的流程与算法如下：
开 始 把S0放入OPEN表中 Y OPEN=NIL? N 取OPEN表中最前面的结点N放入CLOSE表中，并编号 失 败 Y N=S? N N 可扩展？ Y 可扩展，将其子结点依次放入OPEN 成 功 表的末尾，并配上指向N的返回指针 步骤1：把初始点So放在OPEN表中；
步骤2：若OPEN表为空，则搜索失败，问题无解；
步骤3：取OPEN表中最前面的一个结点N，放在CLOSE表中，并给以编号n； 步骤4：若N=Sg（目标结点），则搜索成功，问题得解； 步骤5：若该结点无子结点，返回为否则继续；
步骤6：扩展N结点，并把它的诸子结点依次放入OPEN标的末尾，且让这些结
点的返回指针指向N，转步2。
三． 搜索效率的定量描述
一个搜索过程的搜索效率决定于它的启发能力和其它许多与问题求解有关
的属性，至今没有一个成熟的方法来评价，目前已发展出一些定量计算的方法，它们是片面的，但它们在比较同一个问题的不同的搜索方法的效率时是有用的。其中一种量度是外显率P（Penetrance），它反映较差目标搜索时的搜索宽度，被定义为：
P=L/T 其中，L——到达目标的长度；
T——整个搜索过程中产生的结点综述。
一般来说，P≤1。其中，当效率最高的搜索P=1，且启发能力强。若P?1，搜索能力弱。P和问题的难度有关，一般是L越小的简单问题，P值越高，反之P值越低。
搜索效率的另一种度量是：有效分支因素（Effective Branching Factor）B，它表示整个搜索过程中，每个有效结点平均生成的子结点。
第四节 常见的知识推理技术
一． 图搜索
图搜索主要是解决由状态空间法所表示的问题的求解方法，常见的搜索方法有：
1． 广度优先搜索法
在每级的全部结点中沿广度进行“横向”扫描，这里，评价函数E（x）=d（x）并按各结点生成的先后次序，先生成、先检查、先扩展，沿广度遍历所有结点。是一种完备的优先搜索法，是一种推理算法。
评价函数： E（x）=d（x）
d（x）为结点x的深度。
2.深度优先搜索法
按“最晚生成的点先扩展”，并沿最晚生成的子结点分支，逐级纵向深入发展。
若目标结点Sg不在最晚生成的子结点分支中，且该分支为无穷分支，则搜索过程无限循环，搜索失败。因而它是不完备的，不是推理算法，而是推理步骤。
评价函数： E（x）=N（x）
N（x）为x的先后生成次序。
3.有界深度优先搜索法
对深度优先搜索法的改进，加入定界问题，是搜索具有完备性。 d（Sgm）=min（d（Sg））
当搜索失败时，可适当的增加界值dm。 4.代价驱动搜索法
根据“最小代价”优先扩展的原则，优先最小代价的搜索路径，进行推理求解问题。
①代价驱动广度优先搜索法：在滚滚度优先搜索法中，引入“最小代价”原则，相应的评价函数： E（x）=c（x）
So到Sgx所支付的代价。
②代价驱动深度优先搜索：“代价最小，优先扩展”控制策略。 5.局部择优搜索法
是一种启发是搜索方法，是深度优先搜索法的一种改进。在控制策略上引入了启发式知识，使搜索过程的评价函数E（x）反应启发信息。
根据评价函数E（x）的取值大小，进行比较择优，选取待扩展的结点N，逐级向纵深搜索前进的。
E（N）=min 或 max[E(x1),E(x2),……E(xn)] 当求解极值问题时，定义评价函数为梯度函数 E（x）=grad H（x）
对于极值问题，搜索可能会失败，因此局部择优法或瞎子爬山法是不完备的推理步骤。
6.全局择优搜索法
是一种启发试图搜索方法，它弥补了局部择优法的局限性，对多极值问题进行了考掠。在同级的所有子结点中进行比较择优，利用评价函数对所有子结点进行评价。
该搜索法的效率和完备性取决于评价函数E（x）