基于物聯(lián)網(wǎng)和大數(shù)據(jù)分析的互聯(lián)網(wǎng)+尋路系統(tǒng)研究

沈煜航 李甜 李家胤

摘要

互聯(lián)網(wǎng)+尋路系統(tǒng)是基于物聯(lián)網(wǎng)技術、通過大數(shù)據(jù)分析對標準尋路算法進行優(yōu)化與拓展，并將之運用于實際生活中、解決現(xiàn)實問題的尋路系統(tǒng)。介紹了互聯(lián)網(wǎng)+尋路系統(tǒng)的基本概念及其重要應用價值，重點討論了用互聯(lián)網(wǎng)+思維優(yōu)化尋路模型的方法，研究了基于物聯(lián)網(wǎng)和大數(shù)據(jù)分析的互聯(lián)網(wǎng)+尋路系統(tǒng)的構建和有關貪心算法、預處理算法的改進技術，并對如何使用互聯(lián)網(wǎng)+尋路系統(tǒng)解決實際問題進行了探討。本文的研究是對這種新的互聯(lián)網(wǎng)+技術的提升、總結和推廣，其結果具有較重要的應用價值。

【關鍵詞】互聯(lián)網(wǎng)+尋路系統(tǒng) 物聯(lián)網(wǎng) 大數(shù)據(jù)A+算法 Floyd算法

無論現(xiàn)實生活還是電子游戲，尋路問題總是無處不在。從精確定位安排路線的GPS衛(wèi)星導航，到游戲中自動安排行徑路線，我們總是不自覺地與尋路打交道，尋路算法也成了日常生活最常接觸到的算法之一。近年來，互聯(lián)網(wǎng)+時代來臨，物聯(lián)網(wǎng)產(chǎn)業(yè)興起，智慧物聯(lián)技術愈來愈融入我們的生活，物聯(lián)網(wǎng)這種“物物相連”的模式己延伸至各個產(chǎn)業(yè)，通過對千萬用戶信息的大數(shù)據(jù)分析，為各關聯(lián)行業(yè)提供包括用戶偏好在內(nèi)的各式用戶數(shù)據(jù)，以為用戶提高最好的體驗、為企業(yè)帶來最佳的收益。在互聯(lián)網(wǎng)+這一時代背景下，我們對許多問題的認識都會發(fā)生質的改變，尋路問題無疑也會順應時代發(fā)生變革。我們將這種在互聯(lián)網(wǎng)+時代下發(fā)生巨大改變的尋路問題稱作互聯(lián)網(wǎng)+尋路問題，用于實際模型中解決這類問題的系統(tǒng)是互聯(lián)網(wǎng)+尋路系統(tǒng)。研究互聯(lián)網(wǎng)+尋路系統(tǒng)，對于推進相關產(chǎn)業(yè)發(fā)展具有重要的現(xiàn)實意義。本文圍繞互聯(lián)網(wǎng)+尋路系統(tǒng)的構建，探討尋路算法改進等關鍵技術問題，為相關技術升級提供思路。

1標準尋路算法

A*算法和Dijkstra算法是主流的尋路算法。其優(yōu)點是簡單、高效而又易于編輯。它們都是構建在貪心算法基礎上的尋路算法，代碼的基本結構也有很多相似點，而不同之處在于A*主要用于解決游戲、導航的實時尋路問題，Dijkstra作為搜索最短路徑的主流算法更加被程序開發(fā)者所熟知。它們最大的區(qū)別在于貪心算法的啟發(fā)式函數(shù)。程序員們在A*算法中加入了比Dijkstra更加“貪心”的啟發(fā)式函數(shù)來提高運算效率。用于搜索最短路徑的Dijkstra算法在追求高效的同時也得保證最優(yōu)解的準確性，因此，優(yōu)化Di.jkstra算法顯得更加困難。實際應用中，Dijkstra常見的優(yōu)化方法如使用斐波那契堆、小根堆以及鏈表等都是在優(yōu)化路徑搜索的枚舉過程，這些方法對時間復雜度的優(yōu)化相當有限。

