以互联网+思维改进地图导航寻路系统探讨

沈煜航 李家胤 李甜

摘要：地图导航系统是为解决寻路问题而构建于寻路算法之上的寻路系统。随着物联网技术的兴起，寻路问题与各类用户数据相关联，衍生出具有物联网时代意义的互联网+寻路模型和寻路系统。该文分析了构建于互联网+寻路模型下的寻路系统在地图导航科技方面的应用，重点探讨了寻路模型构建、导航系统寻路算法优化和拓展相关的关键技术，还讨论了人工智能在地图导航寻路算法中的应用。全文以相关产业技术升级为目标，探索了物联网时代地图导航寻路系统的发展思路。

关键词：互联网+；地图导航；寻路模型；物联网； 贪心算法

中图分类号：TP393.4， TP319 文献标识码：A

文章编号：1009-3044（2019）12-0195-03

The Modification of the Map Navigation Path Finding System by Employing Internet+ thinking

SHEN Yu-hang，LI Jia-yin， LI Tian

（School of Information and Communication， University of Electronic Science and Technology， Chengdu 611731， China）

Abstract： The internet+ path finding system is based on internet of things （IoT） technology， and realizes the optimization and outward development of standard path finding algorithms by Big Data Analysis. It is studied that the application of the internet+ path finding system in map navigation field. We focused on how to build the internet+ model and investigating the key technologies of the modification of the path finding algorithms. The results can be contributed to expand the research idea of new generation of map navigation system.

Key words： internet+； map navigation； path finding model； internet of things； greedy algorithm

网约车作为近年来的一个新兴产业已经在全国得到推广，从都市到乡县，随处都能使用这种网约租车业务。为网约车的精确定位、安排路线的GPS卫星导航，需要与地图导航系统打交道。地图导航系统是为解决寻路问题而构建于寻路算法之上的寻路系统[1-2]。随着物联网技术[3-5]的兴起，寻路问题与各类用户数据相关联，衍生出具有物联网时代意义的互联网+寻路模型，其中就包括以互联网+思维将地图导航、出租的士等行业相结合的地图导航应用模型。本文探索讨论了构建于互联网+寻路模型下的寻路系统在地图导航科技方面的应用，重点分析模型构建、寻路算法关键技术，目的是为相关产业技术升级提供参考思路。

1 基于互联网+的地图导航寻路模型

基于互联网+的地图导航寻路模型是一类基于特殊限制条件的复杂模型。这些条件，来源于各类反馈信息，包括来自地图导航软件本身用户的反馈数据，也可以是通过物联网技术得到的交通行业数据，等等。构建寻路模型，首先需要搭建模型基本框架，然后对收集的反馈信息进行大数据处理，再将处理后的数据加入模型框架的各个步骤中并对一部分框架进行拓深、变形，将整个模型进行整理、修饰，从而形成互联网+地图导航寻路模型。

地图导航的寻路问题衍生出多个子问题，包括多约束条件下的司机匹配问题、基于交通流量的最优路径问题、拼车路径问题[6，7]等。其中，对于司机匹配问题而言，寻路软件需要解决的不只是传统的图匹配问题，还需要解决在同一打车地点的多个用户需要包车、拼车、顺风车、预约车等不同打车需求的司机匹配问题，这就需要利用打车软件中统合的用户与司机信息的大数据，进行司机偏好分类以及用户等待时间容耐分类处理，为就近的司机按照他们的历史偏好分派接单类型，为历史时间容耐性低的用户优先匹配。

