时间戳

首页 > 解决方案 > 使用距离矩阵查找带有航点的最短路线

algorithm - 使用距离矩阵查找带有航点的最短路线

问题描述

我想使用谷歌地图 v3 获得 A 点和 B 点之间的最短路线，其中有 X 个航点。

对于这个例子，假设我想计算 A 和 B 之间的最短路线，其间有 C、D、E 航路点。

为此，我使用距离矩阵服务来查找 [AB, AC, AD], [BC, BD, BE], [CD, CE], [DE] 之间的距离，结果如下：

A) 地址 A [B: 4, C: 1.4, D: 1.4] 总是路线的起点

B) 地址 B [C: 3.8 ,D: 1.3, E: 3.1]

C) 地址 C [D: 1.2, E: 3.1]

D) 地址 D [E: 2.7]

E) 地址 E - 始终结束路线

路线1：A + B + C + D + E = 4 + 3.8 + 1.2 + 2.7 = 11.7Kms

路线2：A + C + B + D + E = 1.4 + 3.8 + 1.3 + 2.7 = 9.2Kms

路线3：A + D + B + C + E = 1.4 + 1.3 + 3.8 + 3.1 = 9.6Kms

路线：A + B + D + C + E = 4 + 1.3 + 1.2 + 3.1 = 9.6Kms

路线5：A + C + D + B + E =1.4 + 1.2 + 1.3 + 3.1 = 7Kms

路线 6：A + D + C + B + E = 1.4 + 1.2 + 3.8 + 3.1 = 9.5 公里

在这种情况下，获胜者是 Route 5，但我有三个问题：

  1. 就谷歌地图的大量计费而言，这是自杀吗？考虑到路由最多有 12 个地址，包括起始地址和结束地址。

  2. 就javascript性能而言，这是自杀吗？

  3. 有没有更好的方法来解决这个问题？

提前致谢

标签： algorithmgoogle-maps

解决方案

这个怎么样：

保留所有距离的列表（假设 A --> F，具有 B、C、D 和 E 中间点）：

A: AB, AC, AD, AE
B: BC, BD, BE, BF
C: CB, CD, CE, CF
D: DB, DC, DE, DF
E: EB, EC, ED, EF

假设我们根据距离对它们进行排序。

从 A 中选择最短的距离（假设是 AC）。

从 C 中选择到另一个中点 (CE?) 的最短距离

重复此操作并获得类似 ACEBDF 的内容。将此距离存储为 d_min。

回去尝试另一条路。我们可以更改的第一件事是EB，我们可以将其更改为ED。ACEDB 比 ACEBDF 长吗？如果是这样，请进一步返回并尝试 ACB。如果不是，则针对 d_min 测试 ACEDBF。

依此类推-这可能会为您节省一些更长的路线，并且它会找到最短的路线，尽管它可能会测试所有排列。但是，我认为不存在更快的方法来做到这一点。

推荐阅读