《大数据的互联网和寻路系统分析.docx》由会员分享，可在线阅读，更多相关《大数据的互联网和寻路系统分析.docx（10页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、大数据的互联网和寻路系统分析【摘要】互联网+寻路系统是基于物联网技术、通过大数据分析对标准寻路算法进行优化与拓展，并将之运用于实际生活中、解决现实问题的寻路系统。介绍了互联网+寻路系统的基本概念及其重要应用价值，重点讨论了用互联网+思维优化寻路模型的方法，研究了基于物联网和大数据分析的互联网+寻路系统的构建和有关贪心算法、预处理算法的改良技术，并对怎样使用互联网+寻路系统解决实际问题进行了讨论。本文的研究是对这种新的互联网+技术的提升、总结和推广，其结果具有较重要的应用价值。【关键词】互联网+寻路系统;物联网;大数据;A*算法;Floyd算法;无论现实生活还是电子游戏，寻路问题总是无处不在。从
2、准确定位安排道路的GPS卫星导航，到游戏中自动安排行径道路，我们总是不自觉地与寻路打交道，寻路算法也成了日常生活最常接触到的算法之一。近年来，互联网+时代来临，物联网产业兴起，智慧物联技术愈来愈融入我们的生活，物联网这种“物物相连的形式已延伸至各个产业，通过对千万用户信息的大数据分析，为各关联行业提供包括用户偏好在内的各式用户数据，以为用户提高最好的体验、为企业带来最佳的收益。在互联网+这一时代背景下，我们对很多问题的认识都会发生质的改变，寻路问题无疑也会顺应时生变革。我们将这种在互联网+时代下发生宏大改变的寻路问题称作互联网+寻路问题，用于实际模型中解决这类问题的系统是互联网+寻路系统。研究
3、互联网+寻路系统，对于推进相关产业发展具有重要的现实意义。本文围绕互联网+寻路系统的构建，讨论寻路算法改良等关键技术问题，为相关技术升级提供思路。1标准寻路算法A*算法和Dijkstra算法是主流的寻路算法。其优点是简单、高效而又易于编辑。它们都是构建在贪心算法基础上的寻路算法，代码的基本构造也有很多类似点，而不同之处在于A*主要用于解决游戏、导航的实时寻路问题,Dijkstra作为搜索最短途径的主流算法愈加被程序开发者所熟知。它们最大的区别在于贪心算法的启发式函数。程序员们在A*算法中参加了比Dijkstra愈加“贪心的启发式函数来提高运算效率。用于搜索最短途径的Dijkstra算法在追求高
4、效的同时也得保证最优解的准确性，因而，优化Dijkstra算法显得愈加困难。实际应用中，Dijkstra常见的优化方法如使用斐波那契堆、小根堆以及链表等都是在优化途径搜索的枚举经过，这些方法对时间复杂度的优化相当有限。Floyd算法在准确计算诸多节点间的最短途径时，有很大的优越性。基于Floyd的特性，一次运算便能得出地图中所有结点间点最短途径，然后再将这些途径保存起来，当用户搜索到其中包含的途径时，直接将预存的途径提供应用户即可。这类方法也被称为“打表。“打表思想的应用相当广泛，例如各类下载软件会将下载量大的一些磁力链接提早在服务器中预处理，当用户需要下载时便能以最快的速度从服务器中下载，并
5、能节省下载软件从同一个磁力链接地址屡次抽调资源的流量；又如有时在解决问题时无法通过算法程序在规定时间内得出答案，就能够考虑先用程序跑出各种数据对应的答案然后存储起来，再用这些数据匹配输入数据并直接给出预先计算出的答案。“打表思想为人们提供了一种近似一劳永逸的方法，只需预先的一次计算，之后便能直接享用预处理出的结果。对于一些反复使用到的数据，“打表既能节约资源占用，又能节省运算时间，相较于“打表后所避免的庞大复杂度浪费，复杂度极高的Floyd算法也显得尤其高效。然而，当地图的尺寸大到一定的程度，甚至连使用导航网格方法的时间复杂度都大得无法操作时，导航软件又该怎么进行寻路呢？对此，本篇论文将会在互
6、联网+寻路系统部分进行仔细讨论。2互联网+寻路系统基于诸多优秀的寻路算法，各式各样的寻路模型诞生了。物联网技术拓宽了寻路模型的广度、发展出新的寻路问题，大数据技术为寻路系统提供了系统性的优化、赋予其对寻路问题全新的处理方式，这种在物联网时代下发生极大变革的寻路模型和系统我们称为互联网+寻路模型与互联网+寻路系统,如图1所示。2.1互联网+寻路模型首先讨论怎样构建互联网+寻路模型。寻路问题衍生出的互联网+寻路模型是基于一些特殊限制条件的较为复杂的模型，这些限制条件来源于各类反应信息，模型使用的反应信息能够是来自软件本身用户的反应数据，可以以是通过物联网技术得到的关联行业数据。我们首先要搭建出寻路
7、模型的基本框架，然后对收集的反应信息进行大数据处理，将处理后的数据参加模型框架的各个步骤中并对一部分框架进行拓深、变形，将整个模型进行整理、修饰后，互联网+寻路模型便构建完成了。不同于直接创始新的互联网+寻路模型，将互联网+思维应用于原有的寻路模型上以提供高效率的优化，是物联网时代下革新寻路模型的另一重要方式。对于大多数已经在实际问题中得到应用的寻路模型而言，它们几乎已经到达了完好的程度，不过互联网+思维照旧为这些模型提供了不少提升空间。利用物联网技术的特性，一方面，导航软件能够将地图导航与各类相关APP关联起来，通过数据分享与大数据分析，优化地图导航的算法实现。不同于物联网技术，利用人工智能
8、技术优化互联网+寻路模型主要利用的是一种经历性的搜索思维。地图导航软件的程序设计者们能够设计一个基于深度学习算法的人工智能程序，并将多张复杂的城市地图数字化后整合到一起，用人工智能来模拟在整合的数字化地图中各地点间的途径搜索，使之积累各种路况情况下的搜索经历，并将这些经历应用于实际生活中地图导航的搜索引擎中。这种经历性的寻路算法也类似于A*的启发式算法，不过其效率与准确率的决定因素远多于A*算法，包括人工智能使用的深度学习算法、模拟经过中构建的数字地图、考虑到的道路可能性组合的完好程度等，因而利用人工智能数字模拟的优化不一定优于使用物联网技术的优化。利用互联网+思维优化传统的寻路模型，图1：互
9、联网+寻路模型与系统在资金和时间方面的投入相对较低，其市场前景也并不亚于创始新的互联网+寻路模型。优化旧有的与开发创新的，两者对投资者而言都特别重要。2.2互联网+寻路系统与算法改良2.2.1互联网+寻路系统的概念系统和模型是相互对应的。模型是问题、理论在实际生活中的应用，系统是实现与处理这个模型的技术基础。互联网+寻路系统，是在实际生活中应用互联网+寻路模型的技术支持，为现代下的寻路问题提供新的解决方法，而融汇互联网+思维的寻路算法正是这一系统的核心。2.2.2物联网时代下的贪心算法互联网+思维对贪心算法的优化主要体如今两个方面：一是我们之前提到过的通过用户历史途径选择偏好来编写启发式函数；
10、二是通过对相关产业收集到的各类数据进行大数据分析，拓展贪心算法的启发式函数。基于上述两种启发式函数的贪心算法往往比普通优化下的A*算法更优无论是时间复杂度还是途径优越度，这得益于物联网与大数据技术基于实践数据以及统计学最优的特性。这里我们同样以地图导航系统为例，深化讨论这两种优化下的贪心算法。用户的历史途径选择偏好，是用户在实践中对各种路况的途径选择的经历性偏好，通过实践得出的经历性数据往往比纯粹计算模拟得出的数据更准确且贴合实际。地图导航软件有两种途径去收集用户的途径偏好数据。首先，导航软件能够在征得用户同意的情况下常驻后台，利用卫星定位监控用户在某种路况下对途径的选择，并将之上传、汇总，利
11、用大数据技术分析后在启发式函数中参加这些经历性的途径取舍抉择并赋予其高优先度。其次，在导航软件已有的启发式函数的基础上，当用户使用地图导航时，若在某些路段偏离导航选择了另一道路，并且这些路段的通行时间比软件预期的更短，那么导航软件会将这些更改后的途径抉择上传、汇总，在大数据分析后对原有的启发式函数进行更新。这些基于用户偏好的启发式函数在使用时往往也具有一种较为人性化的选择，不同于普通优化的A*算法，这种贪心算法在积累了足够多的偏好数据后便不会出现为了途径最短而选择一些糟糕的道路，例如一条泥泞的近道，它更倾向于选择那些大多数人都喜欢走的道路。导航数据处理经过如图2所示。与地图导航相关的数据涵盖了
12、很多方面，如一个地段的天气情况、某个地区的微信收发总数、某条道路的车载广播接收情况、某一路段测速仪的平均测量数值、甚至是某一区域4G基站的负荷程度。其中大部分数据反映的是一个区域的人流量以及交通流量，还有的数据反映一个路段的通行能否方便、快速。启发式函数中引入相关行业数据的优化后，贪心算法会首先躲避掉4G基站负荷大、车载广播接收多的路段，由于这些路段的人流量与车流量必定很大，而优先选择平均测速高、天气情况较好的路段。这种启发式函数与用户偏好优化下的启发式函数产生了两种不同的优先级别，合理选用这两种优先取舍的标准对优化互联网+寻路系统特别重要。而不同于用户偏好的是，这些数据是实时性的，其优化的启
13、发式函数也是实时性的，因而导航软件需要随时监控这些数据并为用户更新启发式函数的相应模块。启发式函数是贪心算法的核心，利用互联网+思维优化启发式函数比程序设计者们拼尽脑汁想出的优化方案简单很多，而其时间复杂度与精准程度也愈加优越。引入互联网+思维对构建与优化互联网+寻路系统至关重要。2.2.3预处理算法的革新我们在讨论Floyd算法的时候提到了它在寻路系统中可用于预处理一些常用的途径，而这种预处理受其O(n3)的时间复杂度的影响有相当程度的局限性，即便利用导航网格方法和下三角矩阵的性质进行优化，也是O(n2)以上的复杂度。那么我们应该怎么利用互联网+思维来优化预处理算法呢？本篇论文将提供两种思路
14、：一是将时间复杂度分散，利用区块链的思想将数据计算、处理、储存分担到各个用户终端上；二是摒弃Floyd算法，而利用大数据的思想，将用户的搜索记录与结果等数据上传、汇总，进行大数据处理后得出搜索度较高的一些地点与途径，并储存到服务器上。值得注意的是，为了节约空间复杂度，对于搜索度没有高到一定程度的结点，其储存的途径应当是互不包含的。区块链的本质是一个去中心化的数据库，也就是将集中于服务器中的数据分散到每个终端中处理、储存。区块链的基础数据是以“哈希链的形式保存，系统是由诸多终端结点共同介入运行的，分布式是区块链的核心思想。利用互联网+思维，将这种去中心化的系统形式的分布式思想融入互联网+寻路系统
15、的预处理算法中，大大分散了时间和空间上的复杂度。对于另一种完全摒弃Floyd的预处理算法而言，时间复杂度主要在于大数据处理的经过，这对需要预处理大量途径的互联网+寻路系统而言无疑是相当适宜的优化方案。3互联网+寻路系统应用这里介绍一种互联网+寻路系统在社会、城市层面的应用范例，我们称之为互联网+城市交通管理系统。随着物联网时代的发展、人工智能时代的到来，无人驾驶汽车必将在世界范围内得到普及。对于无人驾驶技术而言，普通的交通管制已不再有意义，它需要的是一个基于城市交通网络流通情况的数字调控信息，而处理并发送这些调控信息的系统便是互联网+城市交通管理系统。那么互联网+城市交通管理系统在技术层面上又
16、将如何实现呢？互联网+城市交通管理系统需要统筹物联网、大数据、人工智能、深度学习等技术，首先得靠这些技术完善一套高性能的互联网+寻路系统，其次再利用这个寻路系统来为无人驾驶汽车安排途径。在为车辆规划道路时，互联网+城市交通管理系统需要通过物联网技术综合获取各类相关数据，譬如天气情况与行人流量状况，随后通过大数据分析这些数据为每个路段分配一个交通流量的限制值。为了简化问题，系统还需将城市划分成多个区域，然后通过大数据分类处理，将城市中的无人驾驶汽车根据当前所在位置与目的地区域分类，对每一类中包含的无人驾驶汽车流利用互联网+思维优化的启发式函数求解一遍参杂贪心思想的网络流问题。需要注意的是，考虑到
17、所有分类的车辆，系统不能直接只为一组分类安排最优解，而应该为全部分类的车辆安排较优的分配方式。寻找出较优的分配方式后对这些区域再次细分，然后对上一次分类中的车辆根据更细分的区域分类，重复执行以上操作，直到每组分类中的车辆的目的地区域范围较小，随后对每辆车用互联网+寻路系统搜索从目的地区域到目的地的最优途径。最后，系统将每辆无人驾驶汽车在网络流中分配的途径，与在目的地区域中搜索出的最优途径串联起来，便规划完成了。到此，一个粗略的互联网+城市交通管理系统便已基本成型。随着物联网现代的到来，物联网、大数据、人工智能、深度学习等新兴技术得到了极大的发展。传统的寻路系统也进行着革新。互联网+寻路系统是现代下运用互联网+思维构建的寻路系统。在互联网+寻路系统中，上接166页算法的计算复杂度大大降低，系统愈加智能化，解决寻路问题显得愈加实用高效。随着物联网时代的发展，互联网+寻路系统还会继续完善。