分段路径寻优算法研究及实现

Algorithm for Searching Shortest Path Piecewise and Its Implementation

传统的路径寻优只考虑了起点和终点,不能满足一些用户的实际需求;研究了一类带有必经节点序列和避开节点序列的路径寻优问题。首先将必经节点序列进行有序调整,然后根据避开节点序列和调整后的必经节点序列进行分段路径寻优,最后生成满足用户要求的最短路径。将其应用到面向手机用户的路径诱导业务中,取得了良好的效果。

One kind of special shortest path search algorithm is studied in order to obtain the shortest path with some constraint conditions, Some locations should go and some locations should be avoid are considered. First, the locations should go are ordered according to the direction of shortest path; then shortest path is searched piecewise according to the locations should go, at the same time the location should be avoided are considered; at last, the shortest path is accomplished by connecting the piecewise shortest paths.