A＊寻路算法的并行化设计及改进

徐唐剑

（江西财经大学软件与物联网工程学院，南昌330013）

0 引言

启发式搜索算法是一种在人工智能等领域中常用的方法。对于人工智能系统来说，问题可能的状态随着搜索的深入呈现指数递增或者阶乘递增，启发式搜索通过模拟人脑的认知模式，对部分可能的状态而不是每个可能的状态进行权衡，找到一个或几个可能性最大的路径排除其他可能性较小或为零的路径，降低算法复杂性。具体的搜索方法就是在搜索过程中不断评估状态空间中的每一个状态，根据其评估值有选择性地得到相对最优的状态，然后以这个状态继续扩展至最终状态。常用的搜索算法包括三种：深度优先搜索（Depth-First Search）、广度优先搜索（Breadth-First Search）、以及最佳优先搜索（Best-First Search）。A*算法是一种基于最佳优先搜索的启发式搜索算法，其应用取得了不错的效果。

算法就是一个定义明确的计算过程，在这个计算过程中取一个值或者值的集合作为程序的输入并产生一个值或者值的集合作为程序的输出。同时为了更好地解决在生活、工作中遇到的某些问题，有些时候需要对所设计的算法做出优化，如时间复杂度、空间复杂度、正确性和健壮性等方面。而为了让计算机每秒执行更多的计算，计算机芯片通常被设计成具有多个处理“核”，可以把这些多核计算机当做工作在某一芯片上的几台计算机，即“并行计算机”。随着多核处理器的普及，为了使多核计算机获得最佳的性能的同时提高程序的运行速度，在设计算法时必须考虑算法的并行性。

1 Dijkstra算法

1.1 算法概述

Dijkstra算法是在1959年的时候由荷兰的科学家Edsger Wybe Dijkstra提出，它能够有效解决单源最短路径问题，该算法要求有向图中边的权重都为非负。算法的主要特点是从起点开始不断向外搜索和扩展，直至达到目标为止，同时在扩展的过程中通过“松弛”操作不断更新shortest值和pred值，最后在结果中可以得到起点到图中其他所有结点的最短路径及其权重和。通过简单的数组实现的Dijkstra算法，那么它的时间复杂度是O（n2）。但采用更优的数据结构实现的话，如使用斐波那契堆实现的Dijkstra算法，它的时间复杂度可以达到O（nlgn+m）。

1.2 算法思想

Dijkstra算法中最关键的部分是维护结点集S。算法不断从结点集Q中选取具有shortest最小的结点u，将结点u加入到结点集S，然后对所有与该结点有关的边进行松弛操作。Dijkstra算法每次都是从结点集Q中选取与结点u“最近”的结点加入到结点集S中，这是一种典型的贪心策略。但不是使用贪心策略一定能够获得最优解，但是可以通过一些定理和推论可以证明Dijkstra算法的解确实是最优解。

（1）松弛操作

首先将从起点到结点u的所花费最短路径的值与边（u,v）的权重之和与起点到当前结点v所花费的最短路径值进行比较。如果加上边（u,v）的权重得到的值更小，那么需要将shortest[v]的值更新为当前shortest[u]+weight（u,v），并且将最短路径上结点v的前驱设置为结点u。

程序RELAX（u,v）

输入：边（u,v）的顶点 u,v

结果：

如果shortest[v]的值减小了，那么令pred[v]取u。

如 果 shortest[u]+weight（u,v）＜shorest[v]，那 么 将shortest[v]赋值为shortest[u]+weight（u,v），同时将pred[v]赋值为u。

（2）算法步骤

Dijkstra算法通过重复对具有最小shortest值的结点相关联的每条边执行松弛操作来工作。首先，需要将有向图中所有结点加入结点集Q，然后还需要唯一确定一个源点s，并将shortest[s]的值初始化为0，对于图中其他所有顶点v的shortest[v]值设为无穷大，对所有结点的pred[v]值将其设为NULL，算法不断从结点集Q中选取具有shortest最小值的结点u，并将该结点从结点集Q中移除，再对所有与结点u相关的边执行松弛操作。

程序DIJKSTRA（G,s）

输入：有向图G、源点s

结果：对于有向图G中的任何一个非源点v，shortest[v]的值指的是从源点s到结点v的最短路径上所有边的权重和。pred[v]表示在最短路径上结点v的父结点。对于源点，将其shortest[s]的值置为0,pred[s]的值置为NULL。规定如果从源点s与结点v不存在路径，那么shortest[v]的值是无穷大，而pred[v]的值是NULL。

