沈煜航 李家胤 李甜

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

關(guān)鍵詞：互聯(lián)網(wǎng)+；地圖導(dǎo)航；尋路模型；物聯(lián)網(wǎng)； 貪心算法

中圖分類號：TP393.4， TP319 文獻(xiàn)標(biāo)識碼：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

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

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

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

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

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

2 基于互聯(lián)網(wǎng)+的地圖導(dǎo)航尋路算法改進(jìn)

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

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

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

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

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

2.1.2 Floyd算法與“打表”思想

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

2.2 貪心算法[12]的改進(jìn)

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

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

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

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

2.3 預(yù)處理算法的改進(jìn)

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

2.4 基于深度學(xué)習(xí)的經(jīng)驗(yàn)性尋路算法的應(yīng)用

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

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

3 結(jié)語

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

參考文獻(xiàn)：

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

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

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

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

[5] 何文樂.融合物聯(lián)網(wǎng)智慧校園安防系統(tǒng)優(yōu)化設(shè)計(jì)[J]，信息技術(shù)，2018，（11）：139-142+147.

[6] 黃美靈，陸百川.考慮交叉口延誤的城市道路最短路徑[J]，重慶交通大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2009，28（6）：1060-1063.

[7] 曾慶福，王孟平.基于MATLAB編程Dijkstra算法的消防救援最佳路線研究[J].武警學(xué)院學(xué)報(bào)，2018，33（6）：9-13.

[8] 陳昊，寧紅云.基于集合運(yùn)算的最短路徑搜索算法[J].計(jì)算機(jī)工程，2007（20）：199-200+203.

[9] 王維，裴東，馮璋.改進(jìn)A*算法的移動機(jī)器人最短路徑規(guī)劃[J]，計(jì)算機(jī)應(yīng)用， 2018，38（5）：1523-1526.

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

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

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

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