劉宏魁

摘要 在對(duì)A-star算法展開(kāi)分析的基礎(chǔ)上，本文采用該算法設(shè)計(jì)了一種地圖查詢(xún)系統(tǒng)。從系統(tǒng)實(shí)現(xiàn)效果來(lái)看，路徑查找準(zhǔn)確率可以達(dá)到100%，能夠滿(mǎn)足實(shí)際應(yīng)用需求。

【關(guān)鍵詞】A-star算法 地圖查詢(xún)系統(tǒng) 路徑搜索

在日常出行中，人們需要依靠地圖查詢(xún)系統(tǒng)進(jìn)行地理位置信息的查詢(xún)，從而確定當(dāng)前位置到目的地的距離，選擇適合的路徑。在這一背景下，各種地圖查詢(xún)系統(tǒng)得到了開(kāi)發(fā)和應(yīng)用。本文采用A-star算法實(shí)現(xiàn)地圖查詢(xún)系統(tǒng)的開(kāi)發(fā)，能實(shí)現(xiàn)位置信息的準(zhǔn)確快速搜索，很好的完成地圖查詢(xún)。

1 A-star算法分析

在人工智能中，A-star算法為典型啟發(fā)式搜索算法，可以用于實(shí)現(xiàn)靜態(tài)路網(wǎng)中最短路徑的有效求解。采用A-star算法，可以對(duì)估價(jià)函數(shù)進(jìn)行定義和描述，得到啟發(fā)能力較強(qiáng)的搜索算法。在實(shí)際應(yīng)用該算法時(shí)，通過(guò)對(duì)需要安裝地圖數(shù)據(jù)進(jìn)行處理，完成地圖圖片坐標(biāo)平面規(guī)劃，并將多路徑節(jié)點(diǎn)坐標(biāo)值進(jìn)行標(biāo)注，然后進(jìn)行結(jié)構(gòu)體變量記錄，則能確定結(jié)構(gòu)體MapPoint中節(jié)點(diǎn)坐標(biāo)值、周?chē)?jié)點(diǎn)號(hào)等元素。采用A-star算法，對(duì)評(píng)價(jià)函數(shù)f（n）=g（h）+h（n）進(jìn)行搜索，可以確定初始節(jié)點(diǎn)到n節(jié)點(diǎn)的路徑散耗g（n），即節(jié)點(diǎn)到該點(diǎn)最短路徑路程。而h（n）為節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)最短路徑路程，需要合理選擇估價(jià)函數(shù)，才能得到最優(yōu)解。在h（n）不超出n到目標(biāo)節(jié)點(diǎn)距離實(shí)際值的情況下，擁有較多的搜索點(diǎn)，搜索范圍將較大，搜索效率也將較低，但是可以獲得最優(yōu)解。如果估計(jì)值比實(shí)際值要大，盡管搜索范圍得到了減小，可以快速完成搜索，但是不一定能獲得最優(yōu)解。在采用曼哈頓方法進(jìn)行估算時(shí)，還要利用結(jié)構(gòu)體AstarPoint對(duì)路徑中各節(jié)點(diǎn)的x、v坐標(biāo)值和各種函數(shù)值進(jìn)行記錄，并記錄結(jié)構(gòu)體指針類(lèi)型元素。

2 基于A-star算法的地圖查詢(xún)系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)

2.1 系統(tǒng)結(jié)構(gòu)設(shè)計(jì)

采用A-star算法進(jìn)行地圖查詢(xún)系統(tǒng)設(shè)計(jì)，需要采用ARCIS軟件實(shí)現(xiàn)地理數(shù)據(jù)信息矢量化處理，完成系統(tǒng)需要數(shù)據(jù)的提取。采用Browser/Service結(jié)構(gòu)，則能完成數(shù)據(jù)信息發(fā)布平臺(tái)設(shè)計(jì)。軟件平臺(tái)使用AutodeskmapGuide，可以利用HTML+JavaScript語(yǔ)言完成用戶(hù)界面編寫(xiě)。系統(tǒng)服務(wù)器端采用ASP.NET+AJAX技術(shù)進(jìn)行應(yīng)用程序的編寫(xiě)，并利用SQL Server數(shù)據(jù)庫(kù)進(jìn)行請(qǐng)求的發(fā)送，同時(shí)實(shí)現(xiàn)數(shù)據(jù)輸入，向用戶(hù)進(jìn)行數(shù)據(jù)反饋。采用Autodeskmap Guide Server地圖服務(wù)器，可以進(jìn)行地圖數(shù)據(jù)的提供，并實(shí)現(xiàn)數(shù)據(jù)顯示。在分布式系統(tǒng)環(huán)境中運(yùn)行，系統(tǒng)客戶(hù)端可以為用戶(hù)提供實(shí)現(xiàn)GIS應(yīng)用的瀏覽器。

2.2 系統(tǒng)功能模塊

