2 C B 2 A 2 3 3 3 1 1 1 4 4 4 1 C 2 B 4 A 2 3 1 3 1 4 2 4 3
初始状态S0 目标状态Sg
图 4-31 圆盘问题
解：设用qA，qB和qC分别表示把A盘，B盘和C盘绕轴逆时针转动90o，这些操作（算符）的排列顺序是qA，qB，qC。
应用广度优先搜索，可得到如下搜索树。在该搜索树中，重复出现的状态不再划出，节点旁边的标识Si，i=0,1,2,…，为按节点被扩展的顺序给出的该节点的状态标识。
由该图可以看出，从初始状态S0到目标状态Sg的路径是 S0→2→5→13(Sg)
21
qA 2 S1 2 1 3 3 24 11 3 4 4 qB 2 S0 C 2 B 2 A 1 1 1 3 3 3 4 4 4 2 1 2 4 3 4 qB S6 qC S3 1 2 2 2 3 3 1 1 4 4 4 3 S2 3 2 3 qC 1 4 1 qA 2 1 S4 S5 2 22 1 1 1 3 3 1 4 3 1 1 3 2 2 4 4 1 23 24 14 3 1 3 2 3 3 4 3 4 4 3 4 qA 2 2 3 qB S10 2 4 2 4 2 4 S7 1 3 1 2 2 3 1 1 2 4 3 3 S8 1 4 4 qC qC 2 1 4 S11 1 S12即Sg 2 4 3 3 4 2 1 1 3 2 1 3 1 4 3 4 1 2 3 1 1 2 2 4 4 3 3 4 4 4.7题的广度优先搜索树
其深度优先搜索略。
S9 4 2 2 1 3 3 1 1 3 4 4 2 4.8 图4-32是5个城市的交通图，城市之间的连线旁边的数字是城市之间路程的费用。要求从A城出发，经过其它各城市一次且仅一次，最后回到A城，请找出一条最优线路。
解：这个问题又称为旅行商问题（travelling salesman problem, TSP）或货郎担问题，是一个较有普遍性的实际应用问题。根据数学理论，对n个城市的旅行商问题，其封闭路径的排列总数为：
(n!)/n=(n-1)!
其计算量相当大。例如，当n=20时，要穷举其所有路径，即使用一个每秒一亿次的计算机来算也需要350年的时间。因此，对这
22
A 10 B 2 8 9 C 11 6 3 12 8 D 9 E 4-32 交通费用图
类问题只能用搜索的方法来解决。
下图是对图4-32按最小代价搜索所得到的搜索树，树中的节点为城市名称，节点边上的数字为该节点的代价g。其计算公式为
g(ni+1)=g(ni)+c(ni, ni+1)
其中，c(ni,ni+1)为节点ni到ni+1节点的边代价。
3 8 C 18 8
B 10 12 6 D 22
16 E 8 10 C 2 3
8 E 10 6 9 2 A 0 9 11 D 9 12 3 B 21 8 6
9 18 E 6 B 17 E 11 8 9 C 19
20 D B 10 D 5 12 6
C 12 8 8
8 12 3 12
8 12 9 6 8 3 8 9 23 31 29 25 22 16 19 20 20 C 25 D B 32 C C E 16 B E D D B E
22
21 24 14 26 B 24 27 D E 26 20 27 C D 25 B 17 E C C E B D 8 8 9 9 12 12 3 6 6
8 6 6 12 9 8 9 3 3 31 27 28 31 26 31 E 33 E D D B E 26 B 28 B D
32 B 34 30 23 20 C E D 27 C 28 E D 35 B E 28
可以看出，其最短路经是 A-C-D-E-B-A 或
A-B-E-D-C-A 其实，它们是同一条路经。
4.11 设有如下结构的移动将牌游戏：
B B W W E 30 A 2 10 A 30
3 9 图4.32的最小代价搜索树
其中，B表示黑色将牌，W表是白色将牌，E表示空格。游戏的规定走法是：
(1) 任意一个将牌可移入相邻的空格，规定其代价为1；
(2) 任何一个将牌可相隔1个其它的将牌跳入空格，其代价为跳过将牌的数目加1。
游戏要达到的目标什是把所有W都移到B的左边。对这个问题，请定义一个启发函数h(n)，并给出用这个启发函数产生的搜索树。你能否判别这个启发函数是否满足下解要求？再求出的搜索树中，对所有节点是否满足单调限制？
解：设h(x)=每个W左边的B的个数，f(x)=d(x)+3*h(x)，其搜索树如下：
23
f(x)=0+12=12
f(x)=2+12=14
B B E W W B B W W E f(x)=1+12=13 B B W E W B B E W W f(x)=1+12=13 f(x)=2+9=11 B E W B W f(x)=3+9=12 E B W B W f(x)=4+6=10 W B E B W f(x)=5+3=8 W B W B E W B W E B f(x)=6+3=9 f(x)=7+0=7 W B W E B 4.14 设有如图4-34的与/或/树，请分别按和代价法及最大代价法求解树的代价。
5 B 7 D 2 t1
2 E 3 t2
A 6 C 2 t3 1 t4 图4.34 习题4.14的与/或树
解：若按和代价法，则该解树的代价为： 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
24
4.15 设有如图4-35所示的博弈树，其中最下面的数字是假设的估值，请对该博弈树作如下工作：
(1) 计算各节点的倒推值；
(2) 利用α-β剪枝技术剪去不必要的分枝。
S0 A B
C G H I D J K E L M F N
0 5 -3 3 3 6 6 -2 3 5 4 -3 0 6 8 9 -3 图4.35 习题4.15的博弈树
解：各节点的倒推值和剪枝情况如下图所示：
≥4 ≤0 A S0 B
≤4 ≥0 ≤0 G C ≤-3 H ≤3 ≥3 I D J ≤4 ≥4 E L ≤6 ≥6 M F K ≤-3 N
0 5 -3 3 3 3 6 6 -2 3 5 4 -3 0 6 8 9 -3
习题4.15的倒推值和剪枝情况
第5章 计算智能部分参考答案
5.15 对遗传法的选择操作：设种群规模为4，个体采用二进制编码，适应度函数为 f(x)=x，初始种群情况如下表所示：
25
2