如果对于任何结点n，有h(n)≤h*(n)，则此时的A算法称为A*算法。

A*特点：（1）是一种启发式的图搜索算法；（2）当问题有解时，A*算法一定能找到解，并且能保证找到最佳解。

12.在与或图中，什么是能解结点？

答：能解结点：（1）代表本原问题的终结点是能解结点；（2）若非终结点有"或"子结点时，当且仅当其子结点至少有一个能解，该非终结点才能解；（3）若非终结点有"与"子结点时，当且仅当其子结点均能解，该非终结点才能解。

13.什么是归结？简述用谓词归结法证明定理的过程。

答：设C1和C2是子句集中的任意两个子句，如果C1中的文字L1与C2中的文字L2互补，那么可从C1和C2中分别消去L1和L2，并将C1和C2中余下的部分按析取关系构成一个新子句C12，则称这一个过程为归结，称C12为C1和C2的归结式，称C1和C2为C12的亲本子句。

过程：（1）将已知条件化作子句集；（2）将结论的否定化作子句集；（3）从所有子句集中选取两个可归结的子句进行归结；（4）重复过程（3），直到出现空子句NIL为止。这时，就证明了在所给已知条件下结论成立。

在归结过程中，可以删除包含纯文字的子句以及永真式子句。都不会影响子句集的不可满足性，并且可以缩小归结的范围，提高归结的效率。

14.简述回溯策略与深度优先策略的不同点

答：（1）深度优先搜索属于图搜索，而回溯搜索则不是图搜索；

（2）在回溯搜索中，只保留从初始结点到当前结点的搜索路径，而深度优先搜索中则保留了所有已经搜索过的路径。

15.产生式系统由哪些部分组成？产生式知识表示方法的优缺点是什么？

答：把一组产生式放在一起，让它们相互配合，协同作用，一个产生式生成的结论可以供另一个产生式作为已知事实使用，以求得问题的解，这样的系统称为产生式系统。

组成产生式系统的三要素:（1）数据库；（2）规则库；（3）推理机。

优点：表示的格式固定、形式单一、规则间相互独立，整个过程只是前件匹配，后件动作；模块性好；自然性好；推理方式单纯。

缺点：求解效率低，不能表示结构性的知识。

16.什么是语义网络知识表示?给出这种表示方法的优缺点

答：语义网络是通过概念及其语义关系来表示知识的一种网络图，它是一个带标注的有向图。其中，有向图的各结点用来表示各种概念、事物、属性、情况、动作、状态等，结点上的标注用来区分各结点所表示的不同对象，每个结点可以带有若干个属性，以表征其所代表的对象之特性；弧是有方向、有标注的，方向用来体现结点间的主次关系，而其上的标注则表示被连接的两个结点间的某种语义联系或语义关系。

优点：结构性、自然性、联想性和非严格性。

缺点：推理规则不十分明了；表达范围有限，一旦结点个数太多，网络结构复杂，推理就难以进行。

17.什么是置换？置换是可交换的吗？

答：通常用有序对的集合s＝{t1/v1，t2/v2，…，tn/vn}来表示任一置换，置换集的元素ti/vi的含义是表达式中的变量vi处以项ti来替换，用s对表达式E作置换后的例简记为Es。

一般来说，置换是不可交换的，即两个置换合成的结果与置换使用的次序有关。

18.为什么A*算法会出现重复扩展结点的问题？解决的方法有哪些？

答：一般情况下，当A*算法扩展结点n时，并不能保证已经找到了从初始结点到结点n的最短路径，所以在以后的搜索中，当找到了更短的从初始结点到结点n的路径时，就要对n进行重复扩展。

如果h是单调的时，当A*算法扩展结点n时，就已经找到了从初始结点到结点n的最优路径，因此在以后的搜索过程中，不会出现需要修改到n的路径问题，因此也就不会出现重复扩展结点问题了。

19.什么是启发式搜索？

答：启发式搜索又称为有信息搜索，它是指在搜索求解的过程中，根据问题本身的特性或搜索过程中产生的一些信息来不断地改变或调整搜索的方向，使搜索朝着最有希望的方向前进，加速问题的求解，并找到最优解。

20.α－β剪枝的条件是什么？

答：α剪枝：若任一极小值层结点的β值小于或等于它任一先辈极大值结点的α值，即α（先辈层）≥β（后继层），则可中止该极小值层中这个MIN结点以下的搜索过程。这个MIN结点最终的倒推值就确定为这个β值。

β剪枝：若任一极大值层结点的α值大于或等于它任一先辈极小值层结点的β值，即α（后继层）≥β（先辈层），则可以中止该极大值层中这个MAX结点以下的搜索过程。这个MAX结点的最终倒推值就确定为这个α值。

21.产生式系统中，推理机的推理方式有哪几种？请分别解释说明。

答：产生式系统推理机的推理方式有正向推理、反向推理和双向推理三种。

正向推理：正向推理是从己知事实出发，通过规则库求得结果。

反向推理：反向推理是从目标出发，反向使用规则，求证已知的事实。

双向推理：双向推理是既自顶向下又自底向上的推理。推理从两个方向进行，直至在某个中间界面上两方向结果相符便成功结束；如两方衔接不上，则推理失败。

22.什么是盲目搜索？主要有几种盲目搜索策略？

答：盲目搜索又称无信息搜索，即在搜索过程中，只按预先规定的搜索控制策略进行搜索，而没有任何中间信息来改变这些控制策略。

主要的盲目搜索策略有：宽度优先搜索、深度优先搜索、有界深度优先搜索、代价树的宽度优先搜索和代价树的深度优先搜索。

四：应用题