当然，随着互联网+思维的引入，地图导航模型的功能以及实际问题上的应用并不会发生太大的改变，但其解决问题的方法会因互联网+思维的优化而革新。对于地图导航模型而言，互联网+思维带来的优化主要来源于两个方面——基于智慧物联大数据的优化与基于人工智能数字模拟的优化。利用物联网技术的特性，一方面，导航软件可以将地图导航与各类相关APP关联起来，通过数据共享与大数据分析，优化地图导航的算法实现。例如，我们可以将IOS的“健康”与“地图”这两个APP关联起来，用户在“健康”里统计步数与步行时间的同时，“地图”中会统计用户的行径路线，并记录下从出发地点到每个经过地点的步数与时间，将之上传至服务器，服务器再对所有用户的数据进行汇总与处理，得出某两个地点间当前时刻的最优路径，甚至可以根据这些数据安排出一条最适合健身或散步的路径。另一方面，导航软件可以利用用户的路径选择偏好以及反馈信息等数据，对导航算法进行优化，或者对导航路线进行修正。

2 基于互联网+的地图导航寻路算法改进

互联网+思维对优化寻路算法有著重要作用。在物联网技术的支持下，各种各样的大数据分析为贪心算法的优化提供了助力。有了历史搜索大数据的帮助，“打表”预处理和实时寻路等过程中算法的时间复杂度呈指数级地降低。还有，随着深度学习技术的提升，人工智能通过对各种路况的学习、理解也为建立一套经验性的寻路算法提供了条件。

2.1 传统寻路算法[8-11]讨论

2.1.1 A*与Dijkstra算法及其优化问题

主流的寻路算法，首推A*算法[8-9]。A*算法的优点是简单、高效而又易于编辑。A*和另一种常用算法即Dijkstra算法[10]都是构建在贪心算法基础上的寻路算法。从大体上看，A*算法与Dijkstra算法极为相似，它们最大的区别在于贪心算法的启发式函数不同。不过，在现实中，市区交通网络的地图庞大、路径庞多，需要进行实时路径搜索的A*算法面临着时间复杂度上的挑战，程序员们需要使用更加“贪心”的算法去优化A*。在代码方面，A*算法有严格的模块化划分，在修改地图时，程序员只需在特定的模块中增减禁行区与通路属性即可，大大减少了地图编辑者们的工作量，这也是A*算法受程序设计者的青睐的原因之一。

A*算法在搜索最短路径时允许有容许误差。相比而言，Dijkstra算法在搜索最短路径方面更加高效，同时有更高的准确性。为保持这一优点，Dijkstra算法优化就显得更困难一些。在处理Dijkstra的优化问题上，国内诞生了一套备受程序开发者青睐的子算法——SPFA。作为Dijkstra的子算法，SPFA继承了Dijkstra的贪心思想，并保持了Dijkstra的准确性，却将其期望复杂度缩减至O（k*E），其中E是边数，k是每个节点进入队列的次数一般不高于2次。这种级别的优化，几乎将时间复杂度降低了一个次数，然而缺陷却只是会被某种特殊的网络情况卡成O（N2）的时间复杂度，我们只需要对这种情况特殊判断，并通过贪心的启发式算法去规避便可。

2.1.2 Floyd算法与“打表”思想

对于另一种更加简单的寻路算法——Floyd算法[11]，程序设计者们往往因為其过高的时间复杂度而将之摒弃。然而不得不承认，Floyd在精确计算众多节点间最短路径时，仍有其优越性。在考虑实际问题时，一个导航软件在同一区域中短时间内可能会面对的数百万级的客流量，若是其中每个用户各自进行导航当然不成问题，但是他们的时间复杂度叠加在一起便是个大的离谱的数字。针对这种情况，Floyd便发挥作用了。我们不妨在每个用户搜索路径前，先将整张地图进行A*的导航网格化处理，随后用Floyd在分成小块的局部导航网格中运行，因为Floyd的特性，一次运算便能得出所有结点间的最短路径，然后再将这些路径保存起来，当用户搜索到其中的路径时直接提供给用户即可。这类方法也被称为“打表”。“打表”思想的应用相当广泛，譬如各类下载软件会将用户最常下载的一些磁力链接提前在服务器中预处理，以便用户需要下载时能够以最快的下载速度从服务器中直接下载，并能节省下载软件从磁力链接地址抽调资源的流量。上述四种算法时间复杂度、应用模型和优化方法比较，如表1所示。

