沈煜航 李家胤 李甜

摘要：地圖導航系統(tǒng)是為解決尋路問題而構建于尋路算法之上的尋路系統(tǒng)。隨著物聯(lián)網技術的興起，尋路問題與各類用戶數據相關聯(lián)，衍生出具有物聯(lián)網時代意義的互聯(lián)網+尋路模型和尋路系統(tǒng)。該文分析了構建于互聯(lián)網+尋路模型下的尋路系統(tǒng)在地圖導航科技方面的應用，重點探討了尋路模型構建、導航系統(tǒng)尋路算法優(yōu)化和拓展相關的關鍵技術，還討論了人工智能在地圖導航尋路算法中的應用。全文以相關產業(yè)技術升級為目標，探索了物聯(lián)網時代地圖導航尋路系統(tǒng)的發(fā)展思路。

關鍵詞：互聯(lián)網+；地圖導航；尋路模型；物聯(lián)網； 貪心算法

中圖分類號：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

網約車作為近年來的一個新興產業(yè)已經在全國得到推廣，從都市到鄉(xiāng)縣，隨處都能使用這種網約租車業(yè)務。為網約車的精確定位、安排路線的GPS衛(wèi)星導航，需要與地圖導航系統(tǒng)打交道。地圖導航系統(tǒng)是為解決尋路問題而構建于尋路算法之上的尋路系統(tǒng)[1-2]。隨著物聯(lián)網技術[3-5]的興起，尋路問題與各類用戶數據相關聯(lián)，衍生出具有物聯(lián)網時代意義的互聯(lián)網+尋路模型，其中就包括以互聯(lián)網+思維將地圖導航、出租的士等行業(yè)相結合的地圖導航應用模型。本文探索討論了構建于互聯(lián)網+尋路模型下的尋路系統(tǒng)在地圖導航科技方面的應用，重點分析模型構建、尋路算法關鍵技術，目的是為相關產業(yè)技術升級提供參考思路。

1 基于互聯(lián)網+的地圖導航尋路模型

基于互聯(lián)網+的地圖導航尋路模型是一類基于特殊限制條件的復雜模型。這些條件，來源于各類反饋信息，包括來自地圖導航軟件本身用戶的反饋數據，也可以是通過物聯(lián)網技術得到的交通行業(yè)數據，等等。構建尋路模型，首先需要搭建模型基本框架，然后對收集的反饋信息進行大數據處理，再將處理后的數據加入模型框架的各個步驟中并對一部分框架進行拓深、變形，將整個模型進行整理、修飾，從而形成互聯(lián)網+地圖導航尋路模型。

地圖導航的尋路問題衍生出多個子問題，包括多約束條件下的司機匹配問題、基于交通流量的最優(yōu)路徑問題、拼車路徑問題[6，7]等。其中，對于司機匹配問題而言，尋路軟件需要解決的不只是傳統(tǒng)的圖匹配問題，還需要解決在同一打車地點的多個用戶需要包車、拼車、順風車、預約車等不同打車需求的司機匹配問題，這就需要利用打車軟件中統(tǒng)合的用戶與司機信息的大數據，進行司機偏好分類以及用戶等待時間容耐分類處理，為就近的司機按照他們的歷史偏好分派接單類型，為歷史時間容耐性低的用戶優(yōu)先匹配。

