A*

open表
close表 //处理过的节点
f(n) = g(n) + h(n)
f(n) --从起点经由n到达终点的最短路径的估计
g(n) --从起点到n点已找到最短路径代价(代价函数)
h(n) --从n点到终点的最短路径的代价估计(启发式函数)

1.把起点S放入open表
2.从open表找f值最小的节点N,为当前节点,放入close list(如果open表空了则失败)
3.当前N的所有后续节点处理(如果N是目标节点则成功):
//1.如果不在OPEN也不在CLOSE则加入OPEN表,并且之前N
//2.已经在OPEN表,如果新的f值小于老的f值则修改指针指向N
//3.如果在CLOSE且新的f小于老的f,移动到open,指针指向N
4.按照f值排序open表

重复2,3,4

从目的格子回溯到起始格子

如果启发式函数h(n)是可接纳,即h(n)<=h*(n),A*能确保能找到最短路径。
h*(n)--最短路径的实际距离

放宽h(n)的限制,不能保证路径最短,但可以提高搜索速度

原文地址:https://www.cnblogs.com/zzyoucan/p/11788415.html