CA 1
DA 1
CLOSED 节 父深 点 节度 A 0
B A1
深度优先
A
A
B
B
D
CD
C
I E
IE
G
F
OPEN 节父 深 点节 度 A 0 BA 1
I B2
CB 2
CA 1
DA 1
CLOSED 节 父深 点 节度 A 0
B A1 I B2 C A1
深度优先
A
A
B
B
D
CD
C
I E
IE
G G
OPEN 节父 深 点节 度 A 0 BA 1
t4
解：（1）与/或树的广度优先搜索
先扩展节点A,得到节点B和C，再扩展节点B,得节点t1、
t2，因为t1、t2为可解节点，故节点B可解，从而可节点
A可解。
所以求得解树为：
A
B
t1
t2
（2）与/或树的深度优先搜索 先扩展节点A, 得到节点B和C,再扩展节点C, 得节点D和t5,t5 为可解节点，再扩展节D，得节点t3、t4，因为t3、t4为可解 节点，故节点D可解，因为节点D和t5可解，故节点C可解， 从而可节点A可解。 所以求得解树为：
-3
6 M
α剪枝
β剪枝
N
α剪枝
0 5 -3 3 3 6 -2 3 5 4 -3 0 6 8 9 -3
1、已知下列事实： （1）超市（Supermarket）卖（Sail）的商品(Goods)便宜(Cheap)。 （2）王（Wang）买（Buy）需要的（Want）便宜商品。 （3）自行车（Bicycle）是商品且超市卖自行车。 （4）王需要自行车。 （5）赵（Zhao）跟随王买同样的商品。 请应用归结反演证明方法回答以下问题： （1）王买自行车吗？ （2）赵买什么商品？
迷宫问题： 分别用宽度优先、深度优先和有界深度
搜索算法求A——F的路径,列出搜索中OPEN、
CLOSED表的内容 。 要求：深度值相同时，按字母序扩展
A
有界深度dm=3
B D
C
I
E
G
F
宽度优先
A
A
B
B
D
CD
C
I
I
E
E
OPEN
节父 深 点节 度 A 0 BA 1
CA 1
DA 1
I B2 CB 2
EC 2
A C
D t5
t3
t4
3.设有如图所示与或树，分 别用和代价法、最大代 价法求解树的代价。
A
5
6
B
72
2
D
E 2 3 t3
t1
t2
C 1
t4
若按和代价法，则该解树的代价为： h(A)=2+3+2+5+2+1+6=21
若按最大代价法，则该解树的代价为： h(A)=max{h(B)+5, h(C)+6} = max{(h(E)+2)+5, h(C)+6} = max{(max(2, 3)+2)+5, max(2, 1)+6}
I B2
CB 2
CA 1 EC 2
DA 1
CLOSED 节 父深 点 节度 A 0
B A1 I B2 C A1 EC 2
F
深度优先
A
A
B
B
D
CD
C
I E
IE
G G
F F
OPEN 节父 深 点节 度 A 0 BA 1
I B2 CB 2
CA 1 EC 2
GE 3 DA 1
CLOSED 节 父深 点 节度 A 0
GE 3 DA 1
GD 2 FG 3
设有如下结构的移动将牌游戏：
B B WWE
其中，B表示黑色将牌，W表是白色将牌，E表示空格。游戏的 规定走法是：
(1) 任意一个将牌可移入相邻的空格，规定其代价为1； (2) 任何一个将牌可相隔1个其它的将牌跳入空格，其代价为 跳过将牌的数目加1。 游戏要达到的目标是把所有W都移到B的左边。对这个问题， 请定义一个启发函数h(n)，并给出用这个启发函数产生的搜索 树。
B B E WW B E WB W
f=3+3*3=12
E B WB W
f=4+3*2=10
WB E B W
f=5+3*1=8
WB WB E
f=6+3*1=9
WB WE B
f=7+0=7
WE WB B
2.设有如图所示与或树，请 分别用与或树的广度优 先和深度优先搜索求出 解树。
A
B
C
D
t1
t2
t5
t3
B A1 I B2 C A1 EC 2
GE 3
深度优先
A
A
B
B
D
CD
C
I E
IE
G G
FБайду номын сангаас
解为：FA-C-E-G-F
OPEN 节父 深 点节 度 A 0 BA 1 I B2 CB 2 CA 1 EC 2 GE 3 FG 4 DA 1
CLOSED 节 父深 点 节度 A0
B A1 I B2 C A1 EC 2
定义谓词 Goods(x): x是商品 Cheap(x)：x便宜 Sail(super,x)：超市卖x Buy(x,y)：x买y Want(x,y) ：x需要y
用谓词写事实、规则 超市（Supermarket）卖（Sail）的商品(Goods)便宜(Cheap)： (x)( Sail(super，x) Goods(x) Cheap(x)) 王（Wang）买（Buy）需要的（Want）便宜商品： (x)( Want(Wang，x) cheap(x) Buy(Wang，x)) 自行车（Bicycle）是商品且超市卖自行车： Goods（bike）Sail(super，bike) 王需要自行车： Want（Wang，bike） 赵（Zhao）跟随王买同样的商品： (x)( Goods(x) Buy(Wang，x) Buy(Zhao，x)) Q1：Buy(Wang，bike) ～Q1：～Buy(Wang，bike) Q2：Buy(Zhao，a) 构造其重言式：Q2∨～Q2: Buy(Zhao，a) ∨～Buy(Zhao，a)
G
G
GD 2
在OPEN表中调整C的父指针 G E 3 在OPEN表中调整G的父指针 F G 3
F
F
解为：A-D-G-F
CLOSED 节 父深 点 节度 A 0 BA 1 CA 1 DA 1 I B2 EC 2 GD 2 FG 3
深度优先
A
A
B
B
D
CD
C
I
I
E
G
F
OPEN 节父 深 点节 度 A 0 BA 1
GE 3 FG 4
有界深度优先
A
A
B
B
D
CD
C
I E
I E
G
G
F
F
在CLOSED表中调整G的父指针
解为：A-D-G-F
OPEN 节父 深 点节 度 A 0 BA 1 I B2 CB 2 CA 1 EC 2 GE 3 DA 1
GD 2 FG 3
CLOSED 节 父深 点 节度 A0
B A1 I B2 C A1 EC 2
解：启发函数h(n)=每个w左边B的个数，f(n)=d(n)+3*h(n)
W可以移到B右边的三种情况：
EBW
代价：2 B E W
代价：3
B WE
代价：2
f=1+3*4=13
B B WWE
f=0+3*4=12 f=1+3*4=13
B B WE W
B B E WW
f=2+3*4=14
f=2+3*3=11
=max{(5+5, 2+6)}=10
设有如图博弈树，其中最下面的数字是假设的估值，（1） 计算各节点的倒推值；
（2）利用α-β剪枝技术剪去不必要的分枝
β≤ 0
α≥ 0 A0
4 S0 β≤ 4
4 B
α≥ 0 C0
D
3 α≥
3
α≥E4
4
6 F
α≥
6
0G
H
-3 β≤ -3
I
3
J
β剪枝
K 4
β≤
L -3