java - 迭代归约到空矩阵

Question

这就是问题所在：我得到了一个类似的矩阵

输入：

1 1 1
1 1 1
1 1 1

在每一步，我都需要找到一个由 1 和 0 组成的“第二个”矩阵，在同一行或同一列上没有两个 1。然后，我将从原始矩阵中减去第二个矩阵。我将重复这个过程，直到我得到一个全为 0 的矩阵。此外，我需要采取尽可能少的步骤。

我需要在 O(n) 时间内打印所有“第二个”矩阵。在上面的示例中，我可以通过按顺序减去这三个矩阵，分 3 步得到空矩阵：

预期输出：

我编写了一个尝试，其中我找到了第一个最大值并根据该值的索引创建第二个矩阵。但是对于上述输入，我得到 4 个输出矩阵，这是错误的：

我的输出：

我的解决方案适用于大多数测试用例，但不适用于上面给出的测试用例。有人可以给我一些关于如何进行的指示，或者找到一种保证最优性的算法吗？

有效的测试用例：

输入：

0 2 1
0 0 0
3 0 0

输出

score 1 · Accepted Answer

每行/列的总和并取其中最大的总和为您提供减少到空矩阵所需的矩阵减法的最佳数量。

例如：

1 2 4 0 = 7
2 2 0 1 = 5
0 0 1 0 = 1
3 0 2 1 = 6
= = = =
6 4 7 2

这意味着该矩阵将需要 7 次最佳减法才能清空。

我相信从这个倒数并从具有该值的列/行中删除将解决您的问题（我不确定选择这些的有效方法 - 蛮力？）。
您还可以使用以前的方法删除多余的元素。

例如（使用上面的矩阵）。

第 7 步：
我们必须从第 1 行和第 3 列中减去。

解决了这个问题，所以现在我们可以使用您以前的方法来删除“奖励”元素。

现在再次应用每行/列的总和并继续下一步。

第 6 步：

1 2 3 0 = 6
1 2 0 1 = 4
0 0 1 0 = 1
3 0 2 0 = 5
= = = =
5 4 6 1

下一个减法：

等等。

注意：这仍然不适用于“全 1”矩阵，因为您遇到了从每行和每列中选择 1 的问题（与您在示例中所做的相同）。

但是有人可能能够扩展我的解决方案。

score 0 · Accepted Answer

我很确定这是精确覆盖问题的某种变体，已知它是 NP 完全的。您提出的算法是一个简单的贪心解决方案。贪婪解决方案的问题在于，它们通常运作良好，足以让你相信贪婪是好的，然后突然让你高高在上，寻找更好的解决方案。（例如，考虑全球经济。）无论如何，Knuth 的Dancing Links技术是解决问题的标准方法（精确设置封面，而不是全球经济）。

score 0 · Accepted Answer

1) If all you want to do is iterate through all the elements in your matrix...

2) then all you have to do is loop for (int i=0; i < rows*cols; i++) {} ...

3) And such a loop is ALREADY O(n) (i.e. it increases LINEARLY with the #/elements in your matrix)

score 0 · Accepted Answer

令行数 = 列数 = N

for iteration=1:N
  for row=1:N
      cell(row,(row+iteration)%N) := 0

迭代次数为 N。在每次迭代中，N 个将变为 0

score 0 · Accepted Answer

我不完全确定这是否是您所追求的，但您能否创建一个可用列的列表并将它们标记为用于每次迭代。

例如：

repeat until an empty matrix
  mark all columns as available
  for each row
    find the maximum value in all available columns and store it's coordinates
    mark that column as unavailable
  print, decrement and clear the list of stored coordinates

这不起作用，但它确实显示了 user1459032 正在使用的算法。

java - 迭代归约到空矩阵

5 回答 5

Related

Reference