基于NoSQL的路网最短路径查询及优化

殷鹏

摘要 最短路径问题一直是计算机学科的研究热点。传统的关系数据库在实现路网的最短路径查询时，大量用到表连接查询，耗费时间。本文提出一种基于Ne04j数据库的路网最短路径查询和优化方法。基于Ne04j数据库的特性以及A+算法的特点，从存储结构、队列优化、搜索算法三方面对A*算法进行优化，提出一种适用于图数据库的双向搜索A*算法。最后对其改进效果进行实验验证，改进算法提高了查询效率。

【关键词】NoSQL A* 算法 最短路径 Ne04j

1 引言

路网的最短路径问题一直是计算机与交通领域的研究热点。在以往的研究中，路网的信息主要在传统的关系数据库中以二维表的形式来存储数据。关系型数据库更关注实体内部的属性，这种存储结构在实现图的最短路径算法时，为了描述实体之间的关系，必须通过外键对多个表进行连接查询，耗费时间。随着图数据库、文档数据库等适合不同数据模型的NoSQL数据库的发展，为路网数据模型提供了新的存储方式。NoSQL全称为Not OnlySQL，意即“不仅仅是SQL”，泛指非关系型的数据库。Ne04j是NoSQL数据库中的一种以图的形式存储数据的图形数据库，具有成熟数据库的所有特性。Ne04j设计的初衷就是为了高效的表示实体间的关系，其存储形式更符合以图为数据模型的路网。在Ne04j中，用一个键值对的双向列表来保存实体和关系的属性。节点的关系直接存储在其定义域中，查找节点关系的时间复杂度为0（1），对于存在大量关系的图形数据的查询速度更快。Ne04j还提供了深度优先搜索、广度优先搜索、最短路径、迪杰斯特拉等多种图的搜索算法，因此Ne04j尤其适用于道路交通网络、地图等方面。本文基于Ne04j数据库对路网最短路径的查询和优化进行研究。针对Ne04j数据库数据的存储特性以及A*算法的特点，提出一种适用于图数据库的A*算法，对其改进效果进行实验验证。

2 基于图数据库的路网最短路径查询

2.1 A*算法

A*算法作为一种最短路径算法，建立在Di kstra算法基础上。为了解决Dij kstra算法盲目搜索的问题，A*算法采用了估价函数作为辅助搜索信息，进行有目的的搜索，减少搜索时节点的数目，缩小搜索规模。

A*算法在初始化时创建Open列表和Close列表，然后执行下列步骤：

（1）把起点加入Open列表中。

（2）遍历Open列表，找到估计值f（n）最小的节点n，如果它不是目的节点，就把它作为当前处理的节点，把该节点从Open列表中删除，加入Close列表中。

（3）对节点n的所有子节点c进行遍历，如果Close列表中有c节点，则忽略它，继续遍历下一个子节点，否则做如下操作：

①如果子节点c不在Open列表中，把它加入，并将n设置为子节点c的父节点，计算f，g，h值。

②如果子节点c已在Open列表中，且原估价值f大于f（c），则修改f=f（c），同时将n设置为c的父节点。

（4）重复（2），（3）步，直到目的节点加入了Open列表中，表示找到路径;或者Open列表为空，表示路径不存在。

（5）最后从目的节点沿着父节点移动回到起始节点，就得到了最短路径。

在A*算法的实现过程中，估价函数的计算公式为f（n）=g（n）+h（n），其中，g（n）代表从起始节点到当前节点n的路径代价，h（n）代表从当前节点n到目的节点的估计路径代价。估价函数对算法的性能有很大的影响，好的估价函数可以减少搜索节点，加快搜索速度。因此，A*算法改进的关键问题就是如何设计估价函数让其接近真实路径长度，通过减少搜索节点的个数来降低资源消耗。h（n）通常用距离长度作为参考值，但仅通过距离选取来优化估价函数仍有很大的局限性，网络特征的结构优化与限制条件都会影响算法的效率。此外，改变搜索策略也可以提高效率。

2.2 基于Ne04j的路网最短路径查询性能分析

将相同的路网数据源分别导入关系型数据库PostgreSQL和图形数据库Ne04j中，随机选取了220对点分别测试A*算法在两种数据库中的查询速度。实验中，通过调节可用内存，改变Ne04j对象缓冲区的配置参数，发现内存的变化与高速缓存的變化对Ne04j的性能影响最大;内存改变对PostgreSQL的影响不明显，不需要通过微调优化性能。实验中，通过使用多线程多次执行查询请求的方式，研究两种数据库在查询时间和内存消耗方面的差异。实验结果显示，在使用更多内存的前提下，Ne04j对路网的最短路径查询计算速度更快。与PostgreSQL不同的是，Ne04j每次查询时可以共享内存中已有的数据，只加载当前请求查询的数据。这样在热启动时可以用较少的时间获得查询结果，查询速率优于PostgreSQL数据库。但如果线程数量增多，多个线程执行不同的查询，Ne04j会消耗更多的内存，计算速度也会下降。因此，Ne04j并不适合对大型运输网络做全图遍历，这样只会加重内存消耗。而在存储数据规模较小的网络时，Ne04j是个很好的选择。在内存可用的情况下，Ne04j这种图形数据库更适合做最短路径查询。

