文档介绍：深入Java编程
专业教程
理论讲解部分

第029课算法及数据结构
概述:
A*算法介绍
重点:
难点:
A*算法
A*算法
8 A*算法
第029课算法及数据结构
A*.
例如在这样一副地图中,.
第029课算法及数据结构
节点:这是一副简化了的地图,.
基本概念
开启列表:开启列表中保存所有可能经过的节点信息,并且这里的节点需要保存其父节点.
父节点:表示当前节点的前继节点.
8 A*算法
第029课算法及数据结构
关闭列表:关闭列表中保存不可以到达的节点.
路径评分F:
F = G + H
H = 从网格上那个方格移动到终点B的预估移动耗费。
G = 从起点A,沿着产生的路径,移动到网格上指定方格的移动耗费。
基本概念
8 A*算法
第029课算法及数据结构
移动耗费G:
我们令水平或者垂直移动的耗费为10,对角线方向耗费为14。
估算H:
H值可以用不同的方法估算。我们这里使用的方法被称为曼哈顿方法,它计算从当前格到目的格之间水平和垂直的方格的数量总和,忽略对角线方向。然后把结果乘以10。
基本概念
8 A*算法
第029课算法及数据结构
搜索过程
首先将起始节点加入开启列表.
然后,将这个节点周围的节点都加入开启列表,.
这是将起始点从开启列表中删除,并加入关闭列表.
8 A*算法
第029课算法及数据结构
计算开启列表中的所有节点的路径评分.
74
60
74
60
54
60
54
选取评分最低的节点,从开启列表中删除,.
40
搜索过程
8 A*算法
第029课算法及数据结构
将当前点周围的可行节点加入开启列表中.
74
60
74
60
54
60
54
40
这里分为两种情况,要加入节点没有在开启列表中或者已经在开启列表中.
若不再开启列表中则将当前点作为其父结点并计算G值.
若已在开启列表中则比较以当前点作为父节点的G值与原G值,若当前G值小则改变其父结点为当前点并修改G值,否则什么也不作.
搜索过程
8 A*算法
第029课算法及数据结构
此处在40点下方的点, = 20+40 = .
74
60
74
60
54
60
54
40
这时我们重新搜索开启列表,,该节点作为当前点.
搜索过程
8 A*算法