中国图象图形学报A
中國圖象圖形學報A
중국도상도형학보A
JOURNAL OF IMAGE AND GRAPHICS
2010年
5期
802-807
,共6页
路径规划%A~*算法%均衡控制%智能符号回归
路徑規劃%A~*算法%均衡控製%智能符號迴歸
로경규화%A~*산법%균형공제%지능부호회귀
route planning%A~* algorithm%trade-off control%intelligent symbolic regression
随着地图网站和在线导航系统的普及,多用户网络并发出行信息查询服务的需求日益增长.如何满足多用户并发路径查询效率需求,同时又使得路径查询精度可控,是网络地理信息服务的瓶颈技术问题.本文提出了一种多用户并发路径查询精度效率均衡控制方法,利用系统抽样和智能符号回归技术,根据动态变化的在线路径查询用户规模和系统响应效率容忍阈值,在经典的路径查询A~*启发式算法基础上,根据大样本确定的路径查询严密算法和对应启发式算法得到的系统耗时比和精度比,实时自动确定启发式路径查询启发因子权重,有效平衡多用户并发路径查询的响应效率和精度损失,自适应地控制路径查询算法的精度和效率之间的平衡,在精度预先可控的前提下,最大限度地提升多用户并发路径查询效率,缩短用户的路径查询等待时间.
隨著地圖網站和在線導航繫統的普及,多用戶網絡併髮齣行信息查詢服務的需求日益增長.如何滿足多用戶併髮路徑查詢效率需求,同時又使得路徑查詢精度可控,是網絡地理信息服務的瓶頸技術問題.本文提齣瞭一種多用戶併髮路徑查詢精度效率均衡控製方法,利用繫統抽樣和智能符號迴歸技術,根據動態變化的在線路徑查詢用戶規模和繫統響應效率容忍閾值,在經典的路徑查詢A~*啟髮式算法基礎上,根據大樣本確定的路徑查詢嚴密算法和對應啟髮式算法得到的繫統耗時比和精度比,實時自動確定啟髮式路徑查詢啟髮因子權重,有效平衡多用戶併髮路徑查詢的響應效率和精度損失,自適應地控製路徑查詢算法的精度和效率之間的平衡,在精度預先可控的前提下,最大限度地提升多用戶併髮路徑查詢效率,縮短用戶的路徑查詢等待時間.
수착지도망참화재선도항계통적보급,다용호망락병발출행신식사순복무적수구일익증장.여하만족다용호병발로경사순효솔수구,동시우사득로경사순정도가공,시망락지리신식복무적병경기술문제.본문제출료일충다용호병발로경사순정도효솔균형공제방법,이용계통추양화지능부호회귀기술,근거동태변화적재선로경사순용호규모화계통향응효솔용인역치,재경전적로경사순A~*계발식산법기출상,근거대양본학정적로경사순엄밀산법화대응계발식산법득도적계통모시비화정도비,실시자동학정계발식로경사순계발인자권중,유효평형다용호병발로경사순적향응효솔화정도손실,자괄응지공제로경사순산법적정도화효솔지간적평형,재정도예선가공적전제하,최대한도지제승다용호병발로경사순효솔,축단용호적로경사순등대시간.
With the widespread use of map websites and on-line navigation systems,the need for multi-user concurrent queries for travel information is ever-increasing.In such a case,a bottleneck problem is how to improve the efficiencies of the multi-user concurrent path queries as much as possible,with only a controllable,as little as possible loss of the precisions of the query results.In this paper,an efficiency/accuracy trade-off control approach for the A~* heuristic shortest path algorithm is presented,which fits a curve function of the heuristic factor,the efficiency and the accuracy with large samples,by the techniques of systematic sampling and intelligent symbolic regression.The efficiency and the accuracy of the A~* algorithm are measured by the comparison with the Dijkstra exact algorithm.Through the use of the derived trade-off control model,the effective heuristic factor can be automatically determined with the input of the on-line user number and the required path accuracy,and as a result,the service response time for each user is much shortened.