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

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