Tom*_*Tom 2 java artificial-intelligence dijkstra path-finding graph-algorithm
我在这里询问了一个最短路径算法: 2D航路点寻路:WP的组合从curLocation到targetLocation
(要了解我的情况,请阅读该问题以及此问题.)
似乎Dijkstra最短路径算法能够做到我需要的.但是,我的路线图中有大约500到1000个节点.
到目前为止,我所看到的实现将节点数限制在50以下.我的问题是:我是否应该使用Dijkstra最短路径算法,还是替代？Java中是否有任何实现？
直到你尝试过,你才知道.
1000个节点并不是那么多.Dijkstra的算法在边缘数量上具有线性复杂度,并且边缘数量在节点数量上最差二次方.根据您对图表的描述,很难说出有多少边缘,但即使是完整的1.000.000也不是很大.
主要问题是您使用优先级队列正确实现它.
编辑:Russell&Norvig,第2版,描述了第3章和第4章中的一组通用搜索算法.他们称之为统一成本图搜索本质上是Dijkstra的算法.如果您按照他们的说明操作,则可以在需要时将算法扩展到A*搜索.
| 归档时间： |
|
| 查看次数： |
3091 次 |
| 最近记录： |