发布时间 : 星期三 文章人工智能经典习题集及各章总结（期末考试必备）更新完毕开始阅读78b5c6d64431b90d6d85c772
图4-3-4
所以，最优路径为A->C->D->E
图4-3-5
方法二：代价树的深度优先搜索（不一定是最优解）
（扩展节点ｎ，将其子节点按代价从小到大的顺序放到open表的首部（栈）） 步骤如下：
A C1 3 B1 4 图4-4-1
A C1 3 B1 4 2 D1 5 图4-4-2
A C1 3 B1 4 D1 5 3 4 E2 B2 8 9 图4-4-3
E为目标节点，E2->D1->C1->A 所以路径为A->Ｃ->Ｄ->Ｅ
虽然D1的代价大于B1的代价，但按照代价
树的深度优先搜索策略，要对D1进行扩展，放入closed表中（若按代价树的广度优先搜索，要对B1、D1排序，先扩展B1）
注：该题代价树的深度优先搜索与代价树的广度优先搜索的结果相同，但这只是巧合。一般情况下，这两种方法得到的结果不一定相同。另外，由于代价树的深度优先搜索有可能进入无穷分支的路径，因此它是不完备的。
２ 如下图４-5所示，分别用代价树的广度优先搜索策略和代价树的深度优先搜索策略，
求A到E的最短费用路径。
Ａ ６ Ｂ ５ ７ ７ Ｃ ８ Ｄ ６ Ｅ 图４－５
解：先将其化成代价树,如图4-6：
Ａ 6 Ｂ1 5 D1 7 C2 8 E4 图4-6
(1)代价树的广度优先搜索,步骤如下：
7 C1 7 D2 6 E2 5 B2 6 E3 8 E1 A 6 B1 C1 7 图4-7-1
A 6 B1 5 D1 11 图4-7-2
C1 7 A 6 B1 7 5 D1 11
C1 7 8 E1 15 D2 14 图4-7-3
E为目标节点，路径为A->C->E，代价为15。 （2）代价树的深度优先搜索,步骤如下：
虽然C1代价低于D1，但按照代价树的深度优先搜索策略，对D1进行扩展，放入closed表中，因为B1扩展的节点为D1，而C1是A节点扩展得到的。E出栈，为目标节点，结束。故解路径为A->B->D->E,代价为17，不是最优解。
A 6 B1 7 5 D1 11 图4-8-1
18 图4-8-2 7 C2 D1 A 6 B1 5 C1 C1 7 11 6 E2 17