Floyd算法在精確計算眾多節(jié)點間的最短路徑時，有很大的優(yōu)越性?；贔loyd的特性，一次運算便能得出地圖中所有結點間點最短路徑，然后再將這些路徑保存起來，當用戶搜索到其中包含的路徑時，直接將預存的路徑提供給用戶即可。這類方法也被稱為“打表”?！按虮怼彼枷氲膽孟喈攺V泛，例如各類下載軟件會將下載量大的一些磁力鏈接提前在服務器中預處理，當用戶需要下載時便能以最快的速度從服務器中下載，并能節(jié)省下載軟件從同一個磁力鏈接地址多次抽調資源的流量;又如有時在解決問題時無法通過算法程序在規(guī)定時間內(nèi)得出答案，就可以考慮先用程序跑出各種數(shù)據(jù)對應的答案然后存儲起來，再用這些數(shù)據(jù)匹配輸入數(shù)據(jù)并直接給出預先計算出的答案?！按虮怼彼枷霝槿藗兲峁┝艘环N近似一勞永逸的方法，只需預先的一次計算，之后便能直接享用預處理出的結果。對于一些反復使用到的數(shù)據(jù)，“打表”既能節(jié)約資源占用，又能節(jié)省運算時間，相較于“打表”后所避免的龐大復雜度浪費，復雜度極高的Floyd算法也顯得尤其高效。然而，當?shù)貓D的尺寸大到一定的程度，甚至連使用導航網(wǎng)格方法的時間復雜度都大得無法操作時，導航軟件又該怎么進行尋路呢？對此，本篇論文將會在互聯(lián)網(wǎng)+尋路系統(tǒng)部分進行仔細探討。

2互聯(lián)網(wǎng)+尋路系統(tǒng)

基于眾多優(yōu)秀的尋路算法，各式各樣的尋路模型誕生了。物聯(lián)網(wǎng)技術拓寬了尋路模型的廣度、發(fā)展出新的尋路問題，大數(shù)據(jù)技術為尋路系統(tǒng)提供了系統(tǒng)性的優(yōu)化、賦予其對尋路問題全新的處理方式，這種在物聯(lián)網(wǎng)時代下發(fā)生極大變革的尋路模型和系統(tǒng)我們稱為互聯(lián)網(wǎng)+尋路模型與互聯(lián)網(wǎng)+尋路系統(tǒng)，如圖1所示。

2.1互聯(lián)網(wǎng)+尋路模型

首先討論如何構建互聯(lián)網(wǎng)+尋路模型。尋路問題衍生出的互聯(lián)網(wǎng)+尋路模型是基于一些特殊限制條件的較為復雜的模型，這些限制條件來源于各類反饋信息，模型使用的反饋信息可以是來自軟件本身用戶的反饋數(shù)據(jù)，也可以是通過物聯(lián)網(wǎng)技術得到的關聯(lián)行業(yè)數(shù)據(jù)。我們首先要搭建出尋路模型的基本框架，然后對收集的反饋信息進行大數(shù)據(jù)處理，將處理后的數(shù)據(jù)加入模型框架的各個步驟中并對一部分框架進行拓深、變形，將整個模型進行整理、修飾后，互聯(lián)網(wǎng)+尋路模型便構建完成了。

不同于直接開創(chuàng)新的互聯(lián)網(wǎng)+尋路模型，將互聯(lián)網(wǎng)+思維應用于原有的尋路模型上以提供高效率的優(yōu)化，是物聯(lián)網(wǎng)時代下革新尋路模型的另一重要方式。對于大多數(shù)已經(jīng)在實際問題中得到應用的尋路模型而言，它們幾乎已經(jīng)達到了完整的程度，不過互聯(lián)網(wǎng)+思維依舊為這些模型提供了不少提升空間。

利用物聯(lián)網(wǎng)技術的特性，一方面，導航軟件可以將地圖導航與各類相關APP關聯(lián)起來，通過數(shù)據(jù)共享與大數(shù)據(jù)分析，優(yōu)化地圖導航的算法實現(xiàn)。

不同于物聯(lián)網(wǎng)技術，利用人工智能技術優(yōu)化互聯(lián)網(wǎng)+尋路模型主要利用的是一種經(jīng)驗性的搜索思維。地圖導航軟件的程序設計者們可以設計一個基于深度學習算法的人工智能程序，并將多張復雜的城市地圖數(shù)字化后整合到一起，用人工智能來模擬在整合的數(shù)字化地圖中各地點間的路徑搜索，使之積累各種路況情況下的搜索經(jīng)驗，并將這些經(jīng)驗應用于實際生活中地圖導航的搜索引擎中。這種經(jīng)驗性的尋路算法也類似于A*的啟發(fā)式算法，不過其效率與準確率的決定因素遠多于A*算法，包括人工智能使用的深度學習算法、模擬過程中構建的數(shù)字地圖、考慮到的道路可能性組合的完整程度等，因此利用人工智能數(shù)字模擬的優(yōu)化不一定優(yōu)于使用物聯(lián)網(wǎng)技術的優(yōu)化。