2.2 贪心算法[12]的改进

互联网+思维对贪心算法的优化主要体现在两个方面：一是通过用户历史路径选择偏好来编写启发式函数；二是通过对相关产业收集到的各类数据进行大数据分析，拓展贪心算法的启发式函数。我们来探讨在地图导航系统中如何优化贪心算法。

地图导航软件有两种途径去收集用户的路径偏好数据。首先，导航软件可以在征得用户同意的情况下常驻后台，利用卫星定位监控用户在某种路况下对路径的选择，并将之上传、汇总，利用大数据技术分析后在启发式函数中加入这些经验性的路径取舍抉择并赋予其高优先度。其次，在导航软件已有的启发式函数的基础上，当用户使用地图导航时，若在某些路段偏离导航选择了另一路线，并且这些路段的通行时间比软件预期的更短，那么导航软件会将这些更改后的路径抉择上传、汇总，在大数据分析后对原有的启发式函数进行更新。这些基于用户偏好的启发式函数在使用时往往也具有一种较为人性化的选择，不同于普通优化的A*算法。

与地图导航相关的数据涵盖了许多方面，如一个地段的天气情况、某个地区的微信收发总数、某条道路的车载广播接收情况、某一路段测速仪的平均测量数值、甚至是某一区域4G基站的负荷程度。其中大部分数据反映的是一个区域的人流量以及交通流量，还有的数据反映一个路段的通行是否方便、快捷。启发式函数中引入相关行业数据的优化后，贪心算法会首先规避掉4G基站负荷大、车载广播接收多的路段，因为这些路段的人流量与车流量必定很大，而优先选择平均测速高、天气情况较好的路段。这种启发式函数与用户偏好优化下的启发式函数产生了两种不同的优先级别，合理选用这两种优先取舍的标准对优化互联网+寻路系统十分重要。

启发式函数是贪心算法的核心，其应用如图1所示。利用互联网+思维优化启发式函数比程序设计者们拼尽脑汁想出的优化方案简单很多，而其时间复杂度与精准程度也更加优越。引入互联网+思维对构建与优化互联网+寻路系统至关重要。

2.3 预处理算法的改进

我们在讨论Floyd算法的时候提到了它在寻路系统中可用于预处理一些常用的路径，应该怎么利用互联网+思维来优化预处理算法[11]呢？有两种思路：一是将时间复杂度分散，利用区块链的思想将数据计算、处理、储存分担到各个用户终端上；二是摒弃Floyd算法，而利用大数据的思想，将用户的搜索记录与结果等数据上传、汇总，进行大数据处理后得出搜索度较高的一些地点与路径，并储存到服务器上。值得注意的是，为了节约空间复杂度，对于搜索度没有高到一定程度的结点，其储存的路径应当是互不包含的。比如，如图2所示，A-B-C-D-E这条线路中，若A、C、E是搜索度较高的三个结点，A-B-C、C-D-E、A-B-C-D-E是这三个地点间所对应的最优路径，那么只需要保存A、C、E三个结点以及A-B-C、C-D-E两条路径即可。而A、E两点间的最短路径用户在搜索时会首先检测到A、E两结点在服务器中保存的结点之中，随后通过在这些结点间的路径搜索得出A、E间的最短路径。

2.4 基于深度学习的经验性寻路算法的应用

人工智能已经应用在了各种产业中，其在寻路系统中的应用也早已有人涉足。特斯拉（Tesla）作为无人驾驶汽车的研发大厂，一直致力于深度学习与人工智能的开发，其中利用人工智能来驾驶汽车更是其重点研究对象。近年来，特斯拉在无人驾驶技术上取得了不少成果，已经发展出了一套完善的自动驾驶系统。特斯拉利用Lindar、摄像头和雷达实时监控周遭信息，使用免费的无线3G/4G LTE网络进行实时定位与路况数据交换，通过OTA来获取最新的软件和功能进一步扩展辅助驾驶的潜力，而其自动辅助驾驶硬件会在行驶过程中搜集数据进行分析与学习。在自动辅助驾驶系统方面，特斯拉编写了一个效率极高的深度学习算法为辅助驾驶的人工智能程序积累经验，它让人工智能程序在各种模拟环境下运行以学习详尽的应对方法，最后将积累了充分经验的自动辅助驾驶系统放入现实中测试，在保证安全性的前提下投入市场供消费者使用。

