algorithm - 寻找类似于旅行商的场景的最优解

Question

假设我有一个带权无向连通图，每个顶点有M个商品，需要N个商品。

对于一些顶点，M >= N 这样他们就可以满足他们的要求。对于其他顶点，我们必须将 cargo 从“富”顶点运输到它们，因为必须满足要求。

但是，运输是有成本的。成本等于边的重量乘以运输的 cargo 数量。

假设所有顶点拥有的商品数量大于所有顶点需要的商品数量。我需要一个交通方案，可以让所有顶点以最小的成本满足他们的需求。

对此有什么想法吗？感谢您的宝贵时间!

更新:

为了使这个问题更简单，如果顶点是 map 中的某个地方，则2个顶点之间的边不是 map 中2个地方之间的道路，而是这2个地方之间的最短路径。所以这个图变成了一个完整的图。

然后就不需要在“rich”顶点和“pool”顶点之间进行传输。我们可以将此图视为二分图。

Answer 1

您可以使用最小成本流算法来获得最优解:

1. 该图是二分图:第一组用于“丰富”的顶点。第二组用于可以接收额外商品的顶点。第一组的每个顶点和第二组的每个顶点之间有一条边 capacity = INF和 cost = distance between them .

2. 还有一条边从源到第一组的每个顶点 capacity = number of goods that must be removed和 cost = 0 .

3. 第二组中的每个顶点和带有 capacity = number of goods it can receive 的汇都有一条边和 cost = 0 .

答案是这个图中最大流的成本(从源到汇)。也可以通过查看通过每条边的流量来重建交通计划本身。