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