结合统一搜索和贪婪搜索
统一:把路径成本排序, 即来程的成本 g(n)
贪婪:排序按照与目标的临近性, 即前程成本 h(n)
A* 搜索 : f(n) = g(n) + h(n)
S a d
b
G
h=5
h=6
h=
2
1
8
1
1
2
h=6
h=0
c
h=7
3
e
h=1
1
Example: Teg Grenager
S
a
b
c
ed
dG
G
g = 0
h=6
g = 1
h=5
g = 2
h=6
g = 3
h=7
g = 4
h=2
g = 6
h=0
g = 9
h=1
g = 10
h=2
g = 12
h=0