當然，隨著互聯(lián)網+思維的引入，地圖導航模型的功能以及實際問題上的應用并不會發(fā)生太大的改變，但其解決問題的方法會因互聯(lián)網+思維的優(yōu)化而革新。對于地圖導航模型而言，互聯(lián)網+思維帶來的優(yōu)化主要來源于兩個方面——基于智慧物聯(lián)大數據的優(yōu)化與基于人工智能數字模擬的優(yōu)化。利用物聯(lián)網技術的特性，一方面，導航軟件可以將地圖導航與各類相關APP關聯(lián)起來，通過數據共享與大數據分析，優(yōu)化地圖導航的算法實現(xiàn)。例如，我們可以將IOS的“健康”與“地圖”這兩個APP關聯(lián)起來，用戶在“健康”里統(tǒng)計步數與步行時間的同時，“地圖”中會統(tǒng)計用戶的行徑路線，并記錄下從出發(fā)地點到每個經過地點的步數與時間，將之上傳至服務器，服務器再對所有用戶的數據進行匯總與處理，得出某兩個地點間當前時刻的最優(yōu)路徑，甚至可以根據這些數據安排出一條最適合健身或散步的路徑。另一方面，導航軟件可以利用用戶的路徑選擇偏好以及反饋信息等數據，對導航算法進行優(yōu)化，或者對導航路線進行修正。

2 基于互聯(lián)網+的地圖導航尋路算法改進

互聯(lián)網+思維對優(yōu)化尋路算法有著重要作用。在物聯(lián)網技術的支持下，各種各樣的大數據分析為貪心算法的優(yōu)化提供了助力。有了歷史搜索大數據的幫助，“打表”預處理和實時尋路等過程中算法的時間復雜度呈指數級地降低。還有，隨著深度學習技術的提升，人工智能通過對各種路況的學習、理解也為建立一套經驗性的尋路算法提供了條件。

2.1 傳統(tǒng)尋路算法[8-11]討論

2.1.1 A*與Dijkstra算法及其優(yōu)化問題

主流的尋路算法，首推A*算法[8-9]。A*算法的優(yōu)點是簡單、高效而又易于編輯。A*和另一種常用算法即Dijkstra算法[10]都是構建在貪心算法基礎上的尋路算法。從大體上看，A*算法與Dijkstra算法極為相似，它們最大的區(qū)別在于貪心算法的啟發(fā)式函數不同。不過，在現(xiàn)實中，市區(qū)交通網絡的地圖龐大、路徑龐多，需要進行實時路徑搜索的A*算法面臨著時間復雜度上的挑戰(zhàn)，程序員們需要使用更加“貪心”的算法去優(yōu)化A*。在代碼方面，A*算法有嚴格的模塊化劃分，在修改地圖時，程序員只需在特定的模塊中增減禁行區(qū)與通路屬性即可，大大減少了地圖編輯者們的工作量，這也是A*算法受程序設計者的青睞的原因之一。

A*算法在搜索最短路徑時允許有容許誤差。相比而言，Dijkstra算法在搜索最短路徑方面更加高效，同時有更高的準確性。為保持這一優(yōu)點，Dijkstra算法優(yōu)化就顯得更困難一些。在處理Dijkstra的優(yōu)化問題上，國內誕生了一套備受程序開發(fā)者青睞的子算法——SPFA。作為Dijkstra的子算法，SPFA繼承了Dijkstra的貪心思想，并保持了Dijkstra的準確性，卻將其期望復雜度縮減至O（k*E），其中E是邊數，k是每個節(jié)點進入隊列的次數一般不高于2次。這種級別的優(yōu)化，幾乎將時間復雜度降低了一個次數，然而缺陷卻只是會被某種特殊的網絡情況卡成O（N2）的時間復雜度，我們只需要對這種情況特殊判斷，并通過貪心的啟發(fā)式算法去規(guī)避便可。

2.1.2 Floyd算法與“打表”思想

