5a星算法法?

来源：蜘蛛抓取(WebSpider) 时间：2019-04-04 23:28 标签： a星算法

如图中亮绿色点为起点蓝点为終点，白色为墙体不可行走黄色点区域为被试探到的位置，绿色的路径为最后的最短路径其中这里移动规则是只能上下左右移动。

关於Aa星算法法大家可以去google。这里展一下本项目Aa星算法法的部分（思路）：

+ 把起点加入close集合并把它设为Current节点 + 查找Current节点的相邻节点（上下左祐） + 如果节点不是墙也不在close集合并且也不在open集合的，计算G值H值设置Parent为Current节点，然后加入到open集合 + 如果已经加入了open集合那么查找一下是不是從Current节点到这个节点G值更小，如果是那么改变这个节点的G值为更小值Parent指针指向Current节点 + 如果节点是终点，那么跳出循环 + 遍历open集合查找F值最小嘚节点（F=G+H） + 如果找到了，把这个节点移到close集合 + 如果没有找到并且open表又为空了，那么表示找不到路径了跳出循环 + 循环后如果没找不到路徑，那么结束 + 如果找到路径那么从终点开始，在close表中通过parent指针来寻找路径直到起点

大家可以通过来参考具体代码。

工程实现了编辑地圖保存地图（为下次打开使用）功能。工程使用cocos2d-x3.x引擎

1.启发式搜索：启发式搜索就是在狀态中的搜索对每一个搜索的位置进行评估得到最好的位置，再从这个位置进行搜索直到目标这样可以省略大量无谓的搜索路径，提高了效率在启发式搜索中，对位置的估价是十分重要的采用了不同的估价可以有不同的效果。

　　启发算法有： 、等。

2.估价算法：從当前节点移动到目标节点的预估损耗

　　预估算法有：曼哈顿（manhattan）等。

3.算法特点：理论上时间是最优的但空间增长是指数型的。

4.java实現：上下左右移动

我要回帖

更多关于 a星算法 的文章

 

随机推荐