基于A*算法的最短路径搜索的优化与研究

余博文 华北电力大学

1 引言

目前，有很多搜索图的最短路径，包括：迪克斯特拉算法、广度优先搜索、深度优先搜索、回溯法等方法。在这些算法中，迪克斯特拉算法可以找到最短的路径，但其搜索单源最短路径的效率为O（n2）；广度优先搜索可以找到到达终点的最短步数，不一定为最短的路径；深度优先搜索为递归求解算法的非递归改进；而回溯法方法和深度优先搜索在短时间之内是无法实现的。

上述算法可归为盲目搜索和启发式搜索。启发式搜索一般要优于盲目搜索，但不可过于追求更多的甚至完整的启发信息。此次设计所采用的启发式搜索，其启发信息基于广度优先搜索，恰到好处，搜索在迪克斯特拉算法的基础上进行剪枝。

本文的意义在于完善一些关于基于矩阵（二维数组）存储的图类型的数据结构，进行最短路径的搜索，使得针对于该图类型数据结构的算法在构造、遍历、修改等方面的操作实现达到了高时间效率和高空间效率，这是跟传统图类型数据结构相比较而言最大的区别。针对于无向图最短路径的搜索，突破了“在递归搜索、深度优先搜索、广度优先搜索时对整个图各个结点之间的边要保持长度相同”的限制，比起在传统的迪克斯特拉算法上，运用A*算法搜索图的最短路径，找到了最佳的启发函数，进而找到了最佳的评估函数，并结合迪克斯特拉算法，实现了对迪克斯特拉算法时间效率上的优化。

例如，在电脑鼠迷宫搜索的位置过程中，最好的方法就是要用A*算法去搜索图的最短路径。因此，又快又能正确的找到最短路径则是本次设计的关键。

通过本文所提供的启发函数，展示最短路径的准确搜索，即利用A*算法探究最短路径过程的一个生动实例。本文与其他版本的最主要的区别，就是在电脑鼠移动到期望的位置之时，所走的路径不是其他版本的只有向上移（↑）、向下移（↓）、向左移（←）、向右移（→）四个方向的走法，而且还包括了向左上移）、向右上移）、向左下移）和向右下移（）四个方向。

但是，在进行迷宫搜索的过程中，还需考虑以下情况。

(1)当上（↑）、下（↓）、左（←）、右（→）四个相邻的格子位置可以到达时，电脑鼠可直接移动到此时的目标位置，否则电脑鼠不可到达相应的目标位置。）、向左下移和向右下移）四个方向〕时，如果斜方向的左右

图1 .1 相邻四格子可达

图1 .2 目标位置不可达

图1 .3 斜方向可达，左右方向均可达

图1 .4 斜方向可达，左右有一方不可达

(3)左右均不可达，则电脑鼠需绕道移动，不可穿过两个不可达位置而移动。

图1 .5 斜方向可达，左右方向均不可达，需绕道移动

2 A*算法与启发式的设计

2.1 启发式搜索

在搜索最短路径时，如果把当前地图的每一个格子及起点和终点都作为一个结点，把通道作为边，则该地图可以由一个有向图来表示。那么，搜索最短路径其实就是从该有向图的初始结点（起点）出发，寻找目标结点（终点）的问题。抽象地来看，上述问题都是在某个有向图中寻找目标或路径的问题。通常，把这种描述问题的有向图称为状态空间图（简称状态图），用图的概念来描述状态空间。

状态图中的结点代表问题中的一种格局，称问题中的一个状态。边表示结点之间的某种联系。在状态图中，从初始结点到目标结点的一条路径，或者所找的目标结点，就是相应问题的一个解。根据解题需要，路径解可以表示为边的序列或结点的序列。搜索最短路径的解就是结点序列。

状态空间可用有向图来描述，图的结点表示问题的状态，图的弧表示状态之间的关系有向图就是求解问题的步骤。初始状态对应于实际问题的已知信息，是图中的根结点。图还可以定义目标条件，目标可以描述成一种状态。在问题的状态空间描述中，寻找从一种状态转换为另一种状态的某个操作序列就等价于在一个图中寻找某一路径。各种操作的执行费用是不同的。

