arrays - 为具有已知行/列总和和最大单元格值的矩阵找到可能的解决方案

Question

我正在尝试找到一个矩阵的解，其中我知道行和列的总和以及单元格可以具有的最大值。我想找到在约束范围内的可能解决方案。我已经尝试过各种方法，例如构建所有单元格值的数组并按顺序从每个单元格中挑选，但无论我尝试什么，我总是遇到我用完单元格值的问题。 我也尝试了一种递归算法，但我只设法得到第一个结果，或者它没有得到任何解决方案。我想我必须用回溯算法来做到这一点？不确定...

如有任何帮助或指点，我们将不胜感激。

行总和 A、B、C，列总和 X、Y、Z 以及每个 ?是已知的。所有的值都是正整数。

    C1 | C2 | C3 
-----------------
R1 | ? | ?  | ? | A
-----------------
R2 | ? | ?  | ? | B
-----------------
R3 | ? | ?  | ? | C
-----------------
     X | Y | Z

Answer 1

如果您听说过 linear programming (LP) 及其“表兄弟”(ILP、MILP)，这可能是帮助您高效解决问题的好方法。
线性规划由一组变量(您的矩阵未知数)、约束(最大值、行和列之和)和一个用于最小化或最大化的目标函数(这里没有)组成。

让我们将 x[i][j] 称为您正在寻找的值。 具有以下数据:

NxM 矩阵的维度
max_val[i][j] 变量 x[i][j]
的最大值 row_val[i] i
行值的总和 col_val[j] j 列值的总和

那么可以解决您的问题的一个可能的线性程序是:

// declare variables
int x[N][M] // or eventually float x[N][M] 
// declare constaints
for all i in 1 .. N, j in 1 .. M, x[i][j] <= max_val[i][j]
for all i in 1 .. N, sum[j in 1 .. M](x[i][j]) == row_val[i]
for all j in 1 .. M, sum[i in 1 .. N](x[i][j]) == col_val[j]
// here the objective function is useless, but you still will need one
// for instance, let's minimize the sum of all variables (which is constant, but as I said, the objective function does not have to be useful)
minimize sum[i in 1 .. N](sum[j in 1 .. M](x[i][j]))
// you could also be more explicit about the uselessness of the objective function
// minimize 0

求解器，例如 gurobi或 Cplex (但还有更多，例如参见 here)可以非常快地解决此类问题，特别是如果您的解决方案不需要是整数，但可以是 float (这使问题变得非常非常容易) .它还具有不仅执行速度更快，而且编码速度更快、更简单的优点。他们有多种常见编程语言的 API，以方便使用。
例如，您可以合理地期望在不到一分钟的时间内解决此类问题，整数情况下有数十万个变量，实数情况下有数百万个变量。

编辑: 作为对评论的回应，这里有一段 OPL(Cplex 和其他 LP 求解器使用的语言)代码可以解决您的问题。我们考虑 3x3 的情况。

// declare your problem input
int row_val[1..3] = [7, 11, 8];
int col_val[1..3] = [14, 6, 6];
int max_val[1..3][1..3] = [[10, 10, 10], [10, 10, 10], [10, 10, 10]];

// declare your decision variables
dvar int x[1..3][1..3];

// objective function
minimize 0;

// constraints
subject to {
    forall(i in 1..3, j in 1..3) x[i][j] <= max_val[i][j];
    forall(i in 1..3) sum(j in 1..3) x[i][j] == row_val[i];
    forall(j in 1..3) sum(i in 1..3) x[i][j] == col_val[j];
}

LP 求解器的概念是，您只需描述要解决的问题，然后求解器就会为您解决。必须根据一组特定的规则来描述问题。在当前情况下(整数线性规划，或 ILP)，变量必须全部是整数，并且约束和目标函数必须是关于决策变量的线性等式(或不等式)。
然后求解器将作为黑匣子工作。它将分析问题，运行可以解决问题的算法，进行大量优化，然后输出解决方案。