《常用的数据结构和算法 》.ppt

文档介绍：:A*算法介绍重点:难点:A*算法A*算法8A*算法第029课算法及数据结构A*,:这是一副简化了的地图,:开启列表中保存所有可能经过的节点信息,:*算法第029课算法及数据结构关闭列表::F=G+HH=从网格上那个方格移动到终点B的预估移动耗费。G=从起点A,沿着产生的路径,移动到网格上指定方格的移动耗费。*算法第029课算法及数据结构移动耗费G:我们令水平或者垂直移动的耗费为10,对角线方向耗费为14。估算H:H值可以用不同的方法估算。我们这里使用的方法被称为曼哈顿方法,它计算从当前格到目的格之间水平和垂直的方格的数量总和,忽略对角线方向。然后把结果乘以10。*,将这个节点周围的节点都加入开启列表,,*,从开启列表中删除,*,,若当前G值小则改变其父结点为当前点并修改G值,*算法第029课算法及数据结构此处在40点下方的点,=20+40=,,*算法