人工智能经典习题集及各章总结(期末考试必备) 下载本文

图4-3-4

所以,最优路径为A->C->D->E

图4-3-5

方法二:代价树的深度优先搜索(不一定是最优解)

(扩展节点n,将其子节点按代价从小到大的顺序放到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->C->D->E

虽然D1的代价大于B1的代价,但按照代价

树的深度优先搜索策略,要对D1进行扩展,放入closed表中(若按代价树的广度优先搜索,要对B1、D1排序,先扩展B1)

注:该题代价树的深度优先搜索与代价树的广度优先搜索的结果相同,但这只是巧合。一般情况下,这两种方法得到的结果不一定相同。另外,由于代价树的深度优先搜索有可能进入无穷分支的路径,因此它是不完备的。

2 如下图4-5所示,分别用代价树的广度优先搜索策略和代价树的深度优先搜索策略,

求A到E的最短费用路径。

A 6 B 5 7 7 C 8 D 6 E 图4-5

解:先将其化成代价树,如图4-6:

A 6 B1 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