本站小編為你精心準備了大數據的互聯網和尋路系統分析參考范文，愿這些范文能點燃您思維的火花，激發您的寫作靈感。歡迎深入閱讀并收藏。

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

【關鍵詞】互聯網+尋路系統;物聯網;大數據;A*算法;Floyd算法;

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

1標準尋路算法A*算法和Dijkstra算法是主流的尋路算法。

其優點是簡單、高效而又易于編輯。它們都是構建在貪心算法基礎上的尋路算法，代碼的基本結構也有很多相似點，而不同之處在于A*主要用于解決游戲、導航的實時尋路問題,Dijkstra作為搜索最短路徑的主流算法更加被程序開發者所熟知。它們最大的區別在于貪心算法的啟發式函數。程序員們在A*算法中加入了比Dijkstra更加“貪心”的啟發式函數來提高運算效率。用于搜索最短路徑的Dijkstra算法在追求高效的同時也得保證最優解的準確性，因此，優化Dijkstra算法顯得更加困難。實際應用中，Dijkstra常見的優化方法如使用斐波那契堆、小根堆以及鏈表等都是在優化路徑搜索的枚舉過程，這些方法對時間復雜度的優化相當有限。Floyd算法在精確計算眾多節點間的最短路徑時，有很大的優越性。基于Floyd的特性，一次運算便能得出地圖中所有結點間點最短路徑，然后再將這些路徑保存起來，當用戶搜索到其中包含的路徑時，直接將預存的路徑提供給用戶即可。這類方法也被稱為“打表”。“打表”思想的應用相當廣泛，例如各類下載軟件會將下載量大的一些磁力鏈接提前在服務器中預處理，當用戶需要下載時便能以最快的速度從服務器中下載，并能節省下載軟件從同一個磁力鏈接地址多次抽調資源的流量；又如有時在解決問題時無法通過算法程序在規定時間內得出答案，就可以考慮先用程序跑出各種數據對應的答案然后存儲起來，再用這些數據匹配輸入數據并直接給出預先計算出的答案。“打表”思想為人們提供了一種近似一勞永逸的方法，只需預先的一次計算，之后便能直接享用預處理出的結果。對于一些反復使用到的數據，“打表”既能節約資源占用，又能節省運算時間，相較于“打表”后所避免的龐大復雜度浪費，復雜度極高的Floyd算法也顯得尤其高效。然而，當地圖的尺寸大到一定的程度，甚至連使用導航網格方法的時間復雜度都大得無法操作時，導航軟件又該怎么進行尋路呢？對此，本篇論文將會在互聯網+尋路系統部分進行仔細探討。

2互聯網+尋路系統

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

2.1互聯網+尋路模型

首先討論如何構建互聯網+尋路模型。尋路問題衍生出的互聯網+尋路模型是基于一些特殊限制條件的較為復雜的模型，這些限制條件來源于各類反饋信息，模型使用的反饋信息可以是來自軟件本身用戶的反饋數據，也可以是通過物聯網技術得到的關聯行業數據。我們首先要搭建出尋路模型的基本框架，然后對收集的反饋信息進行大數據處理，將處理后的數據加入模型框架的各個步驟中并對一部分框架進行拓深、變形，將整個模型進行整理、修飾后，互聯網+尋路模型便構建完成了。不同于直接開創新的互聯網+尋路模型，將互聯網+思維應用于原有的尋路模型上以提供高效率的優化，是物聯網時代下革新尋路模型的另一重要方式。對于大多數已經在實際問題中得到應用的尋路模型而言，它們幾乎已經達到了完整的程度，不過互聯網+思維依舊為這些模型提供了不少提升空間。利用物聯網技術的特性，一方面，導航軟件可以將地圖導航與各類相關APP關聯起來，通過數據共享與大數據分析，優化地圖導航的算法實現。不同于物聯網技術，利用人工智能技術優化互聯網+尋路模型主要利用的是一種經驗性的搜索思維。地圖導航軟件的程序設計者們可以設計一個基于深度學習算法的人工智能程序，并將多張復雜的城市地圖數字化后整合到一起，用人工智能來模擬在整合的數字化地圖中各地點間的路徑搜索，使之積累各種路況情況下的搜索經驗，并將這些經驗應用于實際生活中地圖導航的搜索引擎中。這種經驗性的尋路算法也類似于A*的啟發式算法，不過其效率與準確率的決定因素遠多于A*算法，包括人工智能使用的深度學習算法、模擬過程中構建的數字地圖、考慮到的道路可能性組合的完整程度等，因此利用人工智能數字模擬的優化不一定優于使用物聯網技術的優化。利用互聯網+思維優化傳統的尋路模型，圖1：互聯網+尋路模型與系統在資金和時間方面的投入相對較低，其市場前景也并不亞于開創新的互聯網+尋路模型。優化舊有的與開發創新的，兩者對投資者而言都十分重要。

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結語

隨著物聯網新時代的到來，物聯網、大數據、人工智能、深度學習等新興技術得到了極大的發展。傳統的尋路系統也進行著革新。互聯網+尋路系統是新時代下運用互聯網+思維構建的尋路系統。在互聯網+尋路系統中，<<上接166頁算法的計算復雜度大大降低，系統更加智能化，解決尋路問題顯得更加實用高效。隨著物聯網時代的發展，互聯網+尋路系統還會繼續完善。

參考文獻

[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].計算機技術與發展,2012,12:108-111.

[6]張少鵬,王現康,段堅,A*算法在移動機器人路徑規劃中的應用[J],機械工程與自動化,2012,6:147-148.151.

[7]李澤文,唐平,曾祥君,肖仁平,趙廷,基于Dijkstra算法的電網故障行波定位方法[J],電力系統自動化,2018,18:162-168.

[8]吳果林,金珍,鄧小方,稀疏網絡的Floyd動態優化算法[J],江西師范大學學報(自然科學版),2013,37(01):28-32.

[9]鄒桂芳,張培愛,網絡優化中最短路問題的改進FLOYD算法[J].科學技術與工程,2011,28:6875-6878,6892.

作者：沈煜航 李甜 李家胤 單位：電子科技大學信息與通信學院