qA 2 S1 2 1 3 3 24 11 3 4 4 qB 2 S0 C 2 B 2 A 3 3 1 1 1 3 4 4 4 2 1 2 4 3 4 qC S3 1 2 2 2 3 3 1 1 4 4 4 3 S2 3 2 3 qC 1 4 1 qA qB 2 1 S4 S 2 5S6 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 4 3 4 2
4.8 图4-32是5个城市的交通图，城市之间的连线旁边的数字是城市之间路程的费用。要求从A城出发，经过其它各城市一次且仅一次，最后回到A城，请找出一条最优线路。
解：这个问题又称为旅行商问题（travelling salesman problem, TSP）或货郎担问题，是一个较有普遍性的实际应用问题。根据数学理论，对n个城市的旅行商问题，其封闭路径的排列总数为：
(n!)/n=(n-1)!
其计算量相当大。例如，当n=20时，要穷举其所有路径，即使用一个每秒一亿次的计算机来算也需要350年的时间。因此，对这类问题只能用搜索的方法来解决。
下图是对图4-32按最小代价搜索所得到的搜索树，树中的节点为城市名称，节点边上的数字为该节点的代价g。其计算公式为
g(ni+1)=g(ni)+c(ni, ni+1)
21
A 10 B 2 8 9 C 11 6 3 12 8 D 9 E 4-32 交通费用图
其中，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 2 A 0 9 11 D 9 12 3 B 21
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 6 9 12 8 6 8 12 6 8 9 3 8 9 23 29 22 16 19 20 20 C 25 D B 32 C C 25 E 31 16 B E D D B E
22
21 24 14 26 B 24 27 25 17 D E 26 20 27 C D B 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 33 26 31 E E D D B E B B D 28
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 2 30 A
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)，其搜索树如下 f(x)=2+12=14 22 B B E W W B E W B W B B W W E f(x)=0+12=12 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 f(x)=3+9=12
4.14 设有如图4-34的与/或/树，请分别按和代价法及最大代价法求解树的代价。
W B W E B W B W E B W B E B W E B W B W f(x)=4+6=10 f(x)=5+3=8 W B W B E f(x)=6+3=9 f(x)=7+0=7 5 B 7 D 2 t1 2 E 3 t2 A 6 C 1 t4 2 t3 图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
4.15 设有如图4-35所示的博弈树，其中最下面的数字是假设的估值，请对该博弈树作如下工作：
(1) 计算各节点的倒推值；
(2) 利用α-β剪枝技术剪去不必要的分枝。
23
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 N K ≤-3 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)=x2，初始种群情况如下表所示：
编号 S01 S02 S03 S04 个体串 1010 0100 1100 0111 x 10 4 12 7 适应值 百分比 累计百分比 选中次数 若规定选择概率为100%,选择算法为轮盘赌算法，且依次生成的4个随机数为0.42, 0.16, 0.89, 0.71，请填
24
写上表中的全部内容，并求出经本次选择操作后所得到的新的种群。
解：表格的完整内容为：
编号 S01 S02 S03 S04 S01=1100 S02=1010 S03=0111 S04=1100
5.18 设某小组有5个同学，分别为S1,S2,S3,S4,S5。若对每个同学的“学习好”程度打分：
S1:95 S2:85 S3:80 S4:70 S5:90
这样就确定了一个模糊集F，它表示该小组同学对“学习好”这一模糊概念的隶属程度，请写出该模糊集。 解：对模糊集为F，可表示为：
F=95/ S1+85/S2+80/ S3+70/S4+90/S5或 F={95/ S1, 85/S2, 80/ S3, 70/S4, 90/S5} 5.19 设有论域
U={u1, u2, u3, u4, u5}
并设F、G是U上的两个模糊集，且有 F=0.9/u1+0.7/u2+0.5/u3+0.3/u4 G=0.6/u3+0.8/u4+1/u5 请分别计算 F∩G，F∪G，﹁F。
解：F∩G=(0.9∧0)/ u1+(0.7∧0)/ u2+(0.5∧0.6)/u3+(0.3∧0.8)/u4+(0∧1)/u5 =0/ u1+0/ u2+0.5/u3+0.3/u4+0/u5 =0.5/u3+0.3/u4
F∪G=(0.9∨0)/ u1+(0.7∨0)/ u2+(0.5∨0.6)/u3+(0.3∨0.8)/u4+(0∨1)/u5
=0.9/ u1+0.7/ u2+0.6/u3+0.8/u4+1/u5
﹁F=(1-0.9)/ u1+(1-0.7)/ u2+(1-0.5)/u3+(1-0.3)/u4+(1-0)/u5
=0.1/ u1+0.3/ u2+0.5/u3+0.7/u4+1/u5 5.21设有如下两个模糊关系：
个体串 1010 0100 1100 0111 x 10 4 12 7 适应值 100 16 144 49 百分比 32.36 5.18 44.60 15.86 累计百分比 32.36 37.54 84.14 100 选中次数 1 0 2 1 本次选择后所得到的新的种群为：
?0.30.70.2?R1??100.4?????00.51??请写出R1与R2的合成R1οR2。
?0.20.8?R2??0.60.4?????0.90.1?? 解：R(1,1)=(0.3∧0.2)∨(0.7∧0.6)∨(0.2∧0.9)= 0.2∨0.6∨0.2=0.6
R(1,2)=(0.3∧0.8)∨(0.7∧0.4)∨(0.2∧0.1)= 0.3∨0.4∨0.1=0.4 R(2,1)=(1∧0.2)∨(0∧0.6)∨(0.4∧0.9)= 0.2∨0∨0.4=0.4 R(2,2)=(1∧0.8)∨(0∧0.4)∨(0.4∧0.1)= 0.8∨0∨0.1=0.8
25