图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