菜单 学习猿地 - LMONKEY

VIP

开通学习猿地VIP

尊享10项VIP特权 持续新增

知识通关挑战

打卡带练!告别无效练习

接私单赚外块

VIP优先接,累计金额超百万

学习猿地私房课免费学

大厂实战课仅对VIP开放

你的一对一导师

每月可免费咨询大牛30次

领取更多软件工程师实用特权

入驻
99
0

A*

原创
05/13 14:22
阅读数 32046

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)的限制,不能保证路径最短,但可以提高搜索速度

 

 

发表评论

0/200
99 点赞
0 评论
收藏
为你推荐 换一批