基于A-star算法的地圖查詢系統的設計與實現

劉宏魁

摘要 在對A-star算法展開分析的基礎上，本文采用該算法設計了一種地圖查詢系統。從系統實現效果來看，路徑查找準確率可以達到100%，能夠滿足實際應用需求。

【關鍵詞】A-star算法 地圖查詢系統 路徑搜索

在日常出行中，人們需要依靠地圖查詢系統進行地理位置信息的查詢，從而確定當前位置到目的地的距離，選擇適合的路徑。在這一背景下，各種地圖查詢系統得到了開發和應用。本文采用A-star算法實現地圖查詢系統的開發，能實現位置信息的準確快速搜索，很好的完成地圖查詢。

1 A-star算法分析

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

2 基于A-star算法的地圖查詢系統設計與實現

2.1 系統結構設計

采用A-star算法進行地圖查詢系統設計，需要采用ARCIS軟件實現地理數據信息矢量化處理，完成系統需要數據的提取。采用Browser/Service結構，則能完成數據信息發布平臺設計。軟件平臺使用AutodeskmapGuide，可以利用HTML+JavaScript語言完成用戶界面編寫。系統服務器端采用ASP.NET+AJAX技術進行應用程序的編寫，并利用SQL Server數據庫進行請求的發送，同時實現數據輸入，向用戶進行數據反饋。采用Autodeskmap Guide Server地圖服務器，可以進行地圖數據的提供，并實現數據顯示。在分布式系統環境中運行，系統客戶端可以為用戶提供實現GIS應用的瀏覽器。

2.2 系統功能模塊

從系統功能模塊設計上來看，系統包含用戶管理功能模塊，用戶可以利用該模塊進行系統注冊和登錄，進行信息編輯。而系統用戶包含管理員和普通用戶，擁有各自的權限。系統管理員可以通過服務器實現系統登錄，進行系統運行管理。用戶可以通過客戶端進行系統登錄，進行地圖查詢。系統地圖查詢功能模塊可以實現地圖縮放、拖動，并對地圖標注的信息進行查詢。用戶利用該模塊，可以進行地圖上標注的修改，也能用鼠標進行窗口內任意兩點最短路徑量算。使用系統提供的Web瀏覽器，用戶可以進行文字信息、地理位置等各種形式的檢索查詢，并通過選擇地圖對象獲得相關信息報告。

2.3 系統數據庫設計

在設計系統數據庫時，考慮到地圖區域較為復雜，還要合理選擇數據結構形式，從而實現相關信息的合理組織。根據地理位置信息，可以進行地圖區域劃分，并根據地域邊界位置信息確定同區域鄰接關系。采用該種數據結構表現方式，可以實現定點坐標的分開存放，使系統冗余得到減少，以免地圖區域表示受地圖縮放比例變換的影響。此外，采用數組鏈表結構，也能提供區域邊界判定邏輯，滿足系統功能設計要求。結合這些要求，還要采用SQL Server數據庫進行各種數據的存儲，利用JDBC實現數據庫訪問。通過將數據源連接至數據庫上，則能進行用戶所在地點查詢，完成對應數據的調用，繼而實現地圖查詢操作。在數據庫中，包含用戶表User、標準信息表tag、關系表BBS等數據表，用于存儲編號、名稱、信息等屬性信息，能夠實現不同類型數據的存儲和管理，從而為系統數據信息調用提供便利。

2.4 系統功能實現

從系統功能實現上來看，系統以STM32微控制器為核心控制器。系統初始化后，會先對數據庫中地圖數據進行讀取，并在LCD上進行地圖顯示。采用系統查詢路徑時，系統則能實現A-star算法調用，賦予特定地點參數及權值，完成兩點間可行路線中最優路徑查找，通過調用UCGUI API函數進行路徑顯示。經過調試，采用A-Star算法設計的地圖查詢系統可以維持穩定運行，并實現最短路徑準確查找和流暢呈現，路徑查找準確率達100%。

3 結論

采用A-Star算法進行地圖查詢系統的設計，可以及時完成地圖查詢功能的刷新，為用戶提供動態的界面，實現優選路徑信息的查詢。采用該系統，可以達到loO%路徑查找準確率，提供強有力的數據服務。因此相信在地圖查詢方面，該種系統可以獲得較好的應用前景。

參考文獻

[1]張儒俠，付姍姍，基于Android智能手機的志愿服務信息查詢系統設計[J].首都師范大學學報（自然科學版）， 2016， 37 （03）： 63-70.