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

Question

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

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

我认为您可以找到一个解决方案，通过每个可能的组合循环并检查每行和每列中是否正好有一个 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，我们可以检查每个生成的矩阵。如果是，这是一个解决方案。

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

score 3 · Accepted Answer

编辑：

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

新答案：

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

编辑2：

这里的问题是你想找到所有的解决方案。而且还有很多。对于全 1 的 nxn 矩阵，您将有n!解决方案。对于每行都有m1 的矩阵，你可能会有类似的东西

^米米*米！

解决方案。因此，即使您有一个非确定性算法可以在 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 的行或列，所以我们开始赋值。假设我们已经按照我们的回溯算法（在步骤 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-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} 的排序将为您提供上面的第二个矩阵。

score 1 · Accepted Answer

我写了这个简单的代码（使用你的矩阵）：

A=[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]

[row,col]=size(A);
B=zeros(row,col);

for i=1:col

    [one_row,~]=find(A(:,i)==1); %one_row says in wich row of the "i" column there are ones
    where_row=min(one_row); %we're interested only in one of those "ones".I'm taking the first found
    B(where_row,i)=1; %inserting in the output matrix
end

B %for visualization purposes

我希望这个对你有用。

score 1 · Accepted Answer

这是一个二分匹配问题。

考虑一个二部图，其中一个集合 (R) 中有 r 个顶点，另一个集合 (C) 中有 c 个顶点，其中 r 和 c 分别是行数和列数。如果给定矩阵中的元素为 1，则顶点i（在集合 R 中）和顶点（在集合 C 中）之间的边存在。j[i,j]

如果您想找到最大数量为 1 的矩阵（最大二分匹配），您可以使用

使用Ford-Fulkerson 算法的最大二分匹配O(V.E)

或者

用于最大匹配的 Hopcroft–Karp 算法正在运行O(sqrt(V).E)

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

3 回答 3

编辑：

新答案：

编辑2：

原始（错误）答案

Related

Reference