搜索策略有两种基本方式：盲目搜索和启发式搜索。所谓盲目搜索是指在不具有对特定问题的任何有关信息的条件下，按固定的步骤进行的搜索。所谓启发式搜索则是考虑特定问题领域可应用的知识，动态地确定操作步骤。优秀选取较合适的操作，尽量减少不必要的搜索，以求尽快地到达结束状态，提高搜索效率。在盲目搜索中，由于没有可参考的信息，因此只要能匹配的操作都需运用，这会搜索出更多的状态，生成较大的状态空间显式图；而启发式搜索中，如具有较多甚至完整的启发信息，虽然只需运用少量的操作，只生成较小的状态空间显式图，能将搜索引向一个解答，但是，每使用一个操作便需做更多的计算与判断。

A*启发式搜索法的基本特点是，如何寻找并设计一个与问题有关的g(n)（从初始结点到n 结点的实际代价）、h(n)（从n 结点到目的结点的最佳路径的估计代价）及构造出估价函数f(n)=g(n)＋h(n)，然后以f(n)的大小来排列待扩展状态的次序，每次选择f(n)值最小者进行扩展。算法中有一步是根据某些启发信息来排列open 表，它既不同于宽度优先所使用的“队列”，也不同于深度优先所使用的“堆栈”，而是一个按状态的启发估价函数值的大小排列的一个“表”。进入open 表的状态不是简单地排在队尾（或队首），而是根据其估价的大小插入到表中合适的位置，每次从表中优先取出启发估价函数值最小的状态加以扩展。如果将宽度优先（或深度优先）看作特殊的A*算法，则可视“队列”（或“堆栈”）为特殊的优先队列，其启发信息比较函数返回为固定值（如果队列为false，则栈为true；反之亦然）。由是观之，open 表必须保证在启发信息相同的情况下，保证表内元素的稳定性；启发信息不同，则自小向大排列。例如，根据字符串长度，对数组中的字符串元素进行排序。字符串数组为：['London', 'Berlin', 'Paris', 'Washington', 'Tokyo', 'Peking', 'Detroit', 'Texas', 'Orleans', 'New York']。

关于排序的方法有很多种。但这里提及该例是通过将字符串放入一个优先队列性质的集合中，然后依次取出优先队列中的各元素，直到优先队列为空。显然，排序的关键码是字符串的长度，不同于以往的按字典序列排序。则将该字符串的关键码提取出来，则可以表示为：[6, 6, 5, 10, 5, 6, 7, 5, 6, 8]。通过该例是为了说明上文提到的排序的稳定性。如果根据字符串的长度排序，为了保证稳定性，则该字符串数组排序完的结果只有唯一的一种：Paris、Tokyo、Texas、Lond on、Berlin、Peking、Detroit、Orleans、New York、Washington。提取出其关键码，则为：[5, 5, 5, 6, 6, 6, 7, 7, 8, 10]。同样关键码为5 的“Paris”和“Tokyo”，如果顺序颠倒，结果便成 为：['Tokyo', 'Paris', 'Texas', 'London', ……]，则 所 得 的 排序结果有违排序的稳定性。

这里之所以强调排序的稳定性，是因为如果采用了基于不稳定排序的优先队列进行数据的存储，那么所搜索出来的路径虽然可以保证步数最少，但是所经过的距离却不一定最短，所行走的路径出现了“毛刺”。即在该拐弯的地方却没有拐弯，而在不必拐弯的地方却出现了拐弯。这一现象尤其在只用宽度优先搜索时体现得更加明显。此外，选择不当的启发信息亦会出现“毛刺”。图2.1、2.2 为(1, 0)到(1, 4)的步数演示：

图2.1 正确的最短路径

图2.2 出现“毛刺”的路径

本文实验为了保证优先队列的稳定性，因而采用了可插入元素和仅可以每次取出一个元素，而该元素位于二叉树中序遍历的第一个输出的元素，而所有元素的顺序是已经排好顺序的二叉排序树作为实现A*算法中的open 表。

