代价树的广度优先搜索

《代价树的广度优先搜索》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、<人工智能>实验报告4授课时间：2011-2012学年第1学期实验学时：3专业班级：计算机09-1学生姓名No.王丹0936040实验题目：代价树的广度优先搜索—交通图实验目的：1．掌握代价树的广度优先搜索方法。2．通过运用所学代价树的广度优先搜索知识来解答交通图的最短路径问题。实验语言环境：ｃ＋＋与ｃ语言实验要求及内容：如图是5城市之间交通路线图，A城市是出发地，E城市是目的地，两城市间的交通费用(代价)如图中数字所示，求从A到E的最小费用路线。解：采用代价树的广度优先搜索1.代价树的广度优先搜索的方法步骤：

2、(1）把初始节点S0放入OPEN，令g(S0)=0。(2）检查OPEN是否为空，是，无解，退出。(3）把OPEN第一个节点（并记该节点为n）取出放入CLOSED。(4）考察节点n是否为目标节点，是，得解，退出。(5）考察节点n是否可扩展，否，则转2）。(6）扩展节点n，将其子节点放入OPEN，并为每一个子节点都配一个指向父节点的指针计算各子节点的代价，并按各节点的代价进行排序（从小到大），然后转2）。↘按各节点的代价进行排序（从小到大）2.根据交通图，画出代价图代价图：3.开始搜索oepn表存放刚刚生成的节点。

3、closed表存放将要扩展的节点或已经扩展过的节点。open表结构：[代价]

4、[节点]

5、[父节点]closed表结构：[序号]

6、[节点]

7、[父节点]1)把A放入open表open表：0

8、A

9、0      Closed表：空2)把A从open表放入closed表open表：空            closed表：1

10、A

11、03)扩展A，得C1，B1，放入open表C1的代价：3B1的代价：4Open表：3

12、C1

13、A 4

14、B1

15、Aclosed表：1

16、A

17、04)把C1从open表放到closed表Open表：4

18、B1

19、

20、A closed表：1

21、A

22、02

23、C1

24、AC1不是目标节点，于是继续扩展5)把C1扩展得到D1，放入open表D1的代价：3+2=5B1的代价：4open表：4

25、B1

26、A5

27、D1

28、C1closed表：1

29、A 

30、02

31、C1

32、A6)把B1从open放入closed表open表：5

33、D1

34、C1  closed表：1

35、A 

36、02

37、C1

38、A3

39、B1

40、AB1不是目标节点，于是继续扩展7)扩展B1得D2，E1，放入Open表D2的代价：4+4=8E1的代价：4+5=9open表：5

41、D1

42、C1 8

43、D2

44、B1       

45、     9

46、E1

47、B1            closed表：1

48、A

49、02

50、C1

51、A3

52、B1

53、A8)把D1从open表放入closed表open表：8

54、D2

55、B1 9

56、E1

57、B1            closed表：1

58、A

59、02

60、C1

61、A3

62、B1

63、A4

64、D1

65、C1D1不是目标节点，于是继续扩展9)把D1扩展得到E2，B2，放入open表E2的代价：3+2+3=8B2的代价：3+2+4=9D2的代价：8E1的代价：9open表：8

66、E2

67、D1 8

68、D2

69、B1            9

70、B2

71、D1       

72、     9

73、E1

74、B1             closed表：1

75、A

76、02

77、C1

78、A3

79、B1

80、A4

81、D1

82、C110)把E2从open表放入closed表open表：8

83、D2

84、B1           9

85、B2

86、D1            9

87、E1

88、B1            closed表：1

89、A

90、02

91、C1

92、A3

93、B1

94、A4

95、D1

96、C15

97、E2

98、D1    则搜索路径A-C1-D1-E2即：A-C-D-E分析总结：通过本次交通图的代价树的广度优先搜索，更好地掌握了代价树广度优先搜索的算法，代价树的广度优先

99、搜索的基本思想是：每次从OPEN表中选择节点往CLOSED表传递时，总是选择其代价为最小的节点。也就是说，OPEN表中的节点在任意时刻都是按其代价从小到大排序的，代价最小的节点排在最前面，代价最大的节点排在最后面，而不管节点在代价树中处于什么位置上。代价树的广度优先搜索的优点就是在问题的求解过程中总能找到解，并且能找到最优解。附代码：#include#includeusingnamespacestd;#defineint_max10000#defineinf9999#de

100、finemax20//…………………………………………邻接矩阵定义……………………typedefstructArcCell{intadj;char*info;}ArcCell,AdjMatrix[20][20];typedefstruct{charvexs[20];AdjMatrixarcs;intvexnum,arcnum;}MGraph_L;//^^^^^^^^^^^^^^^^^^