利用互聯(lián)網(wǎng)+思維優(yōu)化傳統(tǒng)的尋路模型，在資金和時間方面的投入相對較低，其市場前景也并不亞于開創(chuàng)新的互聯(lián)網(wǎng)+尋路模型。優(yōu)化舊有的與開發(fā)創(chuàng)新的，兩者對投資者而言都十分重要。

2.2互聯(lián)網(wǎng)+尋路系統(tǒng)與算法改進

2.2.1互聯(lián)網(wǎng)+尋路系統(tǒng)的概念

系統(tǒng)和模型是互相對應的。模型是問題、理論在實際生活中的應用，系統(tǒng)是實現(xiàn)與處理這個模型的技術基礎?；ヂ?lián)網(wǎng)+尋路系統(tǒng)，是在實際生活中應用互聯(lián)網(wǎng)+尋路模型的技術支持，為新時代下的尋路問題提供新的解決方法，而融匯互聯(lián)網(wǎng)+思維的尋路算法正是這一系統(tǒng)的核心。

2.2.2物聯(lián)網(wǎng)時代下的貪心算法

互聯(lián)網(wǎng)+思維對貪心算法的優(yōu)化主要體現(xiàn)在兩個方面：一是我們之前提到過的通過用戶歷史路徑選擇偏好來編寫啟發(fā)式函數(shù);二是通過對相關產(chǎn)業(yè)收集到的各類數(shù)據(jù)進行大數(shù)據(jù)分析，拓展貪心算法的啟發(fā)式函數(shù)。基于上述兩種啟發(fā)式函數(shù)的貪心算法往往比普通優(yōu)化下的A*算法更優(yōu)一一無論是時間復雜度還是路徑優(yōu)越度，這得益于物聯(lián)網(wǎng)與大數(shù)據(jù)技術基于實踐數(shù)據(jù)以及統(tǒng)計學最優(yōu)的特性。

這里我們同樣以地圖導航系統(tǒng)為例，深入探討這兩種優(yōu)化下的貪心算法。

用戶的歷史路徑選擇偏好，是用戶在實踐中對各種路況的路徑選擇的經(jīng)驗性偏好，通過實踐得出的經(jīng)驗性數(shù)據(jù)往往比純粹計算模擬得出的數(shù)據(jù)更準確且貼合實際。地圖導航軟件有兩種途徑去收集用戶的路徑偏好數(shù)據(jù)。首先，導航軟件可以在征得用戶同意的情況下常駐后臺，利用衛(wèi)星定位監(jiān)控用戶在某種路況下對路徑的選擇，并將之上傳、匯總，利用大數(shù)據(jù)技術分析后在啟發(fā)式函數(shù)中加入這些經(jīng)驗性的路徑取舍抉擇并賦予其高優(yōu)先度。其次，在導航軟件已有的啟發(fā)式函數(shù)的基礎上，當用戶使用地圖導航時，若在某些路段偏離導航選擇了另一路線，并且這些路段的通行時間比軟件預期的更短，那么導航軟件會將這些更改后的路徑抉擇上傳、匯總，在大數(shù)據(jù)分析后對原有的啟發(fā)式函數(shù)進行更新。這些基于用戶偏好的啟發(fā)式函數(shù)在使用時往往也具有一種較為人性化的選擇，不同于普通優(yōu)化的A*算法，這種貪心算法在積累了足夠多的偏好數(shù)據(jù)后便不會出現(xiàn)為了路徑最短而選擇一些糟糕的路線，例如一條泥濘的近道，它更傾向于選擇那些大多數(shù)人都喜歡走的路線。導航數(shù)據(jù)處理過程如圖2所示。

