algorithm - 矩阵的每一行和每一列恰好有一个值

Question

我试图找出解决此问题的最佳方法: 有这样一个矩阵:

1 0 0 1 0
1 1 0 1 0
1 1 0 0 1
0 0 1 1 0
1 0 1 0 0

我们想找出每行和每列只有一个1的所有可能的矩阵，例如这个矩阵是一个可能的解决方案:

1 0 0 0 0
0 1 0 0 0
0 0 0 0 1
0 0 0 1 0
0 0 1 0 0

我想你可以找到一个解决方案，循环遍历每个可能的组合，并检查每一行和每一列中是否恰好有一个 1？这有什么已知的算法吗？ 是否可以实际计算解决方案而不尝试所有可能性？

非常感谢!

编辑: 一种可能的解决方案(但昂贵)可能是生成每个理论上可能的矩阵，例如(使用 3x3 矩阵，因为它更短): 1.

1 0 0
0 1 0
0 0 1

2.

1 0 0
0 0 1
0 1 0

3.

1 0 0
0 0 1
0 1 0

4.

0 1 0
1 0 0
0 0 1

5.

0 1 0
0 0 1
1 0 0

等等

然后我们可以检查每个生成的矩阵，如果原始矩阵在给定位置有 1。如果是，那就是一个解决方案。

生成所有这些矩阵需要哪些循环？

Answer 1

编辑:

根据您的评论，我重新阅读了原始问题，并意识到我完全错过了问题的重点。我会在这里发布(希望)更相关的答案，但人们应该随时撤销任何赞成票。我讨论过发布一个新答案并删除这个答案，如果人们认为这是可行的方法，我仍然可以这样做。

新答案:

现在我是这样理解你的问题的。给定一个二元方阵 A，找到所有矩阵 B，使得 B 的每一行元素之和为 1，每列元素之和为 1，并且对于所有元素 B(r,c) == 1，原始矩阵 A(r,c) == 1 中的对应元素。

编辑 2:

这里的问题是您想找到所有 的解决方案。它们的数量很多。对于全 1 的 nxn 矩阵，您将有 n! 解。对于每行都有 m 1 的矩阵，您可能会得到类似

的内容

m^n-m * m!

解决方案。因此，即使您使用非确定性算法在 O(1) 时间内生成所有解决方案，简单地将它们打印出来的时间复杂度仍然是指数级的。

正如 MrSmith42 在评论中提到的，您可能需要进行回溯搜索，但您可以采取一些措施来减少搜索空间:

您可以进行的最简单的检查是查找 A 中已经只有一个 1 的行/列。 (显然，如果有任何行/列中没有 1，则没有有效的解决方案。)如果r行在c列中只有一个1 ，将 c 列中的所有其他元素设置为 0。同样，如果 c 列在 r 行中只有一个 1，则设置所有其他元素 行 r 到 0。在您的示例中:

1 0 0 1 0     1 0 0 1 0     1 0 0 1 0
1 1 0 1 0     1 1 0 1 0 ==> 0 1 0 0 0
1 1 0 0 1 ==> 0 0 0 0 1     0 0 0 0 1
0 0 1 1 0     0 0 1 1 0     0 0 1 1 0
1 0 1 0 0     1 0 1 0 0     1 0 1 0 0

第 5 列中只有一个 1，因此 B 中的第 3 行必须在 B(3,5) 处有一个 1 才能有效。这意味着我们可以修改我们的输入矩阵 A 并(稍微)减少搜索空间而不会丢失任何有效的解决方案。从这里开始，您现在在第 2 列中只有一个 1，并且可以将第 2 行中的其他值设置为 0。

接下来，您可以在搜索过程中使用前向检查来防止搜索不可能找到有效解决方案的子矩阵。假设您有以下矩阵:

1 0 0 1 0
0 1 1 0 1
1 1 0 0 1
0 0 1 1 0
1 0 1 0 0

没有只有一个1的行或列，所以我们开始赋值。假设我们按照回溯算法进行到(在第 1 步中)我们已将第 4 列分配给第 1 行的位置。我们将第 1 行和第 4 列中的其他条目设置为 x 以表明他们已经被分配:

               Step 1        Step 2
1 0 0 1 0 ==> x x x 1 x     x x x 1 x
0 1 1 0 1     0 1 1 x 1 ==> x x 1 x 1
1 1 0 0 1     1 1 0 x 1     1 1 x x 1
0 0 1 1 0     0 0 1 x 0     0 0 x x 0
1 0 1 0 0     1 0 1 x 0     1 0 x x 0

在第 2 步中，我们将第 3 列分配给第 2 行，并将行和列设置为已分配。

请注意，在第 4 行中，我们没有留下任何 1，因此不可能通过此分配获得有效的解决方案。我们可以立即回溯，尝试对第 2 行和第 1 行进行不同的分配。

原始(错误)答案

每个可能的 nxn 矩阵，每行和每列中只有一个 1，其余为 0 是单位矩阵的排列。也就是说，对于 n=5，您可以通过交换矩阵的行(或等效地，列)来获取此类型的每个有效矩阵:

1 0 0 0 0
0 1 0 0 0
0 0 1 0 0
0 0 0 1 0
0 0 0 0 1

例如，如果将最后一行交换为行，您将得到:

1 0 0 0 0
0 1 0 0 0
0 0 1 0 0
0 0 0 0 1
0 0 0 1 0

要自动生成所有可能的有效矩阵，您首先要给单位矩阵的每一行一个索引，比如从上到下的 1-5:

1- 1 0 0 0 0
2- 0 1 0 0 0
3- 0 0 1 0 0
4- 0 0 0 1 0
5- 0 0 0 0 1

然后您只需生成所有 n! {1, 2, 3, 4, 5} 的可能排列。 {1, 2, 3, 5, 4} 的排序将给出上面的第二个矩阵。