代价树的广度优先搜索

背景：如图是5城市之间交通路线图，A城市是出发地，E城市是目的地，两城市间的交通费用(代价)如图中数字所示，求从A到E的最小费用路线。

解法：采用 代价树的广度优先搜索
理论：

1. 首先根据交通图，画出代价图

代价图 如图2：



2. 开始搜索

oepn表存放刚刚生成的节点。
closed表存放将要扩展的节点或已经扩展过的节点。

open表结构：
[代价]|[节点]|[父节点]

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



1) 把A放入 open表

open表：
0| A | 0      
Closed表： 空

2) 把A从open表放入closed表

open表： 空            
closed表：
1 | A | 0

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

Open表：
3 | C1 | A 
4 | B1 | A
closed表：
1 | A | 0


4) 把C1从open表放到closed表

Open表：
4 | B1 | A 
closed表：
1 | A | 0
2 | C1 | A

C1不是目标节点，于是继续扩展

5) 把C1扩展得到 D1，放入open表
D1的代价：3+2=5
B1的代价：4

open表：
4 | B1 | A
5 | D1 | C1
closed表：
1 | A  | 0
2 | C1 | A

6) 把B1从open放入closed表

open表：
5 | D1 | C1  
closed表：
1 | A  | 0
2 | C1 | A
3 | B1 | A
B1不是目标节点，于是继续扩展

7) 扩展B1得D2，E1，放入Open表
D2的代价：4+4=8
E1的代价：4+5=9

open表：
5 | D1 | C1 
8 | D2 | B1            
9 | E1 | B1            
closed表：
1 | A | 0
2 | C1 | A
3 | B1 | A


8) 把D1从open表放入closed表

open表：
8 | D2 | B1 
9 | E1 | B1            
closed表：
1 | A | 0
2 | C1 | A
3 | B1 | A
4 | D1 | C1

D1不是目标节点，于是继续扩展

9) 把D1扩展得到E2，B2，放入open表
E2的代价：3+2+3=8
B2的代价：3+2+4=9
D2的代价：8
E1的代价：9

open表：
8 | E2 | D1 
8 | D2 | B1            
9 | B2 | D1            
9 | E1 | B1             
closed表：
1 | A | 0
2 | C1 | A
3 | B1 | A
4 | D1 | C1

10) 把E2从open表放入closed表

                             
open表：
8 | D2 | B1           
9 | B2 | D1            
9 | E1 | B1            
closed表：
1 | A | 0
2 | C1 | A
3 | B1 | A
4 | D1 | C1
5 | E2 | D1                           
E2 是目标节点，搜索结束。

则搜索路径 A - C1 - D1 -E2
即：A - C - D - E