序列找到后，算子序列就作用于状态描述，从而产生新的描述，然后，从达到第一个目标的新描述出发，再探索满足这时处在栈顶的目标。此过程继续进行，直到栈空为止。然后作最后的检查，即将原来的总目标与应用算子产生的最终状态做比较，如果在最终状态时尚有任何一部分分量达到，那么，那些没解决的目标部分将重新压入栈中，过程继续下去。
B） 最小提交策略的非线性规划：
在规划系统中，总是首先假设问题可以分解为子问题，再分别求解子问题，然后，联合子问题的解，看它们是否可以作为原问题的解。若是原问题的解，当然万事大吉；若不是原问题的解，还有很多事情要做。最简单的方法是抛弃已经得到的解，去寻找另一解，看是否变得更好一些。这方法虽然简单，但可能造成极大的浪费。有一种方法称为最小提交策略，它的基本思想是：先考虑每个子问题的结果，再找出它们之间的依次关系，最后才挑选操作的执行次序，以避免出现冲突。
应用最小提交策略来选择算子的执行次序是一种找非线性规划的方法。利用它则不必考虑好算子序列的一切排列。整个方法分两步：第一步就是发现所需要的算子，并找出任何所要求的执行次序。例如，在执行一算子前，必须执行一些为实现该算子前提条件的操作，第二步则是寻找算子的执行次序，使之满足一定的约束条件。问题求解系统NOAH就是这样做的，它既利用一个格结构来记录被选算子的定序，也采用等级规划既形成规划大纲，在逐步填入越来越细的内容。
5、双相推理与“手段——目的”分析 （1） 正向、反向、多向推理： 一般情况下，有三种推理方向： ① 正向推理（向前推理）
从初始状态向前推理到达目标状态为止。
根节点 初始状态 正向 端节点 目标状态
（事实，条件） 反向 （结论，解答）
② 反向推理（向后推理） （同上相反）
③ 双向推理（前后推理）
从初始状态出发，向前推理，也从目标状态出发出发向后推理，双向前后推理，在中部相交，满足一致性条件的终止。
采用双向推理的搜索方法，是压缩搜索空间、延缓“组合爆炸”提高搜索效率的途径之一。
跟节点 初态 端节点 终态 （事实，条件） （结论，解答）
若双向推理所生成的两棵搜索树，恰好在中点相交，并设两棵搜索树的扩展深度相同，等于单向推理搜索树扩展深度的一半，则搜索空间的压缩系数：
n?NN双向单向?2mmn2n?2mn
其中：N ——双、单向搜索树的端节点总数 m——分枝数（广度） m=2，3，4，?? n——分级数（深度） n=1，2，3，??
由上式可知，双向推理可压缩搜索空间η≤1 大多数情况下η《 1
六、关于搜索的一些问题
1.组合爆炸
所谓“组合爆炸”，是指在大型复杂问题求解的搜索过程中，随着搜索广度与深度的增加，搜索树的分支数与节点数急剧增加，这种由于分级与分枝的组合作用，导致搜索空间急剧扩大的现象，称之为“组合爆炸”。
由于组合爆炸的现象严重，使得许多问题不可能采用完备的推理算法来求解，因为计算机存储空间和运算速度的实际限制，不可能对组合爆炸所生成的巨大的状态空间进行全面的搜索。
例如，在博弈问题中，可能的终局总数如下： ?一字棋 ：q！=3.6*105 ?国际象棋： 10120 ?中国象棋： 10261
而计算机的速度估计： ?普通速度：每秒1亿条指令
?最优程序：每步10条指令 0.1μs/步 ?最高速度：实际估计可达1ns/步 ?串行机理论速度极限：10-12ns/步 ?并行机理论速度极限：10-88 ns/步
这样即使用最高理论计算速度运行求解国际象棋的完备算法也需要1亿亿年（=10-16）才能完成，而今我们已知的宇宙历史才100亿年。
2.推理复杂度
由推理复杂性研究可知，计算时间随问题状态空间维数（终局数，节点数）增加而增长，其增长规律有两种：
?指数律：T（n）=2n，3n，n！，nn?? ?多项式律：T（n）=n2，n3，nk，??
单纯的依靠提高计算机速度，扩大解题规模的潜力是有限的，并且要付出一定的代价，此外提高速度与增加计算机存储空量是矛盾的，因为存取信息的时间随容量的扩大而增长，因此在大型复杂问题的推理求解方面，往往是不现实，且效率是很低的。
为此，需要运用启发性知识，寻求高效率的推理求解方法。它只需搜索部分状态空间，就可以求得问题的解，或者利用分解技术和多组规划将大型复杂问题简单化。
但是，只搜索部分状态空间可能将失去谈问题的某些信息，使搜索过程失去完备性，使推理算法蜕变为推理步骤，不能保证求得所需问题的解。因此，如何利用启发信息以尽量减少搜索空间而造成的信息丢失，即提高搜索效率，又不过多的损失完备性，是启发推理方法的关键。
3.搜索效率
从问题求解的角度看，我们希望在搜索过程中生成对求解问题有用的结点，也就是生成从初始结点到目标结点路上的结点，而与此无关的结点尽量少生成或不生成，这样当然搜索效率就高，目前对搜索效率如何定义尚无统一的计算方法。下面我们定义两种有关搜索效率的度量。虽然它们都还不全面，但是它们在比较
同一问题的不同搜索法的效率时是有用的。其中一种度量称为外显率（或穿透率）（Penetrance）p,定义为
P=L/T
其中：L表示从初始状态到目的状态的路长，T表示被搜索过程中所产生的结点总数（不包括初始结点）。这样以来，
P ↗ 搜索效率 ↗
通常P≤1
P=1 搜索效率最高
② 有效分枝因素（Effective Branching Factor）
它代表在搜索过程中，每个有效结点平均生成子结点数目。设L是结点的深度（或路长），则有：
T=B+B2+B3+??BL
T由上知
P?L/T?L(1?B)B?BL?B?BB1?BL
当B接近1时,T接近L值.P=1,效率最高.
如下图所示,可以画出P～Ｌ关系曲线．从图上可看出，当Ｂ一定时，Ｌ越大，Ｐ越小．当Ｌ一定时，Ｂ越大，Ｐ越小．