0

我正在寻找一种方法来确定连接地图上不同坐标的成本最低的路径。这些坐标代表管道网络的消费者和一个供应商

我首先搜索堆栈溢出的 GIS 部分以进行成本最低的路径分析，但这不是我所需要的（我没有找到一种算法，它允许不仅仅是一个起点和终点）。我有一个算法可以确定所有不同坐标之间的最低成本路径，但现在我想对这些数据进行一种关键路径分析。但是，在最终解决方案中必须解决所有坐标，并且除了需要成为第一个的供应商之外，哪个坐标首先出现并不重要。

有人可以帮我吗？

提前致谢

例子

好的，主要问题是：

我将有一个这样的矩阵：

  A  B  C  D

A x  3  4  2

B 3  x  7  5

C 4  7  x  9

D 2  5  9  x

在这个矩阵中，A、B、C 和 D 将代表地图上的一个位置（仅通过 X 和 Y 坐标），数字是在 A 和 B 之间建立连接的价格（例如：这些成本基于我将有）。我的目标是以最便宜的方式将所有这些点连接起来。

为此，我正在考虑一个关键路径分析（您可能从您的业务课程中知道），但显然这不会起作用，因为这些算法未编写导致包含所有位置的路径。但我需要连接所有这些 (4) 节点，但只是以最便宜的方式。

例如：当我以 A 为起点时，我需要这个结果：

建立连接 ADBC（这将花费 2+5+7 = 14）

并不是

ABCD = 19

ACBD = 16

ADCB = 18

ABDC = 17

ACDB = 18

4

1 回答 1

1

您描述的问题是邮递员的问题，不知道哪个是起点。根据您的问题，我相信您的图表不是定向的，因此从 A 到 B 的距离与从 B 到 A 的距离一致。在这种情况下，您可以通过迭代所有点组合并计算总距离来解决您的问题（即路径中距离的总和）。最小值是问题的解决方案。

在这里您可以阅读有关生成组合的更多信息。但是不要提前生成它们，这对内存管理不利，只是总是计算下一个组合，测量它的总距离并与最小值进行比较。如果它低于最小值，则将最小距离修改为新的最小值并将组合存储到一个数组中，该数组将包含最后的最佳路径。如果您的图形是无向的并且所有节点对都有一个顶点，那么这就是答案的结尾。

如果我错了并且您的图表是定向的，那么生成所有组合是不够的，您需要生成所有变体。

请注意，如果由于某种原因可能是节点对不一定具有顶点的情况。在这种情况下，您需要生成所有有效的变体，其中有效意味着彼此靠近的两个节点有一个顶点。

于 2014-04-01T13:16:28.770 回答