算法：使用最大流来计算正确的矩阵值

Question

我得到一个矩阵 A，大小为 N x M N,M <= 100。矩阵 A 由整数值 A(i,j) 组成，其中 i 和 j 分别为 0 < i < M 和 0 < j < N。我还得到了矩阵的 "correct" 列总和和行总和。给定值 A(i,j) 是 "incorrect"（它们与 "correct" 和不匹配）因此我们得到相应的 "incorrectness" 值 B(i,j)，其中 B (i,j) 的范围从 0 到 A(i,j)。

目标是计算矩阵中的"correct"个值C(i,j)，其中A(i,j) - C(i,j) =< B(i,j)，C(i,j)值也必须匹配给定的行和列总和。我想我必须使用最大流量，但我的尝试没有奏效。我怎样才能做到这一点？

Answer 1

这里我只是举个例子。

matrix A:
 10 10 10
 10 10 10
 10 10 10

matrix B:
  2  3  4
  5  6  4
  3  2  1

matrix A-B:
  8  7  6
  5  4  6
  7  8  9

所以你有公式 A[i,j] - C[i,j] <= B[i,j]。您可以将其转换为 A[i,j] - B[i,j] <= C[i,j] 这意味着 B[i,j] 是您需要从 A[i,j 中减去的最小值] 得到小于或等于 C[i,j] 的东西。从这里您知道您需要向矩阵 A-B 中的条目添加一些内容。

现在让我们找出要添加的内容和位置。

假设给定了以下行和列大小：

c1 = 20/20
c2 = 19/21
c3 = 21/24

r1 = 21/21
r2 = 15/17
r3 = 24/27

上面我写的是这样的形式：

(current flow through column or row) / (goal flow through column or row).

现在让我们建立一个网络：

现在请注意，行的总和 = 列的总和。所以你尝试将 'given sum of entries' - 'current sum of entries' 从 's' 推到 't'.

现在，假设节点是按自然数从左到右枚举的。现在，当您将某些内容从第二级节点推送到第三级节点时，例如，您将某些内容从节点 i 推送到节点 j，您还会将推送的内容添加到 NewMatrix[i,j]，其中 NewMatrix 是矩阵 A-B然后你得到你想要的矩阵。

另请注意，一开始，在矩阵 A-B 中，您有最小的 C[i,j]，您必须从 A[i,j] 中减去它才能得到更小或等于 B[i, j]，现在你向 C[i,j] 添加了一些东西，不等式 A[i,j]-C[i,j]<=B[i,j] 仍然成立。

算法：使用最大流来计算正确的矩阵值

Algorithms: Using maximum flow to calculate correct matrix values

algorithm

optimization

networking

graph-theory

matrix