我一直对Map Routing感兴趣，但是我从来没有在它上面找到任何好的入门(甚至是高级！)级别的教程。有人有任何指针，提示等吗？

更新：我主要是在寻找有关如何实现地图系统(数据结构，算法等)的指针。

解决方案

回答

看看开放的街道地图项目，看看如何在仅使用用户提供和许可的数据的真正自由软件项目中解决此类问题，并拥有一个包含我们可能会感兴趣的内容的Wiki。

几年前，这些家伙参与其中，他们很随和，回答了我很多问题，所以我看不出为什么他们仍然不是一个好人。

回答

与其为每个地图服务提供商(例如Gmaps，Ymaps api)学习API，不如学习Mapstraction

" Mapstraction是一个为各种javascript映射API提供通用API的库"

我建议我们转到URL并学习通用的API。也有大量的方法指南。

回答

通过地图路由，意思是找到沿着街道网络的最短路径？

Dijkstra最短路径算法是最著名的。 Wikipedia的介绍不错：http：//en.wikipedia.org/wiki/Dijkstra%27s_algorithm

这里有一个Java applet，我们可以在其中查看它的运行情况：http://www.dgp.toronto.edu/people/JamesStewart/270/9798s/Laffra/DijkstraApplet.html和Google，我们几乎可以将其引为源代码语言。

生成行驶路线的任何实际实现都将在街道网络上包含大量数据，这些数据描述了与遍历链接和节点相关的成本，道路网络层次，平均速度，交叉路口优先级，交通信号灯连接，禁止转弯等。

回答

我还没有找到关于路由的很好的教程，但是有很多代码需要阅读：

有一些使用Openstreetmap数据的GPL路由应用程序，例如Gosmore，可在Windows(+移动版)和Linux上运行。有许多有趣的[使用相同数据的应用程序，但是gosmore有一些很酷的用法，例如与网站的接口。

路由的最大问题是坏数据，而我们永远得不到足够的数据。因此，如果我们要尝试使用它，请保持测试非常本地化，这样我们就可以更好地控制数据。

回答

Google地图路线查找功能的工程师之一巴里·布鲁米特(Barry Brumitt)就该话题写了一篇有趣的文章：

通往更好道路的道路
2007/11/06下午03:47:00

回答

A *实际上更接近于产品映射算法。与Dijikstra的原始算法相比，它所需的探索要少得多。

回答

从概念的角度，想象一下将一块石头扔进池塘里，看着涟漪。路线将代表池塘，而石头则代表出发位置。

当然，随着距离n的增加，该算法将不得不搜索一定比例的n ^ 2路径。我们将以起始位置为起点，并检查从该点开始的所有可用路径。然后递归地调用这些路径末端的点，依此类推。

我们可以通过以下方式来提高性能：不对路径进行重复备份；不重新检查某个路径是否已被覆盖；以及放弃花费时间太长的路径。

另一种方法是使用蚂蚁信息素方法，在这种方法中，蚂蚁从起点随机爬行并留下气味，这会使更多的蚂蚁越过给定的路径。如果我们从起点和终点都发送(足够)的蚂蚁，那么最终气味最浓的路径最终将是最短的。这是因为在给定的时间内，如果蚂蚁以统一的速度行走，最短的路径将被多次访问。

编辑@ Spikie

为了进一步说明如何实现池塘算法，需要突出显示潜在的数据结构：

我们需要将地图存储为网络。这只是它们之间的一组"节点"和"边缘"。一组"节点"构成"路线"。一条边连接两个节点(可能是两个节点)，并具有关联的"成本"，例如"距离"或者"时间"来遍历该边。边可以是双向的也可以是单向的。仅具有单向路径并在节点之间的双向旅行中加倍(即一条从A到B的边而另一条从B到A的边)可能是最简单的。

举例来说，假设三个火车站以等边三角形的形式指向上方。在它们之间的中途还有另外三个站。边将所有相邻桩号连接在一起，最终图将有一个倒三角形，该三角形位于较大的三角形内。

标记节点从左下开始，从左到右并向上，依次为A，B，C，D，E，F(顶部为F)。

假设可以沿任一方向遍历边缘。每个边缘的成本为1公里。

好的，所以我们希望从左下方的A到顶部的车站F。 ABCEBDEF。

我们有一个例行的" NextNode"，它接受一个"节点"和一个"成本"，并针对其可以到达的每个节点进行调用。

显然，如果我们让此例程运行，它将最终发现所有路由，包括可能无限长的路由(例如ABABABAB等)。我们通过检查cost来阻止这种情况的发生。每当我们访问以前从未访问过的节点时，我们都会将成本和来自该节点的节点都放在该节点上。如果在检查现有成本之前已经访问过某个节点，并且如果价格便宜，那么我们将更新该节点并继续(递归)。如果我们更昂贵，那么我们跳过该节点。如果所有节点都被跳过，则我们退出例程。

如果我们击中目标节点，那么我们也将退出例程。

这样，可以检查所有可行的路线，但关键是仅检查成本最低的路线。到流程结束时，每个节点(包括我们的目标节点)将具有最低的成本到达该节点。

为了获得路线，我们从目标节点向后进行工作。由于我们存储了来自节点以及成本，因此我们仅向后跳即可构建路线。对于我们的示例，我们最终将得到以下结果：

节点A(总计)成本0来自节点无
节点A的节点B成本1
节点B的节点C成本2
节点A的节点D成本1
节点E的节点2的成本/节点B的成本2(这是例外，因为成本相等)
节点D的节点F成本2

因此，最短的路线是ADF。