從系統(tǒng)功能模塊設(shè)計(jì)上來(lái)看，系統(tǒng)包含用戶(hù)管理功能模塊，用戶(hù)可以利用該模塊進(jìn)行系統(tǒng)注冊(cè)和登錄，進(jìn)行信息編輯。而系統(tǒng)用戶(hù)包含管理員和普通用戶(hù)，擁有各自的權(quán)限。系統(tǒng)管理員可以通過(guò)服務(wù)器實(shí)現(xiàn)系統(tǒng)登錄，進(jìn)行系統(tǒng)運(yùn)行管理。用戶(hù)可以通過(guò)客戶(hù)端進(jìn)行系統(tǒng)登錄，進(jìn)行地圖查詢(xún)。系統(tǒng)地圖查詢(xún)功能模塊可以實(shí)現(xiàn)地圖縮放、拖動(dòng)，并對(duì)地圖標(biāo)注的信息進(jìn)行查詢(xún)。用戶(hù)利用該模塊，可以進(jìn)行地圖上標(biāo)注的修改，也能用鼠標(biāo)進(jìn)行窗口內(nèi)任意兩點(diǎn)最短路徑量算。使用系統(tǒng)提供的Web瀏覽器，用戶(hù)可以進(jìn)行文字信息、地理位置等各種形式的檢索查詢(xún)，并通過(guò)選擇地圖對(duì)象獲得相關(guān)信息報(bào)告。

2.3 系統(tǒng)數(shù)據(jù)庫(kù)設(shè)計(jì)

在設(shè)計(jì)系統(tǒng)數(shù)據(jù)庫(kù)時(shí)，考慮到地圖區(qū)域較為復(fù)雜，還要合理選擇數(shù)據(jù)結(jié)構(gòu)形式，從而實(shí)現(xiàn)相關(guān)信息的合理組織。根據(jù)地理位置信息，可以進(jìn)行地圖區(qū)域劃分，并根據(jù)地域邊界位置信息確定同區(qū)域鄰接關(guān)系。采用該種數(shù)據(jù)結(jié)構(gòu)表現(xiàn)方式，可以實(shí)現(xiàn)定點(diǎn)坐標(biāo)的分開(kāi)存放，使系統(tǒng)冗余得到減少，以免地圖區(qū)域表示受地圖縮放比例變換的影響。此外，采用數(shù)組鏈表結(jié)構(gòu)，也能提供區(qū)域邊界判定邏輯，滿(mǎn)足系統(tǒng)功能設(shè)計(jì)要求。結(jié)合這些要求，還要采用SQL Server數(shù)據(jù)庫(kù)進(jìn)行各種數(shù)據(jù)的存儲(chǔ)，利用JDBC實(shí)現(xiàn)數(shù)據(jù)庫(kù)訪(fǎng)問(wèn)。通過(guò)將數(shù)據(jù)源連接至數(shù)據(jù)庫(kù)上，則能進(jìn)行用戶(hù)所在地點(diǎn)查詢(xún)，完成對(duì)應(yīng)數(shù)據(jù)的調(diào)用，繼而實(shí)現(xiàn)地圖查詢(xún)操作。在數(shù)據(jù)庫(kù)中，包含用戶(hù)表User、標(biāo)準(zhǔn)信息表tag、關(guān)系表BBS等數(shù)據(jù)表，用于存儲(chǔ)編號(hào)、名稱(chēng)、信息等屬性信息，能夠?qū)崿F(xiàn)不同類(lèi)型數(shù)據(jù)的存儲(chǔ)和管理，從而為系統(tǒng)數(shù)據(jù)信息調(diào)用提供便利。

2.4 系統(tǒng)功能實(shí)現(xiàn)

從系統(tǒng)功能實(shí)現(xiàn)上來(lái)看，系統(tǒng)以STM32微控制器為核心控制器。系統(tǒng)初始化后，會(huì)先對(duì)數(shù)據(jù)庫(kù)中地圖數(shù)據(jù)進(jìn)行讀取，并在LCD上進(jìn)行地圖顯示。采用系統(tǒng)查詢(xún)路徑時(shí)，系統(tǒng)則能實(shí)現(xiàn)A-star算法調(diào)用，賦予特定地點(diǎn)參數(shù)及權(quán)值，完成兩點(diǎn)間可行路線(xiàn)中最優(yōu)路徑查找，通過(guò)調(diào)用UCGUI API函數(shù)進(jìn)行路徑顯示。經(jīng)過(guò)調(diào)試，采用A-Star算法設(shè)計(jì)的地圖查詢(xún)系統(tǒng)可以維持穩(wěn)定運(yùn)行，并實(shí)現(xiàn)最短路徑準(zhǔn)確查找和流暢呈現(xiàn)，路徑查找準(zhǔn)確率達(dá)100%。

3 結(jié)論

采用A-Star算法進(jìn)行地圖查詢(xún)系統(tǒng)的設(shè)計(jì)，可以及時(shí)完成地圖查詢(xún)功能的刷新，為用戶(hù)提供動(dòng)態(tài)的界面，實(shí)現(xiàn)優(yōu)選路徑信息的查詢(xún)。采用該系統(tǒng)，可以達(dá)到loO%路徑查找準(zhǔn)確率，提供強(qiáng)有力的數(shù)據(jù)服務(wù)。因此相信在地圖查詢(xún)方面，該種系統(tǒng)可以獲得較好的應(yīng)用前景。

參考文獻(xiàn)

[1]張儒俠，付姍姍，基于Android智能手機(jī)的志愿服務(wù)信息查詢(xún)系統(tǒng)設(shè)計(jì)[J].首都師范大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2016， 37 （03）： 63-70.