通过排列行和列将矩阵转换为块矩阵

Question

我有一个 n 行 m 列的矩形矩阵。矩阵的所有条目都是自然数（包括 0）。

在 m 列中，我给出了一些索引 j (< m). I'd like the matrix to become a block matrix as shown below.

对于前 i 行（我们可以选择任何 i <= n we want), every entry to the right of j should be 0. And for the next (n-i) rows, every entry to the left of index j should be 0.

如果这是不可能的，则上图中两个阴影区域（深灰色）中的条目之和应尽可能小。

原始矩阵上唯一允许的操作是交换行和交换列。我对实现这一目标的有效算法感兴趣。

Answer 1

n.m. 将矩阵解释为图的邻接矩阵的想法是一个很好的想法。

这是一个最小割问题。

这两个“块”对应于将图的节点划分为两个集合。我们将这些集合称为 S 和 T。

不在“块”内的条目对应于从 S -> T 或相反的边，矩阵中的数字对应于边的权重。

最小化“灰色区域”的条目总和相当于最小化切割的容量，同时考虑到两个方向的边缘。

这可以通过使用最大流算法来有效解决，根据最大流最小割定理也可以给你一个最小割。

您可以使用例如推送重新标记算法来获得 O(n² sqrt(m)) 的解决方案。请注意，m 是边数 - 对应于矩阵中非零条目的数量。所以这个算法对于稀疏矩阵来说会更快，并且在一般情况下是 O(n³)。

您可以任意选择来源；它必须是 S 或 T。

请注意，这是一个最小的“s-t-cut”，也就是说，它是“有向的”：仅当边缘从 S 到 T 时才被计数（其中 S 是包含 s 的集合）。

要计算这两种情况下的边缘，请始终为每个边缘 (u, v) 添加具有相同权重的后边缘 (v, u)。如果这给你平行的边缘，将它们的权重相加。