3 基于图数据库的A*算法仃化

Ne04j在遍历路网时拥有较快的速度，但是在路径搜索时会占用更多的内存。因此A*算法优化的主要方面就是如何能缩小搜索范围，减少遍历节点的数量，以降低内存消耗。

3.1 数据存储结构的优化

为了简化操作，便于实现算法，需要为路网选择合适的存储结构。如表1所示，对比了图的四种存储结构。

通过对存储结构的分析，选择邻接表来存储较大规模的路网数据。

3.2 队列排序优化策略

在A*算法中选取最小估价值时，涉及到大量对Open列表和Close列表的操作。在路网中反复遍历含有大量节点的列表会耗费大量时间。如果采用基本的顺序结构存储列表，在做删除操作时要大量移动元素，效率不高。为了便于查找最小估价值节点，可以用小根堆作为Open列表的存储结构，堆顶元素即为最小估价值，查找的时间复杂度为0（1）。删除堆顶元素后，重新调整为小根堆所需要的时间与查找最小估价值的时间相比可以忽略，因此，采用小根堆的存储方式可以大大提高查找效率。

3.3 双向搜索A*算法优化

在Ne04j中，关系可以从两个方向进行遍历，因此本文提出了一种动态双向搜索算法，通过改变搜索方式对A*算法做出优化，以减少内存消耗。双向搜索就是将搜索分为正向搜索和反向搜索，正向搜索时，把反向的当前搜索节点看作临时目的节点，从Open列表中选择估价值最小的点向后搜索到达节点T;切换为反正搜索时，把正向的当前搜索节点T看作临时目的节点，从反向Open列表中选择估价值最小的点向前搜索。正反向搜索反复迭代，直到正向和反向搜索的当前节点为同一节点时结束。

理论上双向搜索是从两个方向均匀同步进行，直到起始节点和目的节点的中心相遇。但在实际路网中节点的分布密度不同，起点和目的节点所在路网的可达程度也不一样。双向搜索相遇的节点不一定在最短路径的几何中心。因此，算法的关键是如何选择切换标准，尽可能让最佳节点在中间相遇。本文提出了使用基于比较双向最佳节点估价值的思想，通过比较正反向Open列表分别相对于起点和目的节点的最小估计值，来决定切换方向。若正向搜索取出Open列表中最佳节点的估计值小于反向搜索最佳节点的估计值，说明正向搜索更接近返回路径的中心位置，则切换到反向进行搜索，让反向搜索逐渐向最佳路径的几何中心靠拢，最终正反向搜索在中间位置相遇。

4 实验验证

本次实验首先选取了十组数据，对A*算法和队列排序优化后的A*算法的查询效率进行测试，结果如图l所示。

通过折线图分析得出，当搜索节点较少时，优化后的算法耗费时间较长。主要原因是小根堆在插入到Open表时需要查找位置，删除堆顶元素后需要堆调整，因此耗费了一些时间。但是随着路径节点数的增多，搜索范围变大，使用小根堆作为排序数据结构的优势慢慢体现了出来。

实验中按照路径距离随机选取了六组数据，对A*算法和优化后的双向搜索A*算法的查询效率和内存消耗进行测试。实验结果显示双向搜索A*算法加载内存少于A*算法，降低了内存消耗。通过图2所示的实验结果得出，优化后的双向搜索A*算法的搜索节点数比A*大大减少。但第三组实验中双向搜索A*算法比原A*算法多了36个搜索节点，这是由两种方法寻路路径不同导致的，其他组实验的最短路径结果与A*算法相同或相近，证明双向搜索A*算法在保证较高精度前提下，提高了查询效率。

5 结语

本文基于NoSQL数据库对路网最短路径查询及优化问题进行了研究。分析了图形数据库Ne04j的特点以及与关系数据库的差异。在两种存储平台下实现路网最短路径查询，从查询效率以及内存消耗等方面进行比较，分析了Ne04j在查询最短路径时的优点与不足。基于Ne04j数据库的特性以及A*算法的特点，对A*算法进行了优化。通过实验验证，改进算法提高了查询效率。

参考文献

[1]李曉华，王士猛，杨晓春，于戈，基于缓存技术的路网最短路径查询[J].东北大学学报（自然科学版），2014，35 （02）：199—203.

[2]廖志芳，陈亮名，彭志文，李严冰，基于节点压缩的寻径优化算法[J].计算机应用与软件，2017，34 （11）：241-246.

[3]宋宝燕，张永普，单晓欢.Spark-GraphX框架下的大规模加权图最短路径查询[J].辽宁大学学报（自然科学版），2017， 44 （04）： 289-29 3+284.

[4]姜代红，戴磊.Dijkstra算法在嵌入式GIS中的改进与研究[J].计算机工程与应用，2011， 47 （31）： 209-211.