摘要
提出了一种基于连接特性的路径规划算法 ,并针对城市交通网络的路径规划进行算法的验证和应用研究。该算法利用网络的连接特性 ,求取最少连接层数的路径作为较优的全局路径 ,这样获得的全局路径不是加权最少路径。为了提高算法精度 ,在权较大的两点之间插入新的结点 ,这样获得的路径是全局最优路径的可信度很高。这种算法的时间复杂度是线性的 ,即O(N) ,而且通过适当增大模型 ,可以控制路径规划的精度 ,并提出了控制精度的两个指数。经过对城市交通网络的具体例子的计算及分析 ,表明该方法快速、可靠及有效。
Proposes a connectivity-based method to solve the path planning and applies the method to the path planning for the city traffic network. With the method, it is regarded as the best weighted path whose number of connective layers between two nodes is minimal, the best path isn't the global best weighted path. To enhance the path searching quality, the edge, whose weight is big, is split into several edges, and some nodes are inserted. As a result, the obtained path is highly confidently the global best path or is very near to the global best path. The time complexity of the method is linear, the searching for path planning is conducted in the global, and the precise can be controlled by two Indexes, which can be used to determine how many nodes should be inserted. The application to the city transportation network demonstrates that the method is efficient and reliable.
出处
《计算机与现代化》
2002年第6期5-11,共7页
Computer and Modernization