类似特斯拉的做法，我们可以将人工智能应用于互联网+寻路系统中，利用深度学习算法开发出一套经验性的寻路算法。首先需要将多张道路交通地图数字化拼接出一张涵盖了尽可能多种道路情况的数字地图，并在这张数字地图上模拟出各种可能遇见的交通情况；其次程序设计者们需要开发出一个能够用于路径搜索的深度学习算法，赋予人工智能最基础的学习、进化能力；之后再将人工智能程序置于数字地图中进行最短路径搜索模拟，在模拟中积累搜索經验，使其具有应对多数道路交通情况组合的能力，获得一套完善的经验性搜索方法。这套经验性方法可用于优化互联网+寻路系统中A Star算法的启发式函数，也可直接将积累了足够经验的人工智能程序作为核心应用于互联网+寻路系统中，使之利用模拟中得到的经验处理实际问题。不过考虑到人工智能的完善相当困难、在实际问题中可能出现各种bug，不推荐在系统中直接使用人工智能。

3 结语

从游戏到地图导航，寻路系统覆盖了我们生活的方方面面，寻路问题，已然上升到一个新的高度，它可以是利用图论思想求解金融模型、可以是计算错综复杂的航线网络甚至可以是统筹整个城市的交通系统。物联网技术拓宽了地图导航寻路模型的广度、发展出新的寻路问题，大数据技术为寻路系统提供了系统性的优化、赋予其对寻路问题全新的处理方式。本文研究了以互联网+思维改进地图导航系统的关键技术，为大数据新时代导航系统升级提供理论参考。相信在不久的将来，随着物联网技术的普及，地图导航系统将更加先进、实用，随之而来的智能交通系统升级以及游戏开发等领域将拥有更加广阔的前景。

参考文献：

[1] 陈怀民，方泰淙，段晓军.基于骨架提取的飞行器航迹实时重规划法[J].现代电子技术，2018，41（16）：127-131.

[2] 李晓帆，许畅.小车远程控制及自主寻路系统的设计与实现[J]，计算机科学， 2015，42（12）：98-101.

[3] 黄梅.物联网的结构特征研究及系统管理方法[J].信息技术，2018，（11）：168-172.

[4] 陈可睿.物联网的关键技术研究及其应用[J].电子世界，2018（16）：16-18.

[5] 何文乐.融合物联网智慧校园安防系统优化设计[J]，信息技术，2018，（11）：139-142+147.

[6] 黄美灵，陆百川.考虑交叉口延误的城市道路最短路径[J]，重庆交通大学学报（自然科学版）， 2009，28（6）：1060-1063.

[7] 曾庆福，王孟平.基于MATLAB编程Dijkstra算法的消防救援最佳路线研究[J].武警学院学报，2018，33（6）：9-13.

[8] 陈昊，宁红云.基于集合运算的最短路径搜索算法[J].计算机工程，2007（20）：199-200+203.

[9] 王维，裴东，冯璋.改进A*算法的移动机器人最短路径规划[J]，计算机应用， 2018，38（5）：1523-1526.

[10] 李泽文，唐平，曾祥君，等.基于Dijkstra算法的电网故障行波定位方法[J].电力系统自动化，2018（18）：162-168.

[11] 邹桂芳，张培爱.网络优化中最短路问题的改进FLOYD算法[J].科学技术与工程，2011（28）：6875-6878，6892.

[12] 来学.两种不同贪心算法在求解TSP问题中的应用和比较[J].河北北方学院学报（自然科学版）， 2018，34（7）：34-37.

【通联编辑：代影】