如何找到最小化边数的方法？

Question

我在想一个算法来解决下面的问题:

由顶点和边组成的给定图.

有N个客户想要从顶点行进到另一个顶点.每个客户需求都需要一个有向边来连接两个顶点.

问题是如何找到满足所有客户要求的最小边数？

有一个简单的例子:

• 客户1想要从顶点a行进到顶点b.
• 客户2想要从顶点b行进到顶点c.
• 客户3想要从顶点a行进到顶点c.

最简单的方法是为每个客户提供优势:

• 边1:顶点a - >顶点b
• 边2:顶点b - >顶点c
• 边3:顶点a - >顶点c

但实际上只需要2个边缘(即边缘1和边缘2)来满足三个客户的要求.

如果客户数量很大,如何找到满足所有客户要求的最小边缘？

有没有算法来解决这个问题？

Answer 1

您可以将问题建模为混合整数程序。您可以为“使用 arc a-> b”和“客户 c 使用 arc a -> b”定义二元变量，并将要求写为线性不等式。如果您的图形不太大，您可以通过混合整数程序求解器（CPLEX、GUROBI，但网络上也有免费的替代方案）在合理的时间内求解此类模型。

我知道，如果您不熟悉线性规划，此解决方案需要做一些工作，但它保证在有限时间内找到最佳解决方案，并且您可能可以解决（例如）1000 个客户和 1000 个弧。