知足常乐|A* 路径搜索算法( 二 ) 假设地图中存在起点和终点

重复步骤二到步骤四，直到终止。

下面是 A* 搜索最短路径的示例，每一个节点中左边的数字表示 G(n) 即真实距离，右边的数字表示 H(n) 即启发函数计算的距离。 F 值就是 G(n)+H(n) ，在下面的例子中 H(n) 用曼哈顿距离计算 (在下面的例子中等于没有障碍物时， n 到终点 e 的最短距离) 。

A* 算法的例子
4.A* 启发函数的选择与区别如果不设置启发函数，则 A* 就是 Dijkstra 算法，这时可以找到最短路径。
如果启发函数 H(n) 的值一定小于等于 n 到终点的实际距离，则 A* 可以保证找到最短路径。
如果 H(n) 的值等于 n 到终点的实际距离，则 A* 会直接找到最短路径，而不用扩展搜索额外的节点，此时运行是最快的。
【知足常乐|A* 路径搜索算法】如果 H(n) 的值有可能大于 n 到终点的实际距离，则 A* 算法不一定可以找到最短路径，但是运行速度会比较快。
5.参考文献Amit’s A* Pages 地址： ~amitp/GameProgramming/