2

首先，关于这个问题的一些背景：

我正在一个具有多种类型资源（A、B、C ...）的系统中工作。我有一些资源需求，我需要确定我是否能负担得起。

为此，我有一些资源，每个资源都可以提供不止一种类型的资源，但我需要为每种资源选择我要使用的资源。

例如，如果我需要支付 1A、2B 和 0C（表示为 (1,2,0)）并且我有这个来源：

  1. (1,1,0) //意味着我必须选择生产 A 或 B
  2. (0,1,1) //意味着我必须选择生产 B 或 C
  3. (1,1,0)

很明显，我必须将源 2 用于资源 B，我可以选择 1 和 3，其中一个产生 A 和 B

我实现这一点的方法是将其视为一个依赖关系图，其中上述情况表示如下：

在此处输入图像描述

因此，我遍历资源，并且对于每个资源，我都会遍历到达它的链接。如果删除当前资源的当前节点意味着其他资源有足够的剩余到达链接来支付剩余的费用，我使用它。

对于前面的示例，我首先尝试将源 1 用于资源 A。B 仍然有 2 个链接，所以我可以做到。只剩下 B 类资源需要支付，所以我使用剩余资源支付 B。

好的，但现在我需要在一个新场景中工作，其中有两种类型的资源，每一种以成本 1 或成本 2 生产一种资源，我需要最小化总成本。

对示例的轻微更改可能是这样的： 在此处输入图像描述

常识解决方案应该是使用1和2支付B，使用3支付A，总成本为1，但在我的实现中，如上所述，源1用于支付A，因为B还有2个链接到它，所以最后我必须使用成本为 2 的源 3。

如果可能，应避免暗示尝试所有选择组合的解决方案。

您是否知道可以应用于这种情况的任何具有已知解决方案的一般算法问题？或者如何改进我的实际解决方案以在这个新场景中工作？还是我应该采取另一种不同的方法？

4

1 回答 1

1

这个问题简化为在流网络中找到最大流。

这是想法：

  1. 对于每种类型的资源（A，B，...），一个节点具有来自源节点的传入边（源节点与问题的源无关，它是网络流理论中使用的常用标签，通常标记为s ) 的容量等于给定资源的所需数量。例如，如果您需要2B，则容量为 2。

  2. 对于每个源（我的意思是问题描述所定义的源），您创建一个节点，该节点具有到接收器的出边（通常标记为t），容量为 1。

  3. 从步骤 1 中的每个节点开始，为步骤 2 中的每个节点添加一条传出边，这些节点可以提供所需类型的资源。

例如，您的情况的图表如下所示：

流程图

现在这个网络中的最大 ST 流将为您提供答案。类型节点（A、B、C）和源节点（src1、src2、src3）之间基本上饱和的边会告诉你哪个源应该提供哪种类型的资源。

可以使用任何经典算法找到最大流量，例如增加路径 （Ford-Fulkerson、Dinic's等）或推送重新标记方法之一（Goldberg-Tarjan、Relabel-to-Front等）。

最大流量的这种特殊应用也可以被视为一种广义的二分匹配，您将每种类型的资源与可能的多个来源进行匹配，但每个来源只能处理一个资源。这个想法很容易扩展到源可以处理多种类型的情况（通过简单地将src - T边缘容量从 1 更改为所需的容量）。

于 2013-01-24T15:53:30.883 回答