摘要
在室内复杂停车场的路径规划问题上,许多方法使用了单源最短路径的典型算法Dijkstra算法对最短路径进行规划,但该算法需要花费大量时间和空间来计算和存储与最终路径无关节点.为了提高算法效率,通过把地图中所有的结点进行顶点归一、区域集合划分以及区域编号排序等策略,大大提高了算法运行效率.实验显示,在随机对某结点目标进行最短路径搜索时,搜索时间可以缩短80.8%到98.9%,大大减少了时间复杂度和空间复杂度.
On the problem of path scheduling in a complex indoor park, many approaches use the classical algorithm, Dijkstra algorithm, in single source shortest path planning. However, this al- gorithm costs too much time and amounts of memories to calculate and store the nodes which are en- tirely unrelated to the final path. In order to solve the problem, it successfully improves the efficiency of the algorithm through strategies of putting all nodes to normalized vertices, doing region segmenta- tion and sorting with region numbering. The experiments show that when performing our shortest path search for a random target node, the search time can be reduced to 80. 8% to 98. 9%, sing the time complexity and space complexity. greatly decrea-
出处
《福建师范大学学报（自然科学版）》
CAS
CSCD
北大核心
2017年第3期13-18,共6页
Journal of Fujian Normal University：Natural Science Edition
基金
福建省教育厅资助项目(JAT160670)
