A Trade-off Control Approach for A* Algorithm Based on Intelligent Symbolic Regression
基于智能符号回归的路径规划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.