366,2008-02-02 13:30:48,116.45353,39.90732
366,2008-02-02 13:30:53,116.45348,39.90729
366,2008-02-02 13:30:58,116.45334,39.90725
366,2008-02-02 13:31:03,116.4533,39.90722
366,2008-02-02 13:31:08,116.45327,39.90722
366,2008-02-02 13:31:13,116.4532,39.90725
366,2008-02-02 13:31:18,116.45309,39.9076
366,2008-02-02 13:31:23,116.453,39.9077
含义是：
车辆编号，日期，经度，纬度
上一段节选则是卫星在一段时间内，跟踪编号366的车辆，记录下它的经纬度和此刻时间。
现在掌握的数据有 上万辆车，每辆车有上 十万条记录。
假设数据已经足够大，记录了所有车辆，且记录的车辆都是在道路上奔跑的。也就是说，所有有过记录的经纬度都是可以到达的（马路），而因为数据足够大，所以可以认为所有可以到达的点都已覆盖到。（就是说所有出现过的点共同组成了地图）
现在在地图上指定一起点，一终点，求 时间最短的路径
这也就是说要综合考虑路程长短和 预计的拥堵状况
这是我们算法设计老师给出的一个课程设计题目，不要求非常具体的实现，重点是给出可行的算法。
目前简直毫无头绪，希望大家能一起讨论下，提供一些思路或是启发，万分感谢
5 个解决方案
#1
时间粒度太粗，5分钟可能转了好几个弯，根本判断不出走了什么道路。
要么在地图上划方格，统计某个方格进入到离开的平均时间差作为交通状况。
最优路径就简化为走哪些方格所用的时间最少的路径——这样只能有一个大致方向，还是不知道该走那条路。
要么在地图上划方格，统计某个方格进入到离开的平均时间差作为交通状况。
最优路径就简化为走哪些方格所用的时间最少的路径——这样只能有一个大致方向，还是不知道该走那条路。
#2
时间粒度不粗啊，是每5秒不是5分钟哦
#3
我自己目前有了一些大致的方向
首先是生成地图，而地图我只关心拐点（路口）
可以用向量法算出所有的拐点，比如偏角大于40度的都认为是拐点
然后要合并所有重复的拐点，例如，任一拐点30米半径内的所有点，取这些点的中心作为合并点
但是合并这步具体用怎样的算法还没想好，不知怎样的速度快点
所有拐点生成后，路径就分三部分了：起点到第一个拐点，第一个拐点到第n个拐点，第n个拐点到终点
然而要考虑拥堵状况的最优路径。。还是不知道怎么弄
谢谢Tiger_Zhao咯
首先是生成地图，而地图我只关心拐点（路口）
可以用向量法算出所有的拐点，比如偏角大于40度的都认为是拐点
然后要合并所有重复的拐点，例如，任一拐点30米半径内的所有点，取这些点的中心作为合并点
但是合并这步具体用怎样的算法还没想好，不知怎样的速度快点
所有拐点生成后，路径就分三部分了：起点到第一个拐点，第一个拐点到第n个拐点，第n个拐点到终点
然而要考虑拥堵状况的最优路径。。还是不知道怎么弄
谢谢Tiger_Zhao咯
#4
有了拐点ABC之后还要生成有向路径。
AB、BA要分别统计权重（平均用时）。
接下来就是有向图中的最优路径了。
AB、BA要分别统计权重（平均用时）。
接下来就是有向图中的最优路径了。
#5
366,2008-02-02 13:30:58,116.45334,39.90725
366,2008-02-02 13:31:03,116.4533,39.90722
366,2008-02-02 13:31:08,116.45327,39.90722
366,2008-02-02 13:31:13,116.4532,39.90725
这几个貌似拐点。记录足够的话，可以细化维度。比如有21,20,21等。或者就要以20为中心点。2为半径。
红绿灯情况数据可能有标识。
堵车情况可能速度变缓。数据增加。比如22到25中一共有20000条记录。
最后构建最短路径。
366,2008-02-02 13:31:03,116.4533,39.90722
366,2008-02-02 13:31:08,116.45327,39.90722
366,2008-02-02 13:31:13,116.4532,39.90725
这几个貌似拐点。记录足够的话，可以细化维度。比如有21,20,21等。或者就要以20为中心点。2为半径。
红绿灯情况数据可能有标识。
堵车情况可能速度变缓。数据增加。比如22到25中一共有20000条记录。
最后构建最短路径。
#1
时间粒度太粗，5分钟可能转了好几个弯，根本判断不出走了什么道路。
要么在地图上划方格，统计某个方格进入到离开的平均时间差作为交通状况。
最优路径就简化为走哪些方格所用的时间最少的路径——这样只能有一个大致方向，还是不知道该走那条路。
要么在地图上划方格，统计某个方格进入到离开的平均时间差作为交通状况。
最优路径就简化为走哪些方格所用的时间最少的路径——这样只能有一个大致方向，还是不知道该走那条路。
#2
时间粒度不粗啊，是每5秒不是5分钟哦
#3
我自己目前有了一些大致的方向
首先是生成地图，而地图我只关心拐点（路口）
可以用向量法算出所有的拐点，比如偏角大于40度的都认为是拐点
然后要合并所有重复的拐点，例如，任一拐点30米半径内的所有点，取这些点的中心作为合并点
但是合并这步具体用怎样的算法还没想好，不知怎样的速度快点
所有拐点生成后，路径就分三部分了：起点到第一个拐点，第一个拐点到第n个拐点，第n个拐点到终点
然而要考虑拥堵状况的最优路径。。还是不知道怎么弄
谢谢Tiger_Zhao咯
首先是生成地图，而地图我只关心拐点（路口）
可以用向量法算出所有的拐点，比如偏角大于40度的都认为是拐点
然后要合并所有重复的拐点，例如，任一拐点30米半径内的所有点，取这些点的中心作为合并点
但是合并这步具体用怎样的算法还没想好，不知怎样的速度快点
所有拐点生成后，路径就分三部分了：起点到第一个拐点，第一个拐点到第n个拐点，第n个拐点到终点
然而要考虑拥堵状况的最优路径。。还是不知道怎么弄
谢谢Tiger_Zhao咯
#4
有了拐点ABC之后还要生成有向路径。
AB、BA要分别统计权重（平均用时）。
接下来就是有向图中的最优路径了。
AB、BA要分别统计权重（平均用时）。
接下来就是有向图中的最优路径了。
#5
366,2008-02-02 13:30:58,116.45334,39.90725
366,2008-02-02 13:31:03,116.4533,39.90722
366,2008-02-02 13:31:08,116.45327,39.90722
366,2008-02-02 13:31:13,116.4532,39.90725
这几个貌似拐点。记录足够的话，可以细化维度。比如有21,20,21等。或者就要以20为中心点。2为半径。
红绿灯情况数据可能有标识。
堵车情况可能速度变缓。数据增加。比如22到25中一共有20000条记录。
最后构建最短路径。
366,2008-02-02 13:31:03,116.4533,39.90722
366,2008-02-02 13:31:08,116.45327,39.90722
366,2008-02-02 13:31:13,116.4532,39.90725
这几个貌似拐点。记录足够的话，可以细化维度。比如有21,20,21等。或者就要以20为中心点。2为半径。
红绿灯情况数据可能有标识。
堵车情况可能速度变缓。数据增加。比如22到25中一共有20000条记录。
最后构建最短路径。