g*******y
发帖数: 2114 | 1 感觉地图那么大，肯定不会都load到内存里面
要算最短路径（或者最快路径）
都是怎么算的啊
我知道两点最短路径的算法，比如A*
但是直接在gps上算会很慢吧
除非像google map那样放在服务器上算
可是现在的gps算的都很快啊，包括rerouting也很快
当然算法优劣还是不同，iguidance算的就不如garmin XT合理，根据我的经验看
但是基本算法应该是怎么样子的呢？ |
A*****s
发帖数: 13748 | 2 学学图论就知道了
基本模型就是点和边，边有不同的权，然后找最短路
【在 g*******y 的大作中提到】
: 感觉地图那么大，肯定不会都load到内存里面
: 要算最短路径（或者最快路径）
: 都是怎么算的啊
: 我知道两点最短路径的算法，比如A*
: 但是直接在gps上算会很慢吧
: 除非像google map那样放在服务器上算
: 可是现在的gps算的都很快啊，包括rerouting也很快
: 当然算法优劣还是不同，iguidance算的就不如garmin XT合理，根据我的经验看
: 但是基本算法应该是怎么样子的呢？
|
t*********u
发帖数: 26311 | 3 distributed 的 最短路径
【在 g*******y 的大作中提到】
: 感觉地图那么大，肯定不会都load到内存里面
: 要算最短路径（或者最快路径）
: 都是怎么算的啊
: 我知道两点最短路径的算法，比如A*
: 但是直接在gps上算会很慢吧
: 除非像google map那样放在服务器上算
: 可是现在的gps算的都很快啊，包括rerouting也很快
: 当然算法优劣还是不同，iguidance算的就不如garmin XT合理，根据我的经验看
: 但是基本算法应该是怎么样子的呢？
|
g*******y
发帖数: 2114 | 4 这个俺知道
但是手机上和电脑上不一样啊
load到内存的节点数是有限的
因为很多手机内存有限
【在 A*****s 的大作中提到】
: 学学图论就知道了
: 基本模型就是点和边，边有不同的权，然后找最短路
|
d*********g
发帖数: 2906 | 5 在GPS routing的不同阶段是用不同的网络的。
例如从旧金山的一个地址到纽约。首先用Interstate的网络（一共就几十条，只有几百
个junction）来routing。然后再route在local从起点到去Interstate的路，在这个过
程中也是先找最高等级的路，从state freeway到major express way到local street。
这个过程有点像递归算法。
等级越高的路网络越简单，覆盖范围越大；等级越低的路网络越复杂，覆盖范围也越小
。用这种分阶段用不同的网络来routing的方式使得计算复杂度成指数级下降。
在专业的GIS软件中也可以不管路的等级一视同仁的来routing，这样能保证真正的距离
最优（但远远不是时间最优）。即便是一个小州，公路的网络相对简单，在我的8 core
XEON CPU电脑上，任意两个点的routing要花5、6分钟左右。 |
g*******y
发帖数: 2114 | 6 en 这就明白很多了
谢谢
core
【在 d*********g 的大作中提到】
: 在GPS routing的不同阶段是用不同的网络的。
: 例如从旧金山的一个地址到纽约。首先用Interstate的网络（一共就几十条，只有几百
: 个junction）来routing。然后再route在local从起点到去Interstate的路，在这个过
: 程中也是先找最高等级的路，从state freeway到major express way到local street。
: 这个过程有点像递归算法。
: 等级越高的路网络越简单，覆盖范围越大；等级越低的路网络越复杂，覆盖范围也越小
: 。用这种分阶段用不同的网络来routing的方式使得计算复杂度成指数级下降。
: 在专业的GIS软件中也可以不管路的等级一视同仁的来routing，这样能保证真正的距离
: 最优（但远远不是时间最优）。即便是一个小州，公路的网络相对简单，在我的8 core
: XEON CPU电脑上，任意两个点的routing要花5、6分钟左右。
|
l*****e
发帖数: 16384 | |
