注：深度优先搜索是不完备的，即使问题有解，也不一定能求得解。得到的解也不一定是最优解（因为是局部优先搜索）。

3 下图是五城市间的交通费用图，若从西安出发，要求把每个城市都访问一遍，最后到达广州，请找一条最优路线。边上的数字是两城市间的交通费用。

北京B 80 120 150 95 75 160 上海D 130 70 170 A西安 S0 昆明C 90 广州E Sg

图4-9 解：先画出代价树：

A 80 95 120 150 B1 170 75 160 170 C1 90 130 75 D1 70 130 E1 C2 130 90 130 D2 70 E2 75 B2 160 75 D3 70 E3 B3 C3 E4 D4 E5 C4 90 E6 D5 E7 B4 E8 C5 E9 B5 E10 E11 E12 E13 E14 E15 E16 图4-10

按代价树的广度优先搜索即可得出最优路线，步骤如下：

A B1 80 95 C1 120 D1 E1 150 图4-11-1

A 80 B1 95 C1 120 D1 E1 150 C2 250 D2 155 E2 240 图4-11-2

C2 250

80

A B1 95 C1 120 D1 E1 150 D2 155 E2 240 B2 265 D3 225 E3 185 图4-11-3

A 80 B1 95 C1 120 D1 E1 150 C2 250 D2 155 E2 240 B2 265 D3 225 E3 185 B3 195 C3 250 E4 190 图4-11-4

A 80 B1 95 C1 120 D1 E1 150 C2 250 155 D2 E2 240 B2 265 D3 225 E3 185 B3 195 C3 250 E4 190 D4 380 E5 340 C4 285 E6 225 D5 340 E7 425 B4 300 E8 295 C5 365 E9 355 B5 420 E10 340 E12 375 图4-11-5

故由此得出最优路线为A->B1->D2->C4->E12 即A->B->D->C->E，交通费用为375。

4 设有如图所示的一棵与/或树，请分别用与/或树的广度优先搜索及与/或树的深度优先搜索求出解树。

A B D t1 t2 t5 C t3 t4

解：（1）与/或树的广度优先搜索

先扩展节点A,得到节点B和C，再扩展节点B,得节点t1、t2，因为t1、t2为可解节点，故节点B可解，从而可节点A可解。 所以求得解树为：

（2）与/或树的深度优先搜索

先扩展节点A, 得到节点B和C,再扩展节点C, 得节点D和t5,t5为可解节点，再扩展节D，得节点t3、t4，因为t3、t4为可解节点，故节点D可解，因为节点D和t5可解，故节点C可解，从而可节点A可解。 所以求得解树为：

5 设有如图所示的与/或树，请分别按和代价法及最大代价法求解树代价。

A B t1 t2 A C D t5 t3 t4