①初始化。将除起点s以外的任何结点v的shortest[v]值设为无穷大，其pred[v]的值设为NULL。然后将 shortest[s]的值置为 0，pred[s]置为 NULL。

②将所有的结点加入结点集Q。

③只要结点集Q不为空：

A.在结点集Q中选取一个具有shortest[u]最小值的结点u，然后将这个结点从结点集Q中移除。

B.找出每个与顶点u邻接的结点v：

执行松弛操作，即调用RELAX（u,v）。

图1 Dijkstra算法运行流程图

（3）核心代码

Python是一种面向对象的解释型计算机程序设计语言，于1989年由Guido van Rossum发明。Python具有丰富库而且这些库的功能强大，由于它可以与其他语言很好的合作所以常被称为“胶水语言”。近些年来，尤其是人工智能逐渐成为人们关注的重点，而其首选编程语言就是Python。其次Python在网络爬虫方面的运用也是非常广泛的，加上其“优雅”、“明确”、“简单”的设计特点，Python得到了大多数人的青睐。Python于2017年7月在IEEE发布的编程语言排行版位居首位。为了适应互联网时代发展的要求，本文使用了Python作为算法实现的主要编程语言，以下是Dijkstra算法实现的核心代码：

2 A＊算法

2.1 算法概述

2.2 算法思想

A*算法是建立在经典Best-First Search和Dijkstra算法的基础上的一种启发式搜索算法，算法通过引入评估函数减少搜索范围和降低空间复杂度。通常将评估函数定义为：

g（n）表示从起点到当前点n的实际移动距离，即从起点移动到当前点n所花费的移动代价。h（n）表示从当前点n到终点或目标点的估算距离，即对当前点n移动到终点的估算移动代价。通过比较评估函数f（n），选取具有最优值的结点用作下一次的扩展。

（1）算法特性

①当只计算g（n）时，即只计算和考虑起点到当前点n的实际耗费距离，不考虑当前点n到终点的估算耗费距离。那么算法就会被转换为经典的Dijkstra算法，此时需要考虑所有位置的状态。

②当只计算h（n）时，即只计算和考虑当前点n到终点的估算耗费距离，不考虑起点到当前点n的实际耗费距离。那么算法就会被转化为使用贪心策略的Best-First Search，速度最快，但是可能得不到实际最优的解。

③如果估算距离不高于实际距离，即h（n）不高于g（n），那么算法则一定可以得到最优解。常见的估算方法有：欧几里得距离、曼哈顿距离以及切比雪夫距离。

（2）算法步骤

A*算法一般通过Open和Closed两张表维护在搜索过程中扩展得到的结点。将扩展得到的且有效的结

A*算法是目前来说最有效的一种直接搜索算法，同时也是目前常用的一种启发式搜索算法（Heuristically Search）。该算法由 Peter Hart、Nils Nilsson和 Bert ram Raphael三人于1968年在斯坦福研究院提出。A*算法是对Dijkstra算法的一个扩展，同时也是一种高效的搜索算法。A*算法运用非常广泛，可以在游戏领域看到它的身影，如NPC移动计算。点置入Open表，将已经搜索过的结点置入Closed表。具体算法可描述如下：

步骤1初始化Open表和Closed表；

步骤2将起点A加入到Open表，此时待搜索的结点只有一个，即起点A的估价值肯定为最优值；

步骤3若Open表非空，则取出具有评估最优值的结点，进行下一步操作，否则跳转至步骤8；

步骤4将具有评估最优值的结点n取出，并将这个结点加入到Closed表中，如果结点n就是终点B或者就是最终状态，那么跳转至步骤8，否则进行下一步操作；

步骤5对结点n进行扩展，即取与结点n相邻且满足未在Closed表中、非不可操作等条件的结点N1至Nt；

步骤6对结点N1至Nt进行评估，即计算起点A到当前结点的实际移动距离和当前结点到终点B的估算距离之和；

步骤7将结点n作为N1至Nt的父结点，并将N1至Nt加入到Open表中，跳转至步骤3；

步骤8根据父结点进行回溯生成最短路径，销毁Open表和Closed表，程序结束。

图2 A*算法运行结果图

（3）核心代码

根据实际的需求选择选择下一步可以移动的位置，通常在2D游戏中下一步通常可以有八个可以移动的方向，当然也可以设置只有四个可以移动的方向。同时根据障碍物，可以设置相应的规则，如当前结点的右邻有障碍物时，规定当前结点的右上、右、右下三个方向是不可行的。

