0 概述

基于搜索路径规划算法最常用的是Dljkstra(迪杰斯特拉)和A算法，A*算法可认为是迪杰斯特拉算法的扩展。这两种算法流程基本相同，唯一的区别是A*在代价值计算中增加了启发函数

1. 区别

Dijkstra算法的实质是广度优先搜索（队列的先入后出），是一种发散式的搜索。

A*=Dijkstra+贪心算法（启发式函数）

2. A*算法原理

2.1 算法流程

A*算法流程

首先A*算法使用两个集合来表示待遍历的节点，与已经遍历过的节点，这通常称之为open_List和close_List。

然后计算每个节点的优先级，若h(n)=0时，则转化为Dljkstra算法

2.2 启发函数

A*中启发函数的选择直接辉影响算法的速度和准确性，在一些场景下得到的并不是最优的路径针对网格形式的图，有以下这些启发函数可以使用：

  • 图形中只允许朝上下左右四个方向移动，则可以使用曼哈顿距离（Manhattan distance）。
  • 图形中允许朝八个方向移动，则可以使用对角距离。
  • 图形中允许朝任何方向移动，则可以使用欧几里得距离（Euclidean distance）。

红、蓝与黄线分别表示所有曼哈顿距离都拥有一样长度（12），而绿线表示欧几里得距离有6×√2 ≈ 8.48的长度。

曼哈顿距离（Manhattan distance）

其中D是两个相邻节点移动的代价

function H(node) =
    dx = abs(node.x - goal.x)
    dy = abs(node.y - goal.y)
    return D * (dx + dy)

对角距离

这里的D2指的是两个斜着相邻节点之间的移动代价。如果所有节点都正方形，则其值就是 [公式]

function H(node) =
    dx = abs(node.x - goal.x)
    dy = abs(node.y - goal.y)
    return D * (dx + dy) + (D2 - 2 * D) * min(dx, dy)

欧几里得距离（Euclidean distance）

欧几里得距离是指两个节点之间的直线距离，公式为： [公式]

function H(node) =
    dx = abs(node.x - goal.x)
    dy = abs(node.y - goal.y)
    return D * sqrt(dx * dx + dy * dy）

3. 算法优化

在A*算法的每一轮迭代中，根据启发值朝着最佳的方向去拓展路线。然而，在某些情况下我们的寻路效率较低，如下图所示。

由上图我们可以发现搜索的路径是对称的，也是等效的，称为“对称路径”。这种对称路径造成了算法的效率低下，浪费了大量的算力。我们希望尽可能忽略这种对称路径，只找一条路径即可。

由此人们进一步推出JPS（Jump Point Search）算法，优化了 A* 算法寻找后继节点的操作。下一篇将对JPS进行详细的介绍。