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

1、深入Java编程,专业教程,理论讲解部分,Ver3.1,第029课 算法及数据结构,概述：,A*算法介绍,重点：,难点：,A*算法,A*算法,8 A*算法,第029课 算法及数据结构,A*算法是当今比较流行的一种寻路算法.它是解决在一个比较复杂的地图中寻找出最短路径的问题.,例如在这样一副地图中,从绿色的方块移动 到红色方块的最短路径如何求得.其中蓝色为不可通行区域.,第029课 算法及数据结构,节点:这是一副简化了的地图,已经被划分为一个一个的方格.这里我们把这些方格称之为节点.,8.1 基本概念,开启列表:开启列表中保存所有可能经过的节点信息,并且这里的节点需要保存其父节点.,父节点:表示

2、当前节点的前继节点.,8 A*算法,第029课 算法及数据结构,关闭列表:关闭列表中保存不可以到达的节点.,路径评分F:,F = G + H,H = 从网格上那个方格移动到终点B的预估移动耗费。,G = 从起点A，沿着产生的路径，移动到网格上指定方格的移动耗费。,8.1 基本概念,8 A*算法,第029课 算法及数据结构,移动耗费G:,我们令水平或者垂直移动的耗费为10，对角线方向耗费为14。,估算H:,H值可以用不同的方法估算。我们这里使用的方法被称为曼哈顿方法，它计算从当前格到目的格之间水平和垂直的方格的数量总和，忽略对角线方向。然后把结果乘以10。,8.1 基本概念,8 A*算法,第02

3、9课 算法及数据结构,8.2 搜索过程,首先将起始节点加入开启列表.,然后,将这个节点周围的节点都加入开启列表,除关闭列表中节点.并且将其父节点置为起始点.,这是将起始点从开启列表中删除,并加入关闭列表.,8 A*算法,第029课 算法及数据结构,计算开启列表中的所有节点的路径评分.,74,60,74,60,54,60,54,选取评分最低的节点,从开启列表中删除,加入关闭列表.我们命名它为当前点.,40,8.2 搜索过程,8 A*算法,第029课 算法及数据结构,将当前点周围的可行节点加入开启列表中.,74,60,74,60,54,60,54,40,这里分为两种情况,要加入节点没有在开启列表中

4、或者已经在开启列表中.,若不再开启列表中则将当前点作为其父结点并计算G值.,若已在开启列表中则比较以当前点作为父节点的G值与原G值,若当前G值小则改变其父结点为当前点并修改G值,否则什么也不作.,8.2 搜索过程,8 A*算法,第029课 算法及数据结构,此处在40点下方的点,原F值为54.以当前点为父节点计算F = 20+40 = 60.所以什么也不作.其它节点类似.,74,60,74,60,54,60,54,40,这时我们重新搜索开启列表,寻找F值最小的节点.这里有2个54的节点.我们选择左下放的继续.此时,该节点作为当前点.,8.2 搜索过程,8 A*算法,第029课 算法及数据结构,8

5、8,74,将当前节点相邻的可行节点加入开启列表.并将其父节点设置为当前点计算F值,74,60,74,60,54,60,54,40,再次搜索开启列表寻找F值最低节点,然后重复上述步骤.,8.2 搜索过程,8 A*算法,74,88,74,第029课 算法及数据结构,94,68,68,88,74,102,直到将寻找到目标节点.,74,60,74,60,54,60,54,40,74,94,80,74,82,82,74,8.2 搜索过程,8 A*算法,第029课 算法及数据结构,其最终路径按照目标点的父结点以次寻找其后节点的父节点直到起始点.,74,88,74,94,68,68,88,74,102,74

6、,60,74,60,54,60,54,40,74,94,80,74,82,82,74,8.2 搜索过程,8 A*算法,第029课 算法及数据结构,8.3 算法描述,1.将起始节点添加到开启列表.,2.重复如下内容:,a.寻找开启列表中F值最低的节点.称其当前节点.,b.把当前节点从开启列表中删除并加入关闭列表.,c.对相邻可行的节点若不在开启列表中,则设置当前点为父结点并计算其F值加入开启列表;若在开启列表中则比较若当前F值小则改变其父节点并更新F值,否则不作任何事.,d.终止.找到目标或者开启列表已经为空仍旧没有找到列表.前者查找成功,后者说明路径并不存在.,8 A*算法,第029课 算法及数据结构,3.保存路径.从目标格开始，沿着每一格的父节点移动直到回到起始格。,8.3 算法描述,8 A*算法,小结：,A*算法介绍,第029课 算法及数据结构,1