关于地图的一个可能功能的思考
今天是周末,我计划着先去理发,再去银行取钱,再去学校取包裹,然后再回来。
由于这三个地方不怎么在一个方向,就想计划一下。
打开地图看看都是告诉你两点之间怎么走最快,最短,最省时间等等。
那么我现在需要一天去做好几件事情,而且这些事情没有先后顺序,先做哪个都可以。
那么地图中有没有这个功能呢?
用户给出他/她想去的几个地方,优先权相同的。
然后地图可以计算出他/她怎么走最省时间。
首先假设我大西安的交通是如此的发达,不管是不是雾天都绝对不会有traffic jam,也不会有比总书记还大派头的领导来封路,更不会有不明身份的人在路上捣乱。
那么就很简单了。定位自己的点和任务点。给各个任务点所在的block中各个路段赋上权值。
然后用Dijkstra算法?那个是单源最短路径算法……
那么只有求出全局的最短路径,然后筛出含有各个任务点以及自己的点的一个子集?也不对,符合要求的路线也许根本不是全局最短路线。
用一下变了味儿的Floyd-Warshall算法……从自身点和各个任务点开始搜索的“Floyd-Warshall算法”。
呃……有没有大虾来给菜鸟释疑,该用啥算法最快捷?
还有,如果考虑真实情况,XX路段在XX时间容易堵车,XX路段封路,XX路段……再对这么多关键字进行一下各种排序,给出一个相当于现在两点之间“最快”,“最省钱”,“最短”,“不用换乘”之类的路线?
扯了这么多,也不知道这个多点最优路线的功能在现在的几家地图里有没有。或者有没有存在的必要?