基于物联网和大数据分析的互联网+寻路系统研究

沈煜航 李甜 李家胤

摘要

互联网+寻路系统是基于物联网技术、通过大数据分析对标准寻路算法进行优化与拓展，并将之运用于实际生活中、解决现实问题的寻路系统。介绍了互联网+寻路系统的基本概念及其重要应用价值，重点讨论了用互联网+思维优化寻路模型的方法，研究了基于物联网和大数据分析的互联网+寻路系统的构建和有关贪心算法、预处理算法的改进技术，并对如何使用互联网+寻路系统解决实际问题进行了探讨。本文的研究是对这种新的互联网+技术的提升、总结和推广，其结果具有较重要的应用价值。

【关键词】互联网+寻路系统 物联网 大数据A+算法 Floyd算法

无论现实生活还是电子游戏，寻路问题总是无处不在。从精确定位安排路线的GPS卫星导航，到游戏中自动安排行径路线，我们总是不自觉地与寻路打交道，寻路算法也成了日常生活最常接触到的算法之一。近年来，互联网+时代来临，物联网产业兴起，智慧物联技术愈来愈融入我们的生活，物联网这种“物物相连”的模式己延伸至各个产业，通过对千万用户信息的大数据分析，为各关联行业提供包括用户偏好在内的各式用户数据，以为用户提高最好的体验、为企业带来最佳的收益。在互联网+这一时代背景下，我们对许多问题的认识都会发生质的改变，寻路问题无疑也会顺应时代发生变革。我们将这种在互联网+时代下发生巨大改变的寻路问题称作互联网+寻路问题，用于实际模型中解决这类问题的系统是互联网+寻路系统。研究互联网+寻路系统，对于推进相关产业发展具有重要的现实意义。本文围绕互联网+寻路系统的构建，探讨寻路算法改进等关键技术问题，为相关技术升级提供思路。

1标准寻路算法

A*算法和Dijkstra算法是主流的寻路算法。其优点是简单、高效而又易于编辑。它们都是构建在贪心算法基础上的寻路算法，代码的基本结构也有很多相似点，而不同之处在于A*主要用于解决游戏、导航的实时寻路问题，Dijkstra作为搜索最短路径的主流算法更加被程序开发者所熟知。它们最大的区别在于贪心算法的启发式函数。程序员们在A*算法中加入了比Dijkstra更加“贪心”的启发式函数来提高运算效率。用于搜索最短路径的Dijkstra算法在追求高效的同时也得保证最优解的准确性，因此，优化Di.jkstra算法显得更加困难。实际应用中，Dijkstra常见的优化方法如使用斐波那契堆、小根堆以及链表等都是在优化路径搜索的枚举过程，这些方法对时间复杂度的优化相当有限。

Floyd算法在精确计算众多节点间的最短路径时，有很大的优越性。基于Floyd的特性，一次运算便能得出地图中所有结点间点最短路径，然后再将这些路径保存起来，当用户搜索到其中包含的路径时，直接将预存的路径提供给用户即可。这类方法也被称为“打表”。“打表”思想的应用相当广泛，例如各类下载软件会将下载量大的一些磁力链接提前在服务器中预处理，当用户需要下载时便能以最快的速度从服务器中下载，并能节省下载软件从同一个磁力链接地址多次抽调资源的流量;又如有时在解决问题时无法通过算法程序在规定时间内得出答案，就可以考虑先用程序跑出各种数据对应的答案然后存储起来，再用这些数据匹配输入数据并直接给出预先计算出的答案。“打表”思想为人们提供了一种近似一劳永逸的方法，只需预先的一次计算，之后便能直接享用预处理出的结果。对于一些反复使用到的数据，“打表”既能节约资源占用，又能节省运算时间，相较于“打表”后所避免的龐大复杂度浪费，复杂度极高的Floyd算法也显得尤其高效。然而，当地图的尺寸大到一定的程度，甚至连使用导航网格方法的时间复杂度都大得无法操作时，导航软件又该怎么进行寻路呢？对此，本篇论文将会在互联网+寻路系统部分进行仔细探讨。

2互联网+寻路系统

基于众多优秀的寻路算法，各式各样的寻路模型诞生了。物联网技术拓宽了寻路模型的广度、发展出新的寻路问题，大数据技术为寻路系统提供了系统性的优化、赋予其对寻路问题全新的处理方式，这种在物联网时代下发生极大变革的寻路模型和系统我们称为互联网+寻路模型与互联网+寻路系统，如图1所示。

2.1互联网+寻路模型

