29.在启发式搜索当中，通常用启发函数来表示启发性信息。

30.在二人博弈问题中，最常用的一种分析技术是极大极小搜索方法，这种方法的思想是先生成一棵博弈树，然后再计算其倒推值。但它的效率较低，因此人们在此基础上，又提出了α-β剪枝搜索方法。

31.不确定性类型按性质分：随机性、模糊性、不完全性、不一致性和时变性等。

32.合一算法：求非空有限具有相同谓词名的原子公式集的最一般合一。

三：简答题

1.A算法中，是如何判断算法成功结束的？只要出现了目标结点就立即结束对吗？

答：每次从OPEN表中取出第一个结点，在扩展该结点之前，判断该结点是否是目标结点，如果是目标结点，则算法成功结束。如果目标结点虽然出现了，但它还不是OPEN表中f值最小的结点，则不能立即结束，需要继续扩展下去，直到目标结点的f值在OPEN表中最小为止。

2.什么是合一？什么是合一者？

答：若存在一个置换s使得表达式集{Ei}中每个元素经置换后的例有：E1s＝E2s＝E3s＝…，则称表达式集{Ei}是可合一的，这个置换s称作{Ei}的合一者。

3.AO*算法的特点是什么？

答：（1）AO*算法不能像A算法那样，单纯靠评价某一个结点来评价局部图；

（2）由于k-连接符连接的有关子结点，对父结点能解与否以及耗散值都有影响，因而不能像A算法那样优先拓展其中具有最小耗散值的结点；

（3）AO*算法仅适用于无环图的假设，否则耗散值递归计算不能收敛，因而在算法中还必须检查新生成的结点已在图中时，是否是正在被拓展结点的先辈结点；

（4）A算法设有OPEN表和CLOSE表，而AO*算法只用一个结构G，它代表到目前为止已显式生成的部分搜索图，图中每个结点的h(n)值是估计最佳解图，而不是估计解路径。

4.h是单调的条件是什么？

答：如果对于任何结点ni和nj，其中nj是ni的后继结点，h满足条件：h(ni)-h(nj)≤C(ni，nj)，且h(t)＝0，其中t为目标结点，则称为h是单调的。

5.当h满足单调条件时，就可以完全避免重复结点扩展问题吗？为什么？

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

6.什么是人工智能？

答：人工智能是研究如何制造出人造的智能机器或智能系统，来模拟人类智能活动的能力，以延伸人们智能的科学。

7.宽度优先方法的特点是什么？

答：所谓深度优先搜索，就是在每次扩展一个结点时，选择到目前为止深度最浅的结点优先扩展。

宽度有限搜索有如下特点：

（1）属于图搜索；

（2）是一个通用的搜索方法；

（3）当问题有解时，一定能找到解；

（4）在单位耗散值的情况下，问题如果有解，一定能找到最优解。

8.A算法中的f(n)、g(n)和h(n)各代表什么含义？

答：g(n)表示从初始结点当结点n的最优路径耗散值的估计。h(n)表示从结点n到目标结点最优路径耗散值的估计。f(n)=g(n)+h(n)表示从初始结点出发，经过结点n，到达目标结点的最优路径的耗散值的估计。

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

答：不能解结点：（1）没有后裔的非终结点是不能解结点；（2）若非终结点有"或"子结点时，当且仅当所有子结点均不能解时，该非终结点才不能解；（3）若非终结点有"与"子结点时，当至少有一个子结点不能解时，该非终结点才不能解。

10.深度优先方法的特点是什么？

答：所谓深度优先搜索，就是在每次扩展一个结点时，选择到目前为止深度最深的结点优先扩展。

深度有限搜索有如下特点：

（1）属于图搜索；

（2）是一个通用的搜索方法；

（3）如果深度限制不合适，有可能找不到问题的解；

（4）不能保证找到最优解。

11.什么是A算法？什么是A*算法？A*算法有什么特点？

答：定义评价函数:f(n)=g(n)+h(n)对OPEN表中的元素按照f值，从小到大进行排列，每次从OPEN表中取出f值最小的结点扩展，这种图搜索算法成为A算法。