# A*算法

# 1. 原理

A* 算法总是优先考虑f=g+h最小的路径，其中

1. g(path)=path cost
2. h(path)=h(s) = 到终点的估计距离

# 2. 算法过程

# 1. 首先确定每个状态到终点的距离 h

# 2. 起点为：arad

arad---- zerind (75+374=449) 
arad---- sibiu  (140+253=393) 
arad---- timisoara (118+329=447) 

选择 f 最小的路径进行扩展

# 3. 移动到 sibiu

arad---- zerind (75+374=449) 
arad---- sibiu  (140+253=393) 
arad---- timisoara (118+329=447) 
arad---- sibiu---oradea(291+380=671)
arad---- sibiu---fagaras(239+176=415)
arad---- sibiu---rimnicu_vilcea(220+193=413)  

选择 f 最小的路径进行扩展

# 4. 移动到rimnicu vilcea

arad---- zerind (75+374=449) 
arad---- sibiu  (140+253=393) 
arad---- timisoara (118+329=447) 
arad---- sibiu---oradea(291+380=671)
arad---- sibiu---fagaras(239+176=415)
arad---- sibiu---rimnicu_vilcea(220+193=413)  
arad---- sibiu---rimnicu_vilcea---pitesti(417)  
arad---- sibiu---rimnicu_vilcea---craiova(526)  

选择 f 最小的路径进行扩展

# 5. 移动到fagaras

arad---- zerind (75+374=449) 
arad---- sibiu  (140+253=393) (checked)
arad---- timisoara (118+329=447) 
arad---- sibiu---oradea(291+380=671)
arad---- sibiu---fagaras(239+176=415)(checked) 
arad---- sibiu---rimnicu_vilcea(220+193=413)(checked)  
arad---- sibiu---rimnicu_vilcea---pitesti(417)  
arad---- sibiu---rimnicu_vilcea---craiova(526)  
arad---- sibiu---fagaras--bucharest(450+0=450)

选择 f 最小的路径进行扩展

###6. 移动到pitesti

arad---- zerind (75+374=449) 
arad---- sibiu  (140+253=393) (checked)
arad---- timisoara (118+329=447) 
arad---- sibiu---oradea(291+380=671)
arad---- sibiu---fagaras(239+176=415)(checked) 
arad---- sibiu---rimnicu_vilcea(220+193=413)(checked)  
arad---- sibiu---rimnicu_vilcea---pitesti(417)(checked)  
arad---- sibiu---rimnicu_vilcea---craiova(526)  
arad---- sibiu---fagaras--bucharest(450+0=450)
arad---- sibiu---rimnicu_vilcea---pitesti---bucharest(418)
arad---- sibiu---rimnicu_vilcea---pitesti---craiova(526)

# 7. 移动到终点buchares

到达终点

# 3. 一致性与可纳性

那么是否能够保证，A*算法一定能找到这样的路径呢？ 答案是否定的，是否能找到取决于启发函数 h

符合条件的函数 h应该是，小于通过该状态且通往目标的路径的真是耗散，即： h(s)<true cost

A*算法能够找到最小路径的条件可以表述为：

1. h 不能高估与目标的距离

2. h 是乐观的

3. h 是可采纳的

4. 为什么乐观启发函数一定能找到最小路径呢

路径 p 一定小于所有边缘上的路径，因为最短优先。此外，超过边缘上的节点，一定大于该路径因为耗散>=0

# 4. 数据结构

# 1. 路径

# 2. 分类集