與地圖導航相關的數(shù)據(jù)涵蓋了許多方面，如一個地段的天氣情況、某個地區(qū)的微信收發(fā)總數(shù)、某條道路的車載廣播接收情況、某一路段測速儀的平均測量數(shù)值、甚至是某一區(qū)域4G基站的負荷程度。其中大部分數(shù)據(jù)反映的是一個區(qū)域的人流量以及交通流量，還有的數(shù)據(jù)反映一個路段的通行是否方便、快捷。啟發(fā)式函數(shù)中引入相關行業(yè)數(shù)據(jù)的優(yōu)化后，貪心算法會首先規(guī)避掉4G基站負荷大、車載廣播接收多的路段，因為這些路段的人流量與車流量必定很大，而優(yōu)先選擇平均測速高、天氣情況較好的路段。這種啟發(fā)式函數(shù)與用戶偏好優(yōu)化下的啟發(fā)式函數(shù)產(chǎn)生了兩種不同的優(yōu)先級別，合理選用這兩種優(yōu)先取舍的標準對優(yōu)化互聯(lián)網(wǎng)+尋路系統(tǒng)十分重要。而不同于用戶偏好的是，這些數(shù)據(jù)是實時性的，其優(yōu)化的啟發(fā)式函數(shù)也是實時性的，因此導航軟件需要隨時監(jiān)控這些數(shù)據(jù)并為用戶更新啟發(fā)式函數(shù)的相應模塊。

啟發(fā)式函數(shù)是貪心算法的核心，利用互聯(lián)網(wǎng)+思維優(yōu)化啟發(fā)式函數(shù)比程序設計者們拼盡腦汁想出的優(yōu)化方案簡單很多，而其時間復雜度與精準程度也更加優(yōu)越。引入互聯(lián)網(wǎng)+思維對構建與優(yōu)化互聯(lián)網(wǎng)+尋路系統(tǒng)至關重要。

2.2.3預處理算法的革新

我們在討論Floyd算法的時候提到了它在尋路系統(tǒng)中可用于預處理一些常用的路徑，而這種預處理受其O（n3）的時間復雜度的影響有相當程度的局限性，即使利用導航網(wǎng)格方法和下三角矩陣的性質進行優(yōu)化，也是O（n2）以上的復雜度。那么我們應該怎么利用互聯(lián)網(wǎng)+思維來優(yōu)化預處理算法呢？本篇論文將提供兩種思路：一是將時間復雜度分散，利用區(qū)塊鏈的思想將數(shù)據(jù)計算、處理、儲存分擔到各個用戶終端上;二是摒棄Floyd算法，而利用大數(shù)據(jù)的思想，將用戶的搜索記錄與結果等數(shù)據(jù)上傳、匯總，進行大數(shù)據(jù)處理后得出搜索度較高的一些地點與路徑，并儲存到服務器上。值得注意的是，為了節(jié)約空間復雜度，對于搜索度沒有高到一定程度的結點，其儲存的路徑應當是互不包含的。

區(qū)塊鏈的本質是一個去中心化的數(shù)據(jù)庫，也就是將集中于服務器中的數(shù)據(jù)分散到每個終端中處理、儲存。區(qū)塊鏈的基礎數(shù)據(jù)是以“哈希鏈”的形式保存，系統(tǒng)是由眾多終端結點共同參與運行的，分布式是區(qū)塊鏈的核心思想。利用互聯(lián)網(wǎng)+思維，將這種去中心化的系統(tǒng)模式的分布式思想融入互聯(lián)網(wǎng)+尋路系統(tǒng)的預處理算法中，大大分散了時間和空間上的復雜度。

對于另一種完全摒棄Floyd的預處理算法而言，時間復雜度主要在于大數(shù)據(jù)處理的過程，這對需要預處理大量路徑的互聯(lián)網(wǎng)+尋路系統(tǒng)而言無疑是相當合適的優(yōu)化方案。

3互聯(lián)網(wǎng)+尋路系統(tǒng)應用

這里介紹一種互聯(lián)網(wǎng)+尋路系統(tǒng)在社會、城市層面的應用范例，我們稱之為互聯(lián)網(wǎng)+城市交通管理系統(tǒng)。

隨著物聯(lián)網(wǎng)時代的發(fā)展、人工智能時代的到來，無人駕駛汽車必將在世界范圍內(nèi)得到普及。對于無人駕駛技術而言，普通的交通管制己不再有意義，它需要的是一個基于城市交通網(wǎng)絡流通情況的數(shù)字調控信息，而處理并發(fā)送這些調控信息的系統(tǒng)便是互聯(lián)網(wǎng)+城市交通管理系統(tǒng)。

那么互聯(lián)網(wǎng)+城市交通管理系統(tǒng)在技術層面上又將怎樣實現(xiàn)呢？互聯(lián)網(wǎng)+城市交通管理系統(tǒng)需要統(tǒng)籌物聯(lián)網(wǎng)、大數(shù)據(jù)、人工智能、深度學習等技術，首先得靠這些技術完善一套高性能的互聯(lián)網(wǎng)+尋路系統(tǒng)，其次再利用這個尋路系統(tǒng)來為無人駕駛汽車安排路徑。

