algorithm - 地图上许多点之间的距离

Question

我有一个 20,000 点的 GPS 位置数组。

它们代表森林路径上需要检查的点。我需要弄清楚需要检查多少公里的森林路径。

1. 将点分组为路线。
2. 测量每条路径的短路路径

我应该考虑哪些算法以及按什么顺序。

我应该获得最短路径并将其分解为路线还是获得路线然后找到每个路线的短路路径。

Answer 1

该解决方案假设您只有点并且不知道这些点在哪条森林路径上，以及以什么顺序等。

我会这样尝试：

1 通过链接将每个节点相互连接，并作为链接权重使用距离（或者在节点之间以 2km/h 的米为单位行驶时更好的秒数：假设在树林中行走的低速比在现有林道）

2 如果森林有困难（山脉、山谷、河流）：

2a：上升/下降：提高链路权重，利用海拔差异，查看户外规划资源，上升多少米对旅行时间有影响。（粗略估计300m可能是额外的一小时）

2b：山谷、河流或其他限制：如果不能直接从一个点到另一个点，要么再次提高重量，要么移除链接。（例如将山谷绘制为多边形并删除所有穿过多边形的链接）

树林里是否已经有小径/林道？
是的，将它们作为链接绘制到模型（图表）中，以使用链接权重，例如 5 公里/小时的步行速度。

现在，您有一个包含节点的图，并且链接具有与节点之间的行进速度相关的真实链接权重。

现在使用 Shortes 路径（Dijkstras 算法）和旅行商算法。

如果这一切都需要大量工作（对于拥有计算机科学学位的人来说可能需要几个月的时间），请手动计划：绘制 1000 x 1000m 的栅格并让人类智能完成其工作。

由于必须通过步行检查 20.000 个点，需要付出很大的努力，因此评估自动规划与人类经验是额外值得的。尝试两种变体并查看哪个更有效。

（我认为有户外经验的人在拥有一张带有县线和检查点的好地图时会做得更好，假设按点预先组织了两个象限分配和象限给人们。）

Answer 2

我的另一个解决方案：

这假设您有更多尚未发布的信息：

您可能拥有的信息不仅仅是点的坐标。谁创造了这个点？在您的图形中，它们看起来就像在路径上一样。他们是在驾驶车辆在该路径上行驶时记录下来的吗？然后你有一个时间戳，因此有一个顺序点的顺序，并且已经与路径相关。

因此，第一步是将点分配给路径。（您还可以将所有称为矢量的森林路径绘制到数字地图上，并自动将这些点与最近的路径匹配）

当您无法直接到达它们之间的直线上的每个节点时，您需要路径（例如，当河流避开直接直线路径时，开车或在树林中行走）

然后，一旦你有一个带有链接节点的图，使用最小生成树来计算以公里为单位的路径长度的总和。

为了访问这些点，您通常必须返回分支，因此旅行推销员算法将有助于提供访问所有节点所需的公里数。

Answer 3

这个问题似乎类似于受约束的车辆路线问题。您可以尝试启发式算法，例如储蓄算法： http: //neo.lcc.uma.es/vrp/solution-methods/heuristics/savings-algorithms/。