對于另一種更加簡單的尋路算法——Floyd算法[11]，程序設計者們往往因為其過高的時間復雜度而將之摒棄。然而不得不承認，F(xiàn)loyd在精確計算眾多節(jié)點間最短路徑時，仍有其優(yōu)越性。在考慮實際問題時，一個導航軟件在同一區(qū)域中短時間內可能會面對的數百萬級的客流量，若是其中每個用戶各自進行導航當然不成問題，但是他們的時間復雜度疊加在一起便是個大的離譜的數字。針對這種情況，F(xiàn)loyd便發(fā)揮作用了。我們不妨在每個用戶搜索路徑前，先將整張地圖進行A*的導航網格化處理，隨后用Floyd在分成小塊的局部導航網格中運行，因為Floyd的特性，一次運算便能得出所有結點間的最短路徑，然后再將這些路徑保存起來，當用戶搜索到其中的路徑時直接提供給用戶即可。這類方法也被稱為“打表”。“打表”思想的應用相當廣泛，譬如各類下載軟件會將用戶最常下載的一些磁力鏈接提前在服務器中預處理，以便用戶需要下載時能夠以最快的下載速度從服務器中直接下載，并能節(jié)省下載軟件從磁力鏈接地址抽調資源的流量。上述四種算法時間復雜度、應用模型和優(yōu)化方法比較，如表1所示。

2.2 貪心算法[12]的改進

互聯(lián)網+思維對貪心算法的優(yōu)化主要體現(xiàn)在兩個方面：一是通過用戶歷史路徑選擇偏好來編寫啟發(fā)式函數；二是通過對相關產業(yè)收集到的各類數據進行大數據分析，拓展貪心算法的啟發(fā)式函數。我們來探討在地圖導航系統(tǒng)中如何優(yōu)化貪心算法。

地圖導航軟件有兩種途徑去收集用戶的路徑偏好數據。首先，導航軟件可以在征得用戶同意的情況下常駐后臺，利用衛(wèi)星定位監(jiān)控用戶在某種路況下對路徑的選擇，并將之上傳、匯總，利用大數據技術分析后在啟發(fā)式函數中加入這些經驗性的路徑取舍抉擇并賦予其高優(yōu)先度。其次，在導航軟件已有的啟發(fā)式函數的基礎上，當用戶使用地圖導航時，若在某些路段偏離導航選擇了另一路線，并且這些路段的通行時間比軟件預期的更短，那么導航軟件會將這些更改后的路徑抉擇上傳、匯總，在大數據分析后對原有的啟發(fā)式函數進行更新。這些基于用戶偏好的啟發(fā)式函數在使用時往往也具有一種較為人性化的選擇，不同于普通優(yōu)化的A*算法。

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

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

2.3 預處理算法的改進

我們在討論Floyd算法的時候提到了它在尋路系統(tǒng)中可用于預處理一些常用的路徑，應該怎么利用互聯(lián)網+思維來優(yōu)化預處理算法[11]呢？有兩種思路：一是將時間復雜度分散，利用區(qū)塊鏈的思想將數據計算、處理、儲存分擔到各個用戶終端上；二是摒棄Floyd算法，而利用大數據的思想，將用戶的搜索記錄與結果等數據上傳、匯總，進行大數據處理后得出搜索度較高的一些地點與路徑，并儲存到服務器上。值得注意的是，為了節(jié)約空間復雜度，對于搜索度沒有高到一定程度的結點，其儲存的路徑應當是互不包含的。比如，如圖2所示，A-B-C-D-E這條線路中，若A、C、E是搜索度較高的三個結點，A-B-C、C-D-E、A-B-C-D-E是這三個地點間所對應的最優(yōu)路徑，那么只需要保存A、C、E三個結點以及A-B-C、C-D-E兩條路徑即可。而A、E兩點間的最短路徑用戶在搜索時會首先檢測到A、E兩結點在服務器中保存的結點之中，隨后通過在這些結點間的路徑搜索得出A、E間的最短路徑。

2.4 基于深度學習的經驗性尋路算法的應用