在為車輛規(guī)劃路線時，互聯(lián)網(wǎng)+城市交通管理系統(tǒng)需要通過物聯(lián)網(wǎng)技術綜合獲取各類相關數(shù)據(jù)，譬如天氣情況與行人流量狀況，隨后通過大數(shù)據(jù)分析這些數(shù)據(jù)為每個路段分配一個交通流量的限制值。為了簡化問題，系統(tǒng)還需將城市劃分成多個區(qū)域，然后通過大數(shù)據(jù)分類處理，將城市中的無人駕駛汽車按照當前所在位置與目的地區(qū)域分類，對每一類中包含的無人駕駛汽車流利用互聯(lián)網(wǎng)+思維優(yōu)化的啟發(fā)式函數(shù)求解一遍參雜貪心思想的網(wǎng)絡流問題。需要注意的是，考慮到所有分類的車輛，系統(tǒng)不能直接只為一組分類安排最優(yōu)解，而應該為全部分類的車輛安排較優(yōu)的分配方式。尋找出較優(yōu)的分配方式后對這些區(qū)域再次細分，然后對上一次分類中的車輛按照更細分的區(qū)域分類，重復執(zhí)行以上操作，直到每組分類中的車輛的目的地區(qū)域范圍較小，隨后對每輛車用互聯(lián)網(wǎng)+尋路系統(tǒng)搜索從目的地區(qū)域到目的地的最優(yōu)路徑。最后，系統(tǒng)將每輛無人駕駛汽車在網(wǎng)絡流中分配的路徑，與在目的地區(qū)域中搜索出的最優(yōu)路徑串聯(lián)起來，便規(guī)劃完成了。到此，一個粗略的互聯(lián)網(wǎng)+城市交通管理系統(tǒng)便己基本成型。

4結語

隨著物聯(lián)網(wǎng)新時代的到來，物聯(lián)網(wǎng)、大數(shù)據(jù)、人工智能、深度學習等新興技術得到了極大的發(fā)展。傳統(tǒng)的尋路系統(tǒng)也進行著革新?；ヂ?lián)網(wǎng)+尋路系統(tǒng)是新時代下運用互聯(lián)網(wǎng)+思維構建的尋路系統(tǒng)。在互聯(lián)網(wǎng)+尋路系統(tǒng)中，算法的計算復雜度大大降低，系統(tǒng)更加智能化，解決尋路問題顯得更加實用高效。隨著物聯(lián)網(wǎng)時代的發(fā)展，互聯(lián)網(wǎng)+尋路系統(tǒng)還會繼續(xù)完善。

參考文獻

[1]李曉帆，許暢，小車遠程控制及自主尋路系統(tǒng)的設計與實現(xiàn)[J].計算機科學，2015， 42 （12）： 98-101.

[2]梁毅，周剛，基于定位點和路徑復用的大型多人在線游戲尋路算法[J]，計算機應用，2010， 30 （12）： 3215-3217.

[3]曾曉敏.移動通信技術在物聯(lián)網(wǎng)中的應用[J]，電子技術與軟件工程，2018，19： 28.

[4]吳海建，呂軍.物聯(lián)網(wǎng)大數(shù)據(jù)處理中實時流計算系統(tǒng)的實踐[J].電子技術與軟件工程，2018，17： 170.

[5]劉鈺，陸建峰，蔡海舟，基于改進A+算法的機器人路徑規(guī)劃方法研究[J].計算機技術與發(fā)展，201 2，12：108-111.

[6]張少鵬，王現(xiàn)康，段堅，A+算法在移動機器人路徑規(guī)劃中的應用[J]，機械工程與自動化，201 2，6：147-148.151.

[7]李澤文，唐平，曾祥君，肖仁平，趙廷，基于Dijkstra算法的電網(wǎng)故障行波定位方法[J]，電力系統(tǒng)自動化，201 8，18： 162-168.

[8]吳果林，金珍，鄧小方，稀疏網(wǎng)絡的Floyd動態(tài)優(yōu)化算法[J]，江西師范大學學報（自然科學版），2013，37 （01）： 28-32.

[9]鄒桂芳，張培愛，網(wǎng)絡優(yōu)化中最短路問題的改進FLOYD算法[J].科學技術與工程，2011， 28： 6875-6878， 6892.