第4章 搜索策略部分参考
答案
八年级地理上册填图题岩土工程勘察试题省略号的作用及举例应急救援安全知识车间5s试题及答案
4.5 有一农夫带一条狼，一只羊和一框青菜与从河的左岸乘船倒右岸，但受到下列条件的限制：
(1) 船太小，农夫每次只能带一样东西过河；
(2) 如果没有农夫看管，则狼要吃羊，羊要吃菜。
请
设计
领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计
一个过河
方案
气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载
，使得农夫、浪、羊都能不受损失的过河，画出相应的状态空间图。
题示：(1) 用四元组（农夫，狼，羊，菜）表示状态，其中每个元素都为0或1，用0表示在左岸，用1表示在右岸。
(2) 把每次过河的一种安排作为一种操作，每次过河都必须有农夫，因为只有他可以划船。
解：第一步，定义问题的描述形式
用四元组S=（f，w，s，v）表示问题状态，其中，f，w，s和v分别表示农夫，狼，羊和青菜是否在左岸，它们都可以取1或0，取1表示在左岸，取0表示在右岸。
第二步，用所定义的问题状态表示方式，把所有可能的问题状态表示出来，包括问题的初始状态和目标状态。
由于状态变量有4个，每个状态变量都有2种取值，因此有以下16种可能的状态：
S0=(1,1,1,1)，S1=(1,1,1,0)，S2=(1,1,0,1)，S3=(1,1,0,0)
S4=(1,0,1,1)，S5=(1,0,1,0)，S6=(1,0,0,1)，S7=(1,0,0,0)
S8=(0,1,1,1)，S9=(0,1,1,0)，S10=(0,1,0,1)，S11=(0,1,0,0)
S12=(0,0,1,1)，S13=(0,0,1,0)，S14=(0,0,0,1)，S15=(0,0,0,0)
其中，状态S3，S6，S7，S8，S9，S12是不合法状态，S0和S15分别是初始状态和目标状态。
第三步，定义操作，即用于状态变换的算符组F
由于每次过河船上都必须有农夫，且除农夫外船上只能载狼，羊和菜中的一种，故算符定义如下：
L(i)表示农夫从左岸将第i样东西送到右岸（i=1表示狼，i=2表示羊，i=3表示菜，i=0表示船上除农夫外不载任何东西）。由于农夫必须在船上，故对农夫的表示省略。
R (i)表示农夫从右岸将第i样东西带到左岸（i=1表示狼，i=2表示羊，i=3表示菜，i=0表示船上除农夫外不载任何东西）。同样，对农夫的表示省略。
这样，所定义的算符组F可以有以下8种算符：
L (0)，L (1)，L (2)，L (3)
R(0)，R(1)，R (2)，R (3)
第四步，根据上述定义的状态和操作进行求解。
该问题求解过程的状态空间图如下：
4.7 圆盘问题。设有大小不等的三个圆盘A、B、C套在一根轴上，每个盘上都标有数字1、2、3、4，并且每个圆盘都可以独立的绕轴做逆时针转动，每次转动90°，其初始状态S0和目标状态Sg如图4-31所示，请用广度优先搜索和深度优先搜索，求出从S0到Sg的路径。
初始状态S0 目标状态Sg
图 4‑31 圆盘问题
解：设用qA，qB和qC分别表示把A盘，B盘和C盘绕轴逆时针转动90º，这些操作（算符）的排列顺序是qA，qB，qC。
应用广度优先搜索，可得到如下搜索树。在该搜索树中，重复出现的状态不再划出，节点旁边的标识Si，i=0,1,2,…，为按节点被扩展的顺序给出的该节点的状态标识。
由该图可以看出，从初始状态S0到目标状态Sg的路径是
S0→2→5→13(Sg)
其深度优先搜索略。
4.8 图4-32是5个城市的交通图，城市之间的连线旁边的数字是城市之间路程的费用。要求从A城出发，经过其它各城市一次且仅一次，最后回到A城，请找出一条最优线路。
A 10 B
2 8
9 C 11 6
3 12 8
D 9 E
4‑32 交通费用图
解：这个问题又称为旅行商问题（travelling salesman problem, TSP）或货郎担问题，是一个较有普遍性的实际应用问题。根据数学理论，对n个城市的旅行商问题，其封闭路径的排列总数为：
(n!)/n=(n-1)!
其计算量相当大。例如，当n=20时，要穷举其所有路径，即使用一个每秒一亿次的计算机来算也需要350年的时间。因此，对这类问题只能用搜索的方法来解决。
下图是对图4-32按最小代价搜索所得到的搜索树，树中的节点为城市名称，节点边上的数字为该节点的代价g。其计算
公式
小学单位换算公式大全免费下载公式下载行测公式大全下载excel公式下载逻辑回归公式下载
为
g(ni+1)=g(ni)+c(ni, ni+1)
其中，c(ni,ni+1)为节点ni到ni+1节点的边代价。
可以看出，其最短路经是
A-C-D-E-B-A
或
A-B-E-D-C-A
其实，它们是同一条路经。
4.11 设有如下结构的移动将牌游戏：
B
B
W
W
E
其中，B表示黑色将牌，W表是白色将牌，E表示空格。游戏的规定走法是：
(1) 任意一个将牌可移入相邻的空格，规定其代价为1；
(2) 任何一个将牌可相隔1个其它的将牌跳入空格，其代价为跳过将牌的数目加1。
游戏要达到的目标什是把所有W都移到B的左边。对这个问题，请定义一个启发函数h(n)，并给出用这个启发函数产生的搜索树。你能否判别这个启发函数是否满足下解要求？再求出的搜索树中，对所有节点是否满足单调限制？
解：设h(x)=每个W左边的B的个数，f(x)=d(x)+3*h(x)，其搜索树如下：
B
B
W
W
E
B
B
E
W
W
B
B
W
E
W
B
B
E
W
W
B
E
W
B
W
E
B
W
B
W
W
B
E
B
W
W
B
W
B
E
W
B
W
E
B
W
E
W
B
B
4.14 设有如图4-34的与/或/树，请分别按和代价法及最大代价法求解树的代价。
解：若按和代价法，则该解树的代价为：
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}
=max((5+5, 2+6)=10
4.15 设有如图4-35所示的博弈树，其中最下面的数字是假设的估值，请对该博弈树作如下工作：
(1) 计算各节点的倒推值；
(2) 利用α-β剪枝技术剪去不必要的分枝。
解：各节点的倒推值和剪枝情况如下图所示：
12
E
D
25
24
8
9
D
C
31
25
9
3
E
C
26
21
8
3
E
D
9
8
6
18
12
21
9
3
12
10
5
10
8
3
16
22
18
6
12
8
8
11
9
2
D
C
B
E
C
B
E
D
B
E
D
C
11
9
2
10
10
0
E
6
2
1
3
1
3
1
D
3
3
23
1
4
C
3
23
3
23
B
A
4.7题的广度优先搜索树
qC
3
3
1
4
2
4
2
4
1
3
2
3
1
qB
4
3
2
1
3
2
1
1
4
13
4
qC
qB
4
2
3
1
1
3
1
4
4
2
22
2
3
qA
4
4
2
4
2
2
1
1
3
1
3
3
qC
qB
qA
C
B
A
4
3
4
4
1
4
3
4
4
3
2
1
4
2
1
4
2
4
2
4
1
1
3
3
2
4
3
4
2
1
2
1
4
1
3
2
3
4
4
3
2
2
2
4
4
4
2
4
1
3
qA
4
4
2
2
1
1
3
1
2
4
3
3
qC
4
4
2
2
1
1
4
3
2
3
3
1
3
2
1
4
3
2
1
1
4
1
23
13
3
3
4
4
4
4
3
3
3
1
1
1
2
2
2
1
3
3
1
3
4
3
2
2
1
2
4
3
1
B
A
A
B
2
2
2
2
2
2
2
1
C
C
f(x)=7+0=7
f(x)=6+3=9
f(x)=5+3=8
f(x)=4+6=10
f(x)=3+9=12
f(x)=2+9=11
f(x)=2+12=14
f(x)=1+12=13
f(x)=1+12=13
f(x)=0+12=12
16
B
C
12
17
9
14
B
D
6
9
16
19
C
E
8
6
20
27
B
E
8
8
20
20
C
B
8
6
26
24
C
D
8
12
17
25
29
B
D
8
3
19
20
27
22
B
C
12
3
32
23
B
6
20
A
10
30
D
28
A
2
30
12
28
D
9
27
E
B
12
31
E
E
8
28
E
6
26
B
6
26
9
E
30
B
8
31
B
12
34
D
3
28
C
8
32
D
3
27
图4.32的最小代价搜索树
D
9
35
E
8
33
E
9
31
图4.34 习题4.14的与/或树
t1
E
t4
t3
t2
D
C
B
A
5
6
2
1
7
2
2
3
3
-3
3
(1,1,1,0)
0
5
R(0)
-3
图4.35 习题4.15的博弈树
5
-2
6
3
L(3)
(1,1,l,1)
R(2)
4
0
6
8
9
-3
3
6
A
S0
L(2)
(0,1,0,1)
(1,1,0,1)
(0,0,0,1)
(1,0,1,1)
(0,1,0,0)
L(1)
R(2)
B
C
D
E
F
G
H
I
J
K
L
N
N
M
K
J
I
H
G
F
E
D
C
B
A
S0
≥6
≤6
≤-3
≥4
≤4
≥4
≤4
≥3
≤3
9
≤-3
≤0
≥0
≤0
6
3
-3
8
6
0
-3
4
5
3
-2
6
3
-3
5
0
3
习题4.15的倒推值和剪枝情况
(0,0,1,0)
L(3)
L(2)
(1,0,1,0)
R(0)
(0,0,0,0)
L(2)
M
L
S0
S1
S2
S3
S4
S5
S6
S7
S8
S9
S10
S11
S12即Sg
6
23
268
5
浙公网安备 33021202002483