algorithm - 我怎样才能找到最小化边数的方法？

Question

我正在考虑一种算法来解决以下问题:

A given graph composed of vertices and edges.

There are N customers who want to travel from a vertex to another vertex.And each customer requirement need a directed edge to connect two vertices.

The problem is how to find the minimum number of edges to satisfy all customers requirements ?

有一个简单的例子:

• 客户 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 个弧。