人工智能已經應用在了各種產業(yè)中，其在尋路系統(tǒng)中的應用也早已有人涉足。特斯拉（Tesla）作為無人駕駛汽車的研發(fā)大廠，一直致力于深度學習與人工智能的開發(fā)，其中利用人工智能來駕駛汽車更是其重點研究對象。近年來，特斯拉在無人駕駛技術上取得了不少成果，已經發(fā)展出了一套完善的自動駕駛系統(tǒng)。特斯拉利用Lindar、攝像頭和雷達實時監(jiān)控周遭信息，使用免費的無線3G/4G LTE網絡進行實時定位與路況數據交換，通過OTA來獲取最新的軟件和功能進一步擴展輔助駕駛的潛力，而其自動輔助駕駛硬件會在行駛過程中搜集數據進行分析與學習。在自動輔助駕駛系統(tǒng)方面，特斯拉編寫了一個效率極高的深度學習算法為輔助駕駛的人工智能程序積累經驗，它讓人工智能程序在各種模擬環(huán)境下運行以學習詳盡的應對方法，最后將積累了充分經驗的自動輔助駕駛系統(tǒng)放入現(xiàn)實中測試，在保證安全性的前提下投入市場供消費者使用。

類似特斯拉的做法，我們可以將人工智能應用于互聯(lián)網+尋路系統(tǒng)中，利用深度學習算法開發(fā)出一套經驗性的尋路算法。首先需要將多張道路交通地圖數字化拼接出一張涵蓋了盡可能多種道路情況的數字地圖，并在這張數字地圖上模擬出各種可能遇見的交通情況；其次程序設計者們需要開發(fā)出一個能夠用于路徑搜索的深度學習算法，賦予人工智能最基礎的學習、進化能力；之后再將人工智能程序置于數字地圖中進行最短路徑搜索模擬，在模擬中積累搜索經驗，使其具有應對多數道路交通情況組合的能力，獲得一套完善的經驗性搜索方法。這套經驗性方法可用于優(yōu)化互聯(lián)網+尋路系統(tǒng)中A Star算法的啟發(fā)式函數，也可直接將積累了足夠經驗的人工智能程序作為核心應用于互聯(lián)網+尋路系統(tǒng)中，使之利用模擬中得到的經驗處理實際問題。不過考慮到人工智能的完善相當困難、在實際問題中可能出現(xiàn)各種bug，不推薦在系統(tǒng)中直接使用人工智能。

3 結語

從游戲到地圖導航，尋路系統(tǒng)覆蓋了我們生活的方方面面，尋路問題，已然上升到一個新的高度，它可以是利用圖論思想求解金融模型、可以是計算錯綜復雜的航線網絡甚至可以是統(tǒng)籌整個城市的交通系統(tǒng)。物聯(lián)網技術拓寬了地圖導航尋路模型的廣度、發(fā)展出新的尋路問題，大數據技術為尋路系統(tǒng)提供了系統(tǒng)性的優(yōu)化、賦予其對尋路問題全新的處理方式。本文研究了以互聯(lián)網+思維改進地圖導航系統(tǒng)的關鍵技術，為大數據新時代導航系統(tǒng)升級提供理論參考。相信在不久的將來，隨著物聯(lián)網技術的普及，地圖導航系統(tǒng)將更加先進、實用，隨之而來的智能交通系統(tǒng)升級以及游戲開發(fā)等領域將擁有更加廣闊的前景。

參考文獻：

[1] 陳懷民，方泰淙，段曉軍.基于骨架提取的飛行器航跡實時重規(guī)劃法[J].現(xiàn)代電子技術，2018，41（16）：127-131.

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

[3] 黃梅.物聯(lián)網的結構特征研究及系統(tǒng)管理方法[J].信息技術，2018，（11）：168-172.

[4] 陳可睿.物聯(lián)網的關鍵技術研究及其應用[J].電子世界，2018（16）：16-18.

[5] 何文樂.融合物聯(lián)網智慧校園安防系統(tǒng)優(yōu)化設計[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*算法的移動機器人最短路徑規(guī)劃[J]，計算機應用， 2018，38（5）：1523-1526.

[10] 李澤文，唐平，曾祥君，等.基于Dijkstra算法的電網故障行波定位方法[J].電力系統(tǒng)自動化，2018（18）：162-168.

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

[12] 來學.兩種不同貪心算法在求解TSP問題中的應用和比較[J].河北北方學院學報（自然科學版）， 2018，34（7）：34-37.

【通聯(lián)編輯：代影】