地图的路由，la谷歌地图？
https://stackoverflow.com/questions/2798
-
08-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
我一直很感兴趣地图的路由，但我从来没有发现任何良好的介绍性(或甚至先进的！) 水平的教程。没有任何人有任何指针，提示，等等？
更新： 我主要是想找针对如何的一个地图系统实施的(数据结构、算法，等等)。
解决方案
看看 开放街道地图项目 怎么看这种事情正在解决在一个真正的免费软件项目使用仅有的用户提供和授权数据，并有一个 wiki含有的东西你可能会觉得有趣.
几年前的人参与其中很容易会，并回答了很多问题，我不得不这样我看不出有任何理由为什么他们仍然不是一个很好的一群。
其他提示
巴里Brumitt，其中一个工程师的谷歌地图的路线，查找功能，写了一篇文章的专题，可能会感兴趣：
道路更好的路径寻找 11/06/2007 03:47:00
A*实际上是远远更接近于生产射算法。它需要相当少一点的勘探相比，Dijikstra的原算法。
通过地图的路由，您意味着找到的最短路径沿着一条街道网络？
Dijkstra的最短路径算法是最有名的。维基百科已经不是一个坏的介绍: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
有一个Java程序在这里你可以看到它在行动： http://www.dgp.toronto.edu/people/JamesStewart/270/9798s/Laffra/DijkstraApplet.html 和谷歌引导你来源代码，在任何语言。
任何真正的执行产生驱动路线将包括相当一些数据在街道网络，介绍了成本与历的链接和节点的公路网络层次，平均速度，交叉的优先权、交通信号连接的，禁止实证明等。
而不是学习Api到每个地图服务提供商(如允许你搜索,Ymaps api)其良好的学习 Mapstraction
"Mapstraction是一个图书馆，提供了一个共同的API各种javascript映Api"
我会建议你去URL和学习的一般API。有良好的数额如何渡过。
从概念的角度来看，想象一下，删除石进入池塘和看涟漪。该路线将代表池塘和石你的位置开始。
当然算法会搜索的一些比例n^2路的距离n增加。你会把你的起始位置，并检查所有可用的路径从这一点。然后递归呼吁点结束这些路径等。
你可以提高性能，通过不双背道路，通过不重新检查路线的一点，如果它已被复盖并且通过放弃路径，考虑太久。
一种替代方法是使用蚂蚁信息素的方法，那里的蚂蚁爬行随机从一开始点，并留下气味线索，它建立了更多的蚂蚁交叉在一定的道路。如果你发送(足够)从蚂蚁的两点开始和结束点，那么最终的路径与最强烈的气味就是最短的。这是因为最短路径已经访问了多次在一定时间，鉴于蚂蚁走在一个统一的步伐。
编辑@Spikie
作为进一步解释如何实现的池塘算法的潜在数据结构所需要的是强调：
你会需要储存地图，作为一个网络。这简直是一组的 nodes 和 edges 他们之间。一个组 nodes 构成 route.一边加入两个节点(可能两者同样的节点)，并且具有关联的 cost 如 distance 或 time 穿越的边缘。一边可以么是双向的或单向的。或许最简单的只有单向的和双两种方式之间旅行的节点(即一个边缘，从A到B和一个不同B)。
通过举例的方式设想的三个火车站安排在一个等边三角形朝上。还有另外三个站中的每一个中间。边加入所有相邻站在一起，最终的图将有一个倒三角的坐在里面的大三角形。
标签节点开始从底左，左右并起来，作为A、B、C、D、E、F(F在上)。
假设边缘可以走在方向。每边都有一个费用为1公里。
Ok,因此我们希望路线底部从左到顶站F。有许多可能的路线，包括那些双重回自己的，例如ABCEBDEF.
我们有一个惯例说， NextNode, 那接受 node 和一个 cost 并呼吁本身为每个节点可以旅行。
显然，如果我们让这个程序运行，这最终会发现所有的路线，包括那些可能是无限的长度(例如ABABABAB等)。我们阻止这种情况的发生，通过检查对的 cost.每当我们参观一点还没有被访问之前，我们把两者的成本和节点我们来自反对该节点。如果一个节点已经访问过我们之前检查，对现有的成本，如果我们便宜，然后我们就更新的节点和进行(递归访问).如果我们更加昂贵，然后我们跳过这个节点。如果所有节点是跳过那么我们退出程序。
如果我们打我们的目标点然后我们就退出程序了。
这种方式的所有可行的路线检查，但至关重要的是只有那些与最低的成本。通过该过程结束时每个节点将具有最低的成本得到这一点，包括我们的目标的节点。
得到的路线，我们的工作向后从我们的目标的节点。由于我们存储节点我们来自与成本，我们只是随后建立的路线。我们的例子，我们会喜欢的东西:
节点一(总额)的费用0-从节点没有
B节点成本的1-从一个节点
节点C-2-从B节点
节D-1，从一个节点
E节点-成本2-从节D/费用2-从B节点(这是一个例外，因为有平等的成本)
节点F-费用2-从D节点
所以最短的路线是ADF.
从我的经验在这一领域工作，*会的工作非常好。它是(如上所述)的速度比Dijkstra的算法，但是仍然很简单的一个通常称职的程序以实现和了解。
建筑的线路网络是最难的部分，但可以分解成一系列的简单步骤：得到所有道路；排序分为令；使团的相同点上不同的道路进入交叉点(节点);添加弧在两个方向上在节点连接(或只在一个方向的一种方式路)。
A*算法本身是 好的记录上的维基百科.关键的地方以优化选择的的最好的节点开列表，因为你需要一个高效的优先权排队。如果你使用C++可以使用STL符的适配器。
定制的算法途径在不同的部件的网络(例如行人、汽车、公共运输，等等。) 的赞成票速度，距离或者其他的准则是相当容易的。你做的是，通过编写过滤器以控制的路段都是可用的，当建立网络，其重量分配给每一个。
另一个想法出现在我有关的费用每历，但是将增加时间和处理所需要的电力来计算。
例如： 有3种方式我可以(在那里我活着)去从A点到B，根据google地图.生产单位提供这3个路径 Quickest 路线计算。之后穿过这些线路很多次，平均(显然会有误差，根据一天的时间、数量的咖啡等)， 我觉得算法可以考虑的数量弯曲的道路，为高级别的准确性， 例如 笔直的公路的1英里会更快于1公里的道路急转弯在这.不是一个实用的建议，但当然我的使用提高，结果设定的，我每天上下班。
