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 E3 185 195 250 190 E1 150 C2 250 D2 155 E2 240 B2 265 D3 225 B3 C3 E4 图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可解。 所以求得解树为：
A B t1 t2
（2）与/或树的深度优先搜索
先扩展节点A, 得到节点B和C,再扩展节点C, 得节点D和t5,t5为可解节点，再扩展节D，得节点t3、t4，因为t3、t4为可解节点，故节点D可解，因为节点D和t5可解，故节点C可解，从而可节点A可解。 所以求得解树为：
5 设有如图所示的与/或树，请分别按和代价法及最大代价法求解树代价。
A C D t5 t3 t4
5 B 2 D A 6 C 1 7 2 2 3 t3 t4 t1 t2
（1） （2）
按和代价法：h(B)=7,h(C)=3,h(A)=7+3+5+6=21 按最大代价法：h(B)=5,h(C)=2,h(A)=5+5=10