最短路径的应用是GIS中的基础。而最短路径的基础又是dijkstra算法。传统的dijkstra算法有一个最大的缺点，那就是用邻接矩阵，O（n*n）的代价是难以想象的，而且即使在dotNet编程环境下也无法构造出超过20000*20000的数组，这就是一些初学者的瓶颈。
对dijkstra算法的改进有多种方法，根据我的总结现有的优化方式有以下几种：1、用邻接表代替邻接矩阵。2、对需要搜索的点进行排序，以加快查找的速度。3、利用像a*算法的估价函数减少搜索的范围。4、双向搜索，不是传统的从起点到终点，而是起点和终点同时进行（个人认为这种方法比较适合两点间的最短路径）。5、估价函数（A*算法）。当然上次还看到了一种更土的做法：计算出图中所有点的最大出度，然后以此构造邻接矩阵（的确可以省不少空间，不过感觉就像在骗钱）。
现在总结一下。邻接表和排序是一定必须的，因为可以大量节约空间和时间上的开销。估价函数方面似乎很大的局限性，毕竟我们用来做最短路径的应用时会考虑到时间、空间以及其他一些因素，目前看到的估价函数也都是以欧氏距离为基础的，所以无法达到最佳效果；我暂时没有考虑这种有估价函数的方法，因为我觉得估价函数加入后，如果无法找到目标，极端的情况下必将遍历整个图，这也是个浪费。双向搜索似乎是一个不错的方法，可惜我也没有具体验证过到底能令效率提高多少。
不知大家是否记得传统dijkstra算法的做法，用两层for循环遍历图中所有节点，将找到最短路径的节点进行标记，并实时修改distance数组中的值，直到找到目标后结束循环。我这里要提出的思路同样基于dijkstra算法，但是最大的区别是我不像大多数实现那样在一开始就规定了扫描的次数。通常的做法使用一个排序的集合容纳需要稍描的节点，并在程序中动态修改这个集合，如果发现需要扫描的点则将其加入集合；每次取出集合第一位的值（权值最小的），扫描过之后则从集合中移除。扫描的结束条件是找到到所有终点的最短路径或者集合中没有任何点存在。为了防止形成回路和避免顺序集合的插入次数增多，标记法也是有必要的。
在另一帖里我说过，对PII或PIII的机子实现20000节点以上的路网可以在2~3秒内算出贯穿全程的两点间的最短路径表示怀疑，希望能有高手给出个实例看看，当然能有代码是最好的。
以下是我刚才所说的思路基于mapXtreme2004简单实现后的测试数据。
我的机器配置是PM1.5G，512M内存，32M显存。测试结果。1、基于福建省路网的测试：17111条道路，13701个节点，从北向南贯穿的最短路径计算平均时间在2500毫秒左右。2、基于全国路网的测试：27877条道路，22319个节点，计算从右上角到左下角贯穿的最短路径平均时间在6300毫秒左右。
最终结论，以前可能有朋友见过我发的帖子，有说过用Hashtable来实现。的确，我现在这个测试程序中也用了Hashtable。Hashtable的确能省一些事情，但是随之而来的是类型转换以及空间上的花费。如果将Hashtable用其他方法替换相信是完全可以提高效率的。
没有评论:
发表评论