人工智能考试复习资料(3)

其一般规律为:（1）任何“或”节点x的α值如果不能降低其父节点的β值，则对节点x以下的分枝可停止搜索，并使x的倒推值为α。这种剪枝成为β剪枝。

（2）任何“与”节点x的β值如果不能升高其父节点的α值，则对节点x以下的分枝可停止搜索，并使x的倒推值为β。这种剪枝成为α剪枝。 习题解答:

1 图4-1是五城市间的交通路线图，A城市是出发地，E城市是目的地，两城市间的交通费用（代价）如图中数字所示。求

从A到E的最小费用交通路线。

图4-1

解：先将交通图转换为代价树，如图4-2所示。

若用g(x)表示从初始节点s0到节点x的代价，用c(x1,x2)表示从父节点x1到子节点x2的代价，则有： g(x2)=g(x1)+c(x1,x2)

方法一：代价树的广度优先搜索

（扩展节点ｎ，将其子节点放入open表中，计算各子节点的代价，并按各节点的代价对open表中全部节点按从小到大的顺序进行排序（队列）） 步骤如下：

A 3 C1 2 D14 4 B1 5 3 D2 4 B2 5 2 C2 3 E3 E1 E2 E4 图4-2

图4-3-1

图4-3-2

图4-3-3

图4-3-4

图4-3-5

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

方法二：代价树的深度优先搜索（不一定是最优解）

（扩展节点ｎ，将其子节点按代价从小到大的顺序放到open表的首部（栈）） 步骤如下：

A C1 3 图4-4-1 B1 4

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

C1 2 D1 3 B1 4 树的深度优先搜索策略，要对D1进行扩展，放入closed表中（若按代价树的广度优先搜索，要对B1、D1排序，先扩展B1）

5 图4-4-2

A C1 3 B1 4 D1 3 E2 8 5 4 B2 9 图4-4-3

E为目标节点，E2->D1->C1->A 所以路径为A->Ｃ->Ｄ->Ｅ

注：该题代价树的深度优先搜索与代价树的广度优先搜索的结果相同，但这只是巧合。一般情况下，这两种方法得到的结果不一定相同。另外，由于代价树的深度优先搜索有可能进入无穷分支的路径，因此它是不完备的。 ２ 如下图４-5所示，分别用代价树的广度优先搜索策略和代价树的深度优先搜索策略，

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

Ａ ６ Ｂ ５ ７ ７ Ｃ ８ Ｄ ６ Ｅ 图４－５

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

Ａ 6 Ｂ1 7 C1 7 8 5 D1 D2 7 6 5 C2 E2 B2 8 E4 图4-6 (1)代价树的广度优先搜索,步骤如下： A 6 B1 C1 7 图4-7-1

A 6 B1 C1 7 7 8 5 D1 D2 E1 11 14 15

图4-7-3

E为目标节点，路径为A->C->E，代价为15。 （2）代价树的深度优先搜索,步骤如下： A 6 B1 C1 7 5

D1 图4-8-1 11 E1 6 E3 A 6 B1 C1 7 5 D1 11 图4-7-2

A 6 B1 C1 7 5 D1 11 7 6 C2 E2 18 17

虽然C1代价低于D1，但按照代价树的深度优先搜索策略，对D1进行扩展，放入closed表中，因为B1扩展的节点为D1，而C1是A节点扩展得到的。E出栈，为目标节点，结束。故解路径为A->B->D->E,代价为17，不是最优解。

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

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

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库人工智能考试复习资料(3)在线全文阅读。