首先讨论如何构建互联网+寻路模型。寻路问题衍生出的互联网+寻路模型是基于一些特殊限制条件的较为复杂的模型，这些限制条件来源于各类反馈信息，模型使用的反馈信息可以是来自软件本身用户的反馈数据，也可以是通过物联网技术得到的关联行业数据。我们首先要搭建出寻路模型的基本框架，然后对收集的反馈信息进行大数据处理，将处理后的数据加入模型框架的各个步骤中并对一部分框架进行拓深、变形，将整个模型进行整理、修饰后，互联网+寻路模型便构建完成了。

不同于直接开创新的互联网+寻路模型，将互联网+思维应用于原有的寻路模型上以提供高效率的优化，是物联网时代下革新寻路模型的另一重要方式。对于大多数已经在实际问题中得到应用的寻路模型而言，它们几乎已经达到了完整的程度，不过互联网+思维依旧为这些模型提供了不少提升空间。

利用物联网技术的特性，一方面，导航软件可以将地图导航与各类相关APP关联起来，通过数据共享与大数据分析，优化地图导航的算法实现。

不同于物联网技术，利用人工智能技术优化互联网+寻路模型主要利用的是一种经验性的搜索思维。地图导航软件的程序设计者们可以设计一个基于深度学习算法的人工智能程序，并将多张复杂的城市地图数字化后整合到一起，用人工智能来模拟在整合的数字化地图中各地点间的路径搜索，使之积累各种路况情况下的搜索经验，并将这些经验应用于实际生活中地图导航的搜索引擎中。这种经验性的寻路算法也类似于A*的启发式算法，不过其效率与准确率的决定因素远多于A*算法，包括人工智能使用的深度学习算法、模拟过程中构建的数字地图、考虑到的道路可能性组合的完整程度等，因此利用人工智能数字模拟的优化不一定优于使用物联网技术的优化。

利用互联网+思维优化传统的寻路模型，在资金和时间方面的投入相对较低，其市场前景也并不亚于开创新的互联网+寻路模型。优化旧有的与开发创新的，两者对投资者而言都十分重要。

2.2互联网+寻路系统与算法改进

2.2.1互联网+寻路系统的概念

系统和模型是互相对应的。模型是问题、理论在实际生活中的应用，系统是实现与处理这个模型的技术基础。互联网+寻路系统，是在实际生活中应用互联网+寻路模型的技术支持，为新时代下的寻路问题提供新的解决方法，而融汇互联网+思维的寻路算法正是这一系统的核心。

2.2.2物联网时代下的贪心算法

互联网+思维对贪心算法的优化主要体现在两个方面：一是我们之前提到过的通过用户历史路径选择偏好来编写启发式函数;二是通过对相关产业收集到的各类数据进行大数据分析，拓展贪心算法的启发式函数。基于上述两种启发式函数的贪心算法往往比普通优化下的A*算法更优一一无论是时间复杂度还是路径优越度，这得益于物联网与大数据技术基于实践数据以及统计学最优的特性。

这里我们同样以地图导航系统为例，深入探讨这两种优化下的贪心算法。

用户的历史路径选择偏好，是用户在实践中对各种路况的路径选择的经验性偏好，通过实践得出的经验性数据往往比纯粹计算模拟得出的数据更准确且贴合实际。地图导航软件有两种途径去收集用户的路径偏好数据。首先，导航软件可以在征得用户同意的情况下常驻后台，利用卫星定位监控用户在某种路况下对路径的选择，并将之上传、汇总，利用大数据技术分析后在启发式函数中加入这些经验性的路径取舍抉择并赋予其高优先度。其次，在导航软件已有的启发式函数的基础上，当用户使用地图导航时，若在某些路段偏离导航选择了另一路线，并且这些路段的通行时间比软件预期的更短，那么导航软件会将这些更改后的路径抉择上传、汇总，在大数据分析后对原有的启发式函数进行更新。这些基于用户偏好的启发式函数在使用时往往也具有一种较为人性化的选择，不同于普通优化的A*算法，这种贪心算法在积累了足够多的偏好数据后便不会出现为了路径最短而选择一些糟糕的路线，例如一条泥泞的近道，它更倾向于选择那些大多数人都喜欢走的路线。导航数据处理过程如图2所示。

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

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

2.2.3预处理算法的革新

