蟒蛇临界路径的变化

Question

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

我第一次搜索堆栈溢出的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为起点时，我需要这样做：

使连接A(这将花费2+5+7 = 14)

而不是

ABCD = 19

ACBD = 16

ADCB = 18

ABDC = 17

ACDB = 18

Answer 1

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

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

如果我错了，而且你的图是有向的，那么就不足以生成所有的组合，你将需要生成所有的变体。

请注意，如果出于某种原因，可能是节点对不一定有终止点的情况。在这种情况下，您需要生成所有有效的变体，其中有效意味着相邻的两个节点都有一个顶点。