2024年3月29日发(作者：笪婀)

代价树的广度优先搜索

< 人工智能 > 实 验 报 告 4 授课时间: 2011-2012 学年 第 1 学期 实验学

时: 3 专业班级: 计算机09-1 学生姓名No. 王丹0936040 实验题目: 代价树的

广度优先搜索—交通图 实验目的:

1(掌握代价树的广度优先搜索方法。

2(通过运用所学代价树的广度优先搜索知识来解答交通图的最短路径问题。

实验语言环境:

;，，与;语言

实验要求及内容:

如图是5城市之间交通路线图，A城市是出发地，E城市是目的地，两城市间

的交通费用(代价)如图中数字所示，求从A到E的最小费用路线。

B4A

345

2CD

3

E

解:采用代价树的广度优先搜索

1. 代价树的广度优先搜索的方法步骤:

(1)把初始节点S0放入OPEN，令g(S0)=0。

(2)检查OPEN是否为空，是，无解，退出。

(3)把OPEN第一个节点(并记该节点为n )取出放入CLOSED。

(4)考察节点n是否为目标节点，是，得解，退出。

(5)考察节点n是否可扩展，否，则转2)。

(6)扩展节点n ，将其子节点放入OPEN，并为每一个子节点都配一个指向父节

点的指针计算各子节点的代价，并按各节点的代价进行排序(从小到大)，然后转

2)。

?按各节点的代价进行排序(从小到大)

2.根据交通图，画出代价图 代价图:

3A4

C1B1

24 5

D1D2E1

3 4 2, 3E2B2C2E3

2024年3月29日发(作者：笪婀)

代价树的广度优先搜索

< 人工智能 > 实 验 报 告 4 授课时间: 2011-2012 学年 第 1 学期 实验学

时: 3 专业班级: 计算机09-1 学生姓名No. 王丹0936040 实验题目: 代价树的

广度优先搜索—交通图 实验目的:

1(掌握代价树的广度优先搜索方法。

2(通过运用所学代价树的广度优先搜索知识来解答交通图的最短路径问题。

实验语言环境:

;，，与;语言

实验要求及内容:

如图是5城市之间交通路线图，A城市是出发地，E城市是目的地，两城市间

的交通费用(代价)如图中数字所示，求从A到E的最小费用路线。

B4A

345

2CD

3

E

解:采用代价树的广度优先搜索

1. 代价树的广度优先搜索的方法步骤:

(1)把初始节点S0放入OPEN，令g(S0)=0。

(2)检查OPEN是否为空，是，无解，退出。

(3)把OPEN第一个节点(并记该节点为n )取出放入CLOSED。

(4)考察节点n是否为目标节点，是，得解，退出。

(5)考察节点n是否可扩展，否，则转2)。

(6)扩展节点n ，将其子节点放入OPEN，并为每一个子节点都配一个指向父节

点的指针计算各子节点的代价，并按各节点的代价进行排序(从小到大)，然后转

2)。

?按各节点的代价进行排序(从小到大)

2.根据交通图，画出代价图 代价图:

3A4

C1B1

24 5

D1D2E1

3 4 2, 3E2B2C2E3