摘要
通过对经典Dijkstra算法和启发式搜索的分枝算法各自的不足之处进行分析,并分别对它们进行了改进。利用VC编程进行实验,实验表明:改进的Dijkstra算法可以减少大量的无关节点的计算,使其时间复杂性得到降低,同时运算空间开销也减少;改进的分枝算法则可以提高搜索到最优路径的成功率。
Based on the analysis of the tradition Dijkstra algorithm＇s and Branch-and-bound search algorithm, an improved algorithm is given. The experiment in the VC programming shows that the improved Dijkstra algorithm can decrease the computing of uncorrelated nodes and enhances the calculation efficiency and the improved algorithm can find the more optimum path.
出处
《地矿测绘》
2008年第3期12-14,17,共4页
Surveying and Mapping of Geology and Mineral Resources
关键词
路径规划
GIS
空间分析
DIJKSTRA算法
分枝算法
optimum path planning
Geographic branching algorithm Information System （GIS）
spatial analysis
Dijkstra algorithm