2.2 启发式信息的设计

常见的获取启发信息的方法有计算“欧几里得”距离、“曼哈顿”距离、“切比雪夫”距离。

“欧几里得”(x1,y1)到(x2,y2)的距离计算公式：√(x1-y1)2＋(x2-y2)2；“曼哈顿”(x1,y1)到(x2,y2)的距离计算公式：|x1-x2|＋|y1-y2|；“切比雪夫”(x1,y1）到(x2,y2)的距离计算公式：max{|x1-x2|,|y1-y2|}；然而，本文使用的启发信息，从(x1,y1)到(x2,y2)的距离 计 算 公 式 为：BFS((x1,y1),(x2,y2))；其 中，BFS((x1,y1),(x2,y2)) 表 示在图中，(x1,y1)通过宽度优先搜索到(x2,y2)所经过的结点的最少个数，即从(x1,y1)到(x2,y2)的最少步数。

证明启发式函数的精准度：以没有任何障碍物的图为例，假设从图中的某一点进行遍历，计算“欧几里得”距离、“曼哈顿”距离、“切比雪夫”距离分别如图2.3、图2.4 和图2.5。为了方便描述，可以将图2.3简记为矩阵M、将图2.4 简记为矩阵C、将图2.5 简记为矩阵E。

图2.3 以“曼哈顿”距离为启发信息（记“М”）

图2.4 以“切比雪夫”距离为启发信息（记“С”）

图2.5 以“欧几里得”距离为启发信息（记“Е”）

比较各种启发信息的准确度是根据以某一点为中心进行宽度优先搜索，各个结点记录距出发点已走的步数。此时，将通过宽度优先遍历所得到的矩阵记为В。所以，在八个方向的走法规则下，可以得到一个启发信息如图2.4 的矩阵С，则В-С=Ф，矩阵(В-Е)较矩阵(В-М)有更多取绝对值的元素接近于0。那么得出结论：精准度(В)≥精准度(С)＞精准度(Е)＞精准度(М)。

同理，如果是四个方向的走法，可以得到一个启发信息如图2.3的矩阵М，

则В-М=Ф。那么矩阵В 与其他矩阵做差，则矩阵(В-Е)较矩阵(В-С)有更多取绝对值的元素接近于0。那么得出结论：精准度(В)≥精准度(М)＞精准度(Е)＞精准度(С)。

不同的距离计算方法，适用于在不同的走法规则。假设只允许有向上移（↑）、向下移（↓）、向左移（←）、向右移（→）四个方向的走法，那么“曼哈顿”距离作为启发信息的精准度将比“切比雪夫”距离和“欧几里得”距离更完美；但如果走法规则如本作一样允许八个方向的移动，那么“切比雪夫”距离作为启发信息的精准度将比“曼哈顿”距离和“欧几里得”距离更完美。

2.3 核心数据结构的设计

2.3.1 邻接表的设计

此次采用的邻接表，并非传统意义上用链表实现，而是仅用一个字节就表示一个结点的邻接结点。

图2.6 比特位表示的邻接表

该邻接表的设计思想，是将每一个结点抽象为表示分支节点前进方向的各位字节。当某个结点的某一边与其他结点连接时，则对应的位为1，否则该边不与其他结点相连，则对应的位为0。这里，首先要定义一个方向列表，分别（例如）此顺序存储方向坐标{向右（0, 1）, 向 右 下（1,1）, 向 下（1,0）, 向 左 下（1,-1）, 向 左（0,-1）, 向 左 上（-1,-1）,向上（-1,0）, 向右上（-1,1）}。于是，字节的某一位（如第0 位）如果为1，则表示该结点右方向有结点；为0 则右方向无邻接结点。如果所有结点均可达，且呈网格状分布，则邻接表（掩码）如下：

图2 .7 特殊的“邻接表”(掩码)

2.3.2 closed 表

这里所谓的closed 表指代关于某一结点在遍历之时是否被访问的标记，相对应于所有的结点，将是否被标记的属性专门提取出来的布尔类型变量所构成的表称为“closed”表。

在本文A*算法路径规划中，对于结点是否被访问，每个结点有专门标记访问情况的变量（属性）。之所以这样做，是因为通过标记结点是否被访问的动作，来观察整张图的遍历状态，通过界面显示结点是否被标记。

和一般得求最短路径方法不同的是，这里的所有结点访问标记先初始化为“true”。然后通过从某一结点开始进行宽度优先搜索，在记录启发信息的同时，也要把已经记录启发信息的结点访问状态改为“false”。宽度优先搜索在遇到目标结点之时则会停止遍历，从而使一些启发信息相同，但真正的最短路径不需要经过的结点排除在外，达到“剪枝”的效果。这样，在进行最短路径搜索的时候，一些没有经过宽度优先遍历的结点便也会标记为“true”，以免不可能出现的状态空间进入优先队列，从而增加了搜索量。

图2.8 从(1, 1)到(1, 2)的closed 表访问情况 图2.9 从(1, 1)到(0, 2)的closed 表访问情况

假设求(1,1)到(1,2)，从右方向开始遍历，则只有一个结点访问，周围七个均未访问，表示只有(1,1)和(1,2)两个结点需要进入优先队列；从(1,1)到(0,2)，同样从右方向开始遍历，则周围的八个结点均被访问，那么，则需要让(1,1)及其周围的八个结点一并进入优先队列。

3 A*搜寻最短路径算法

3.1 A*搜寻算法

A*搜寻最短路径算法流程图如图3.1。

图2.10 A*搜寻最短路径算法流程图

A*搜寻算法的代码如下：

算法1：A*搜寻算法

1.unsigned char search Path(int src X, int srcY, int d st X, int dstY) {

2.int i, curX, curY, surX, surY;

3. float surG;

4.BinarySortTree open; //优先队列（Open 表）

5.Close *p;

6.bst_Initial(&open); //优先队列初始化

7.closeInitial(dst X, dstY, src X, srcY); // 地 图Close 表 初始化配置

8.close[dstX][dstY].visited = 1;

9.bst_Add Item(&open, close, dstX, dstY, 0); // 初 始 节 点入队

10.while (!bst_IsEmpty(&open)) { //优先队列为空？

11.p = bst_GetItem(&open); //取出估价函数最小节点

12.curX = p-＞currentNode-＞X;

13.curY = p-＞currentNode-＞Y;

14.if (p-＞H == 0) { //启发信息为0？

15.bst_Destroy(&open);

16.return 1;

17.}

18.for (i = 0; i ＜ 8; i++) { //遍历邻接节点

19.if (! (p-＞currentNode-＞sur & (1 ＜＜ i))) continue;

20.surX = curX + direction[i].X;

21.surY = curY + direction[i].Y;

22.if (!close[sur X][sur Y].visited && close[surX][sur Y].H == close[curX][curY].H - 1) {

23.close[surX][surY].visited = 1;

24.close[surX][surY].from = p;

25.close[surX][surY].orientation = (i + 4) % 8;

26.sur G = p-＞G + (f loat)(i & 1 ? sqrt(2.0f) ： 1); // 记录代价信息

27.bst_Add Item(&op en, close, surX, sur Y, sur G); // 将启发信息比当前节点小的邻接节点入队

28.} // end if

29.} // end for

30.} // end while

31.bst_Destroy(&open);

32.return 0;33. }

特别的，第22步是根据启发式信息特点，若当前启发信息为n（≥1），则下一步的启发信息必为n-1，这样才做到对传统的迪克斯特拉算法优化。这是与其他启发信息相比，而所具有的不同之处。在找到是否存在最短路径后，可以通过起始结点如链表索引般来搜索出整个路径。

算法2：路径索引

1. int symbolize Map(int src X, int src Y, int dst X, int dstY) {

2.Close *p;

3.int step = 0;

4.p = getPath(src X, srcY, dstX, dstY); // 获取最短路径的终止节点

5.if (p == NULL) return 0;

6.while (p-＞from != NULL) { //转置路径

7.w orld Terrain[p-＞current Nod e-＞X][p-＞current Nod e-＞Y].value =

8.S T E P + 1 + c l o s e[p-＞c u r r e n t N o d e-＞X][p-＞currentNode-＞Y].orientation;

9.p rin t f("（%d，%d） → ", p-＞cu r ren t Nod e-＞X, p-＞currentNode-＞Y);

10.p = p-＞from;

11.step++;

12.}

13.p r i n t f("（%d，%d） ", p-＞c u r r e n t N o d e-＞X, p-＞currentNode-＞Y);

14.world Terrain[srcX][srcY].value = SOURCE;

15. world Terrain[dst X][dstY].value = DESTINATION;

16.return step;17. }

例如，搜索在图上从（0,0）点到（2,2）点上的最短路径。图为（1表示障碍物，0 表示可到达结点）：

图2.11 搜索树所用的地图

图2.12 以当前位置到达目标结点所需步数作为启发信息的状态空间示意图

图2.13 传统的曼哈顿距离作为启发信息的状态空间示意图

3.2 实验比较

为了比较启发信息对最终最短路径搜索结果的影响，这里分别演示了以“曼哈顿”距离作为启发信息，和基于宽度优先确立步数的启发信息进行对比。其中，最短距离是以“迪克斯特拉”算法作为标准的。通过基于各种启发信息搜索出来的路径与迪克斯特拉算法计算出得到的最短距离进行比较，来判别出比较启发信息的精准度（迪克斯特拉算法所得到的代价误差小于10-6）。

例如，求(0,0)到(14,19)的最短路径，如果以“曼哈顿”距离为启发信息，则可以求得。而求从(14,19)到(0,0)的最短路径，“曼哈顿”距离所用的最短步数为22 步。实验结果的详细记录如表3.1。

图3.1 以宽度优先为启发式求出的从（0,0）到（14,19）点最短路径

图3.2 以宽度优先为启发式求出的从（14,19）到（0,0）点最短路径

表3 .1 路径结果比较

由于该图为无向图，所以从起点到终点的最短路径长度与从终点到起点的最短路径长度是相同的。但最短路径可以不同。而实际上，最少步数可以通过宽度优先求得，此时应为21步。最短路径不一定唯一，但最短路径的最少步数和最短路径长度一定是唯一的。如果一条路径的最少步数与正确路径的所用最少步数不同，则该路径所经过的最短路径长度必为错误的。

而使用本文以宽度优先确立步数的启发信息进行最短路径搜索，则不会出现像“曼哈顿”距离那样路径的长度不相同的现象。这是由于：当图的所有边的权重均相同之时，可以利用宽度优先搜索求取两个结点之间的最短路径。这一原理广泛地应用于四方向走法规则的情况，典型的例子就是迷宫求解。如果如本文允许八个方向的走法，向左上移（）、向右上移（）、向左下移和向右下移四个方向与向上移（↑）、向下移（↓）、向左移（←）、向右移（→）四个方向所花费的代价是不同的（前者为√2，后者为1）。

此外，有时候以“曼哈顿”距离为启发信息根本搜索不到最短路径，如表3.1 从(14,0)到(14,19)的结果。

如果想利用两次以“曼哈顿”距离为启发信息的搜索的结果取最小值长度的路径作为最终结果返回，即将其起点与终点颠倒之后再进行搜索，以“曼哈顿”距离为启发信息的搜索依然搜索不到最短路径，如表3.1 从(14,19)到(14,0)的结果。

有时，即使以“曼哈顿”距离为启发信息的路径可以找到最少步数，但也不一定是最短距离，如表3.1 从(0,0)到(12,19)的结果。

4 结论

综上所述，本文介绍的A*算法所求的启发式信息方法其精准度要高于“曼哈顿”距离。但具体要使用哪种启发式信息，还要看具体情况而定。如果图的初始化过程比较简单，则搜索的过程将会耗时较长；而图的初始化过程，例如启发信息的确立做的比较彻底的话，那么在搜索过程中，可以以接近于依次访问最短路径结点的效率搜索出正确结果。