Current Issue Cover

周亮,陆锋,郑年波(中国科学院地理科学与资源研究所 资源与环境信息系统国家重点实验室, 北京 100101)

摘 要
A Trade-off Control Approach for A* Algorithm Based on Intelligent Symbolic Regression

ZHOU Liang,LU Feng,ZHENG Nianbo(LREIS, Institute of Geographic Sciences and Natural Resources Research, CAS, Beijing 100101)

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.