???过程的基本思想：首先使搜索树的某一部分达到最大深度，这时计算出某些MAX
节点的?值，或者是某些MIN节点的?值。随着搜索的继续，不断修改个别节点的?或者?。对任意节点，当其某一后继结点的最终值给定时，就可以确定该节点的?或者?。当该节点的其他后继节点的最终值给定时，就可以对该节点的?或者?进行修正。
若任何MIN节点的?值小于或者任何他的先辈MAX节点的?值，则可停止该MIN节点以下的搜索，然后这个MIN节点的最终倒退至结尾它已经得到的?，该值与真正的极大极小的搜索结果的倒退值可能不一样，但是对开始节点而言，倒退至是相同的。当满足该规则时，可以进行?剪枝。
若任何MAX节点的?值大于或者等于它的MIN先辈节点的?值，则可以停止该MAX节点以下的搜索，然后这个MAX节点处的倒退值解为它的?值。当满足该规则时，可以进行?剪枝。
4、 假设N个传教士和N个野人，传每次最多可供K个人乘渡，这里N?5,K?3。
假设在某一时刻，在河的左岸有M个传教士，C个野人。B?1表示船在左岸，
现在已它们的组合作为启发式函数的基本分量。给定下面两B?0表示船在右岸。
种不同的启发式函数：
（1）h1(n)?M?C （2）h2(n)?M?C?2B
试说明h1(n)不满足h1(n)?h(n)，而h2(n)?h(n)
答：（1）要说明h1(n)不满足h1(n)?h(n)，只要给出一个反例。如状态
（M,C,B）=（1,1,1）时，h1(n)?M?C=1+1=2，而实际上只要摆渡一次就可以达到目标。所以h1(n)不满足h1(n)?h(n)
（2）要证明h2(n)?h(n)，从两种情况说明。
A、船在左岸的情况
如果不考虑限制条件，那么摆渡的次数肯定比有限制的摆渡的次数少。另外每船载三人的摆渡次数肯定比每船载2人的次数少。所以先考虑没有限制的条件下，每次船上可以在人数为3人
*****时的摆渡次数为次。其中分子中的“-3”表示剩下最后3个留待者最后一次运过去。除以2是因为一个来回可以运过去2个人，需要??M?c?3?个来回，乘以2是因为一个来回相当于两?2??次摆渡，而最后的加1，则表示将剩下的3个人运过去，需要一次摆渡。化简为
M?C?3?M?c?3?*2?1?*2?1?M?C?2 ??22??B、考虑船在右岸的情况
同样不考虑限制条件。船在右岸，需要一个人将船运到左岸。因此对于状态(M,C,0)来说，七所需要的最少摆渡数，相当于船在左岸时状态(M?1,C,1)或者(M,C?1,1)所需要的最少摆渡数，再加上第一次将船从右岸送到左岸的一次摆渡数。因此所需要的最少摆渡次数为：
(M?C?1)?2?1?M?C，其中M?C?1中的+1表示送船回到左岸的那个人，最后边+1
表示送船到左岸时的一次摆渡。化简得到
(M?C?1)?2?1?M?C
综上分析，所需要的最少摆渡次数可以为M?C?2B
由于该摆渡次数是在不考虑限制的条件选推出的最少所需要的摆渡次数。因此，当有限制条件的时候，最优的摆渡次数只能大于或等于该摆渡次数。所以启发式函数h2(n)满足
h2(n)?h*(n)
5、考虑下面的博弈树，静态值（在叶节点的圆括号中）都是从第一个博弈者的角度得的。假设第一个博弈者为MAX，如图所示。 （1）第一个博弈者将选择什么移动？
（2）假如采用???算法。那些节点无须检验（假设节点按从左到右的顺序检验） L 2 M 3 A B C D E A F A G H I J K N 8 O 5 P 7 Q 6 R 0 S 1 T 5 U 2 V 8 W 4 X 10 Y 2 (1) D
(2) O、Q、I（因此T和U）Y。
6、 简述用归结法证明定理的过程（消解反演求解过程）。
给出一个公式集S和目标公式L，通过反证或反演来求证目标公式L，其证明步骤如下： （1）否定L，得到~L； （2）把~L添加到S中去；
（3）把新产生的集合{~L，S}化成子句集F；
（4）（以前）应用消解原理，力图推导出一个表示矛盾的空子句
（现在ppt）反复归结子句集F中的子句，若出现了空子句，则停止归结，此时就证明了L永真
7、计算下述各字句对的归结式 （1）C1:P?R，C2:?P?Q （2）C1:?P?Q，C2:P
（3）C1:?P?Q?R，C2:?Q??R （4）C1:?P?Q，C2:?P?R （5）C1:Q,C2:?Q
解：（1）两个字句的归结式为：C12:R?Q （2）两个字句的归结式为：C12:Q
（3）两个字句的归结式为存在两个归给式：C12:?P?R??R或者C12:?P?Q??Q。该字句中，只能在Q上或R上归结，不能两者同时归结。所以?P不是归结式
（4）C1中的任何文字都不能与C2中的文字构成互补对，所以C1和C2不存在归结式
（5）
Q和?Q是文字互补对。所以C12:（空字句）
8、将合式公式化为字句形
?x[?P(x)?[?y[?P(y)?P(f(x,y))]???y[?Q(x,y)?P(y)]]]
解：
?x[?P(x)?[?y[?P(y)?P(f(x,y))]???y[?Q(x,y)?P(y)]]]
= ?x[?P(x)?[?y[?P(y)?P(f(x,y))]??y[Q(x,y)??P(y)]]] = ?x[?P(x)?[?y[?P(y)?P(f(x,y))]??w[Q(x,w)??P(w)]]] = ?x[?P(x)?[?y[?P(y)?P(f(x,y))]?[Q(x,g(x))??P(g(x))]]] =?x?y[?P(x)?[[?P(y)?P(f(x,y))]?[Q(x,g(x))??P(g(x))]]]
= ?x?y[[?P(x)?[?P(y)?P(f(x,y))]]?[?P(x)?Q(x,g(x))]?[?P(x)??P(g(x))]] 最后消去全称量词和连接词? ①[?P(x)??P(y)?P(f(x,y))] ②[?P(x)?Q(x,g(x))] ③[?P(x)??P(g(x))]
更改变量名称，于是有
?P(x1)??P(y)?P(f(x1,y)) ?P(x2)?Q(x2,g(x2)) ?P(x3)??P(g(x3))
9、设已知：
(1) 如果x是y的父亲，y是z的父亲，则x是z的祖父； (2) 每个人都有一个父亲。
使用归结演绎推理证明：对于某人u，一定存在一个人v，v是u的祖父。 解：先定义谓词
F(x,y)：x是y的父亲 GF(x,z)：x是z的祖父 P(x)：x是一个人
再用谓词把问题描述出来：
已知F1：(?x) (?y) (?z)( F(x,y)∧F(y,z))→GF(x,z)) F2：(?y)(P(x)→F(x,y))
求证结论G：(?u) (?v)( P(u)→GF(v,u)) 然后再将F1，F2和?G化成子句集： ① ?F(x,y)∨?F(y,z)∨GF(x,z)
② ?P(r)∨F(s,r)
③ P(u)
④ ?GF(v,u))
对上述扩充的子句集，其归结推理过程如下：