（10） P(sun) ∨﹁P(li) (2)与(5)归结 （11） ﹁P(zhao) ∨ P(li) (3)与(4)归结 （12） P(sun) ∨﹁P(qian) (3)与(5)归结 （13） P(qian) (2)与(7)归结 （14） P(sun) (2)与(12)归结
（15） ANSWER(qian) (6)与(13)归结，σ={qian/y} （16） ANSWER(sun) (6)与(14)归结, σ={sun/y} 所以，本题的盗窃犯是两个人：钱和孙。
2 任何兄弟都有同一个父亲，John和Peter是兄弟，且John的父亲是David，问Peter的父亲是谁？
解：第一步：将已知条件用谓词公式表示出来，并化成子句集。那么，要先定义谓词。 （1） 定义谓词：
设Father(x,y)表示x是y的父亲。 设Brother(x,y)表示x和y是兄弟。 （2） 将已知事实用谓词公式表示出来： F1: 任何兄弟都有同一个父亲。
???( x)( y)( z)( Brother(x,y)∧Father(z,x)→Father(z,y))
F2: John和Peter是兄弟。 Brother(John, Peter) F3: John的父亲是David。 Father(David, John)
（3） 将它们化成子句集，得
S1={﹁Brother(x,y)∨﹁Father(z,x)∨Father(z,y), Brother(John, Peter), Father(David, John)}
第二步：把问题用谓词公式表示出来，并将其否定与谓词ANSWER做析取。 设Peter的父亲是u，则有：Father(u, Peter) 将其否定与ANSWER做析取，得
G: ﹁Father(u, Peter) ∨ ANSWER(u)
第三步：将上述公式G化为子句集S2，并将S1和S2合并到S。 S2={﹁Father(u, Peter) ∨ ANSWER(u)} S=S1∪S2
将S中各子句列出如下：
（1）﹁Brother(x,y)∨﹁Father(z,x)∨Father(z,y) （2）Brother(John, Peter) （3）Father(David, John)
（4）﹁Father(u, Peter) ∨ ANSWER(u) 第四步：应用归结原理进行归结。
（5）﹁Brother(John,y) ∨ Father(David,y)
（1）与（3）归结，σ={ David/z, John/x}
（6）﹁Brother(John, Peter) ∨ ANSWER(David)
（4）与（5）归结，σ={ David/u, Peter/y}
（7）ANSWER(David) （2）与（6）归结
第五步：得到了归结式ANSWER(David)，答案即在其中，所以u=David,即Peter的父亲是David。
第4部分 搜索策略
本章小结：
广度优先搜索 深度优先搜索 盲目搜索 状态空间 搜索策略 有界深度优先搜索 代价树的广度优先搜索 代价树的深度优先搜索 局部择优搜索 启发式搜索 搜索策略 A*算法 广度优先搜索 盲目搜索 与/或树 搜索策略 有序搜索 特殊情况 提高搜索效率的方法 全局择优搜索 深度及有界深度优先搜索 博弈问题
α-β剪枝技术 博弈问题：
极大极小分析法：计算出端节点的估值，再推算出父节点的得分。
推算的方法是：对“或”节点，选其子节点中一个最大的得分作为父节点的得分，这是为了使自己在可供选择的方案中选一个对自己最有利的方案；对“与”节点，选其子节点中一个最小的得分作为父节点的得分，这是为了立足于最坏的情况。这样计算出的父节点的得分称为倒推值。
α-β剪枝技术：
对于一个“与”节点来说，它取当前子节点中的最小倒推值作为它倒推值的上界，称此值为
β值。对于一个“或”节点来说，它取当前子节点中的最大倒推值作为它倒推值的下界，称此值为α值。 其一般规律为:（1）任何“或”节点x的α值如果不能降低其父节点的β值，则对节点x以下的分枝可停止搜索，并使x的倒推值为α。这种剪枝成为β剪枝。
（2）任何“与”节点x的β值如果不能升高其父节点的α值，则对节点x以下的分枝可停止搜索，并使x的倒推值为β。这种剪枝成为α剪枝。
习题解答:
1 图4-1是五城市间的交通路线图，A城市是出发地，E城市是目的地，两城市间的交通费用（代价）如
图中数字所示。求从A到E的最小费用交通路线。
图4-1
解：先将交通图转换为代价树，如图4-2所示。
若用g(x)表示从初始节点s0到节点x的代价，用c(x1,x2)表示从父节点x1到子节点x2的代价，则有：
g(x2)=g(x1)+c(x1,x2)
A 3 C1 2 D13 4 B2 5 E4 2 C2 4 4 B1 5 D2 3 E3 E1 E2 图4-2
方法一：代价树的广度优先搜索
（扩展节点ｎ，将其子节点放入open表中，计算各子节点的代价，并按各节点的代价对open表中全部节点按从小到大的顺序进行排序（队列）） 步骤如下：
图4-3-1
图4-3-2
图4-3-3