我们在讨论Floyd算法的时候提到了它在寻路系统中可用于预处理一些常用的路径，而这种预处理受其O（n3）的时间复杂度的影响有相当程度的局限性，即使利用导航网格方法和下三角矩阵的性质进行优化，也是O（n2）以上的复杂度。那么我们应该怎么利用互联网+思维来优化预处理算法呢？本篇论文将提供两种思路：一是将时间复杂度分散，利用区块链的思想将数据计算、处理、储存分担到各个用户终端上;二是摒弃Floyd算法，而利用大数据的思想，将用户的搜索记录与结果等数据上传、汇总，进行大数据处理后得出搜索度较高的一些地点与路径，并储存到服务器上。值得注意的是，为了节约空间复杂度，对于搜索度没有高到一定程度的结点，其储存的路径应当是互不包含的。

区块链的本质是一个去中心化的数据库，也就是将集中于服务器中的数据分散到每个终端中处理、储存。区块链的基础数据是以“哈希链”的形式保存，系统是由众多终端结点共同参与运行的，分布式是区块链的核心思想。利用互联网+思维，将这种去中心化的系统模式的分布式思想融入互联网+寻路系统的预处理算法中，大大分散了时间和空间上的复杂度。

对于另一种完全摒弃Floyd的预处理算法而言，时间复杂度主要在于大数据处理的过程，这对需要预处理大量路径的互联网+寻路系统而言无疑是相当合适的优化方案。

3互联网+寻路系统应用

这里介绍一种互联网+寻路系统在社会、城市层面的应用范例，我们称之为互联网+城市交通管理系统。

随着物联网时代的发展、人工智能时代的到来，无人驾驶汽车必将在世界范围内得到普及。对于无人驾驶技术而言，普通的交通管制己不再有意义，它需要的是一个基于城市交通网络流通情况的数字调控信息，而处理并发送这些调控信息的系统便是互联网+城市交通管理系统。

那么互联网+城市交通管理系统在技术层面上又将怎样实现呢？互联网+城市交通管理系统需要统筹物联网、大数据、人工智能、深度学习等技术，首先得靠这些技术完善一套高性能的互联网+寻路系统，其次再利用这个寻路系统来为无人驾驶汽车安排路径。

在为车辆规划路线时，互联网+城市交通管理系统需要通过物联网技术综合获取各类相关数据，譬如天气情况与行人流量状况，随后通过大数据分析这些数据为每个路段分配一个交通流量的限制值。为了简化问题，系统还需将城市划分成多个区域，然后通过大数据分类处理，将城市中的无人驾驶汽车按照当前所在位置与目的地区域分类，对每一类中包含的无人驾驶汽车流利用互联网+思维优化的启发式函数求解一遍参杂贪心思想的网络流问题。需要注意的是，考虑到所有分类的车辆，系统不能直接只为一组分类安排最优解，而应该为全部分类的车辆安排较优的分配方式。寻找出较优的分配方式后对这些区域再次细分，然后对上一次分类中的车辆按照更细分的区域分类，重复执行以上操作，直到每组分类中的车辆的目的地区域范围较小，随后对每辆车用互联网+寻路系统搜索从目的地区域到目的地的最优路径。最后，系统将每辆无人驾驶汽车在网络流中分配的路径，与在目的地区域中搜索出的最优路径串联起来，便规划完成了。到此，一个粗略的互联网+城市交通管理系统便己基本成型。

4结语

随着物联网新时代的到来，物联网、大数据、人工智能、深度学习等新兴技术得到了极大的发展。传统的寻路系统也进行着革新。互联网+寻路系统是新时代下运用互联网+思维构建的寻路系统。在互联网+寻路系统中，算法的计算复杂度大大降低，系统更加智能化，解决寻路问题显得更加实用高效。随着物联网时代的发展，互联网+寻路系统还会继续完善。

参考文献

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

[2]梁毅，周刚，基于定位点和路径复用的大型多人在线游戏寻路算法[J]，计算机应用，2010， 30 （12）： 3215-3217.

[3]曾晓敏.移动通信技术在物联网中的应用[J]，电子技术与软件工程，2018，19： 28.

[4]吴海建，吕军.物联网大数据处理中实时流计算系统的实践[J].电子技术与软件工程，2018，17： 170.

[5]刘钰，陆建峰，蔡海舟，基于改进A+算法的机器人路径规划方法研究[J].计算机技术与发展，201 2，12：108-111.

[6]张少鹏，王现康，段坚，A+算法在移动机器人路徑规划中的应用[J]，机械工程与自动化，201 2，6：147-148.151.

[7]李泽文，唐平，曾祥君，肖仁平，赵廷，基于Dijkstra算法的电网故障行波定位方法[J]，电力系统自动化，201 8，18： 162-168.

[8]吴果林，金珍，邓小方，稀疏网络的Floyd动态优化算法[J]，江西师范大学学报（自然科学版），2013，37 （01）： 28-32.

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