3 双向A＊算法

3.1 算法概述

通过对传统A*算法进行实现和分析，发现其实际运行时间性能较差且存在一些缺点，很难满足实际运用的需求。可以通过对其搜索方式进行改进和设计，使其满足实际需求。与传统A*算法不同的是，传统A*算法使用的搜索方式为从起点一直搜索扩展到终点为止，由在此过程中生成一条最短路径。而双向A*算法采取的搜索方式是从两个方向同时进行搜索，即一个从起点向终点扩展，另一个从终点向起点扩展。当两个搜索路线汇合到同一个位置时，就可以得到一条最短路径。

3.2 算法思想

双向A*算法的主要思想是：传统A*算法的搜索结果会在图上呈现为一个扇形展开的树结构。而一个大的搜索树的搜索展开速度远远不如两个较小的搜索树，使用两个较小的搜索树在一定情况下可以加快算法的运行速度。同时对传统A*算法引入并行化设计，满足时代发展要求，即符合如今多核计算机已经非常普及的现状。

在理想情况下，双向A*算法的运行速度相比于传统A*算法的运行速度将会提高一倍，理想运行过程如图3所示：

图3 双向A*算法理想情况下的运行流程图

（1）核心代码

双向A*算法通过开启两个线程执行两个不完全相同的搜索过程，即一个线程处理从起点到终点的搜索过程，另一个线程处理从终点到起点的搜索过程。当两个线程处理到同一个结点时，以此可以判定算法已经找到一条最短路径。

（2）双向A*算法实际运行情况

通过实际运行对比，可以发现双向A*算法的运行速度在复杂路径问题的求解中的运行效率是高于传统A*算法的。另外，传统A*算法在求解复杂路径问题是往往只能得到一个固定的解，而双向A*算法在某些路径问题的求解过程中可以得到实际存在的多个不同最优解。

传统A*算法和双向A*算法在某个特定路径问题中求解情况如下（小括号内为算法运行时间）：

图4

4 其他改进方法

4.1 定向搜索

在传统A*算法的搜索过程，Open列表用于保存可能需要被扩展的结点。定向搜索是在传统A*算法的基础上，通过限制Open列表的大小而得到一种改进方法。这种改进方法的好处是，当Open列表太大时即待搜索的结点太多时，会将可能性最小的即评估值最低的节点排除，从而一定程度上减少了算法的搜索空间。但这种改进方法会带来一定的缺陷，即需要对Open列表进行筛选所以对数据结构的选择增加了限制条件，同时这种改进方法可能会得到不到最优解，即无法找到实际最短路径。

4.2 动态加权

该改进方法假定需要在搜索开始时快速达到某个状态或位置。通过一个权值w（w＞=1）和估算函数相关联。在不断接近终点时，权重w的值也不断减少，通过这种改进方法可以降低在对某个状态评估时估算函数的重要性，提高实际花费代价的重要性。算法的思想为搜索前期以搜索速度为重点，搜索后期重点考虑搜索正确率。

4.3 双向搜索变体

为了继续对双向A*算法的性能等方面进行优化和改进，众多文献讨论了不同的方法。

重定向方法不同于一般双向搜索算法，这种方法放弃了完整的前向搜索或者后向搜索，首先从起点开始进行一次短暂的前向搜索并选取一个最佳的前向候选结点。然后进行后向搜索，不同于完整的后向搜索。此次后向搜索的起始结点为终点，目标点为上一步选择的前向候选结点，这个搜索过程也不是完整的，同样也可以得到一个最佳的后向候选结点。接着从前向候选结点向后向搜索结点继续进行扩展，重复这个过程，直到前向搜索结点与后向搜索结点汇合。

面对面方法通过将前向搜索的结果和后向搜索的结果整合在一起。即评估函数满足以下公式：

5 结语

A*算法是广泛应用在图论、人工智能、智能控制领域的一种启发式搜索算法。但是由于在很多情况下它的搜索状态空间非常庞大从而导致其运行及搜索效率不高，所以传统的A*算法并不能在实际生活和工作中得到有效的应用。通过对A*算法引入并行化技术，可以有效减少其运行时间。目前有很多文献对A*算法的优化提出了解决方案，这些方案也成功运用在各个领域，改进后的A*算法可以更好地解决在工作和生活中遇到的路径问题。