algorithm - 对二进制二维矩阵进行排序？

Question

我在这里寻找一些指示，因为我不太知道从哪里开始研究这个。

我有一个二维矩阵，每个单元格中有 0 或 1，例如:

  1 2 3 4
A 0 1 1 0
B 1 1 1 0
C 0 1 0 0
D 1 1 0 0

我想对其进行排序，使其尽可能“上三角”，如下所示:

  4 3 1 2
B 0 1 1 1
A 0 1 0 1
D 0 0 1 1
C 0 0 0 1

行和列必须保持完整，即元素不能单独移动，只能“整体”交换。

我知道可能会出现病态情况，其中矩阵有多个可能的排序结果(即形状相同，但“原始”行/列的标识不同。)

那么，有人可以建议我在哪里可以找到一些起点吗？现有的库/算法会很棒，但我满足于知道我要解决的问题的名称!

我怀疑这是一个线性代数问题，也许有某种适用的图像处理技术。

抛开任何其他想法，我最初的猜测只是对行编写一个简单的插入排序，然后对列进行迭代，直到它稳定下来(并希望检测病态情况不会太难。)

更多细节:关于我正在尝试做的事情的一些更多信息可能有助于澄清。每行代表一个竞争对手，每一列代表一个挑战。每个 1 或 0 代表参赛者在特定挑战中“成功”。

通过对矩阵进行排序，使所有 1 都在右上角，我希望然后提供每个挑战的内在难度排名和竞争对手的排名(这将考虑他们成功挑战的难度at，不仅仅是成功的次数。)

关于已接受答案的注意事项:我已接受模拟退火作为“答案”，但需要注意的是该问题没有正确答案。这似乎是一个很好的方法，尽管我实际上还没有想出一个适合我的问题的评分函数。

Answer 1

基于 simulated annealing 的算法可以处理这类事情而不会有太多麻烦。如果你有一个很可能有固定解决方案的小矩阵，那不是很好，但如果你的矩阵变得更大并且问题变得更加困难，那就太好了。

(但是，这也无法满足您对增量插入的期望。)

预赛

1. 设计一个为矩阵“评分”的性能函数 - 更接近三角形的矩阵应该比那些更接近三角形的矩阵获得更好的分数。

2. 设计一组在矩阵上允许的操作。您的描述有点含糊，但如果您可以交换行，那么一个操作就是 SwapRows(a, b)。另一个可能是 SwapCols(a, b)。

退火循环

我不会在这里给出完整的说明，但这个想法很简单。您使用您的操作对矩阵执行随机转换。您测量操作后矩阵的“好”程度(使用操作前后的性能函数)。然后您决定是否进行该转换。您多次重复此过程。

决定是否提交转换是有趣的部分:您需要决定是否执行该操作。在退火过程结束时，您只接受提高矩阵分数的转换。但在更早的时候，在更困惑的时期，您允许进行不会提高分数的转换。一开始，算法是“热的”，什么都行。最终，算法冷却下来，只允许好的转换。如果对算法进行线性降温，那么是否接受变换的选择是:

public bool ShouldAccept(double cost, double temperature, Random random) {
    return Math.Exp(-cost / temperature) > random.NextDouble();
}

您应该阅读 Numerical Recipes 中包含的优秀信息有关此算法的更多信息。

长话短说，您应该学习其中一些通用算法。这样做将使您能够解决大量难以分析解决的问题。

评分算法

这可能是最棘手的部分。您将需要设计一个记分器来引导退火过程朝着您的目标迈进。记分器应该是一个连续函数，随着矩阵接近理想解，它会产生更大的数字。

您如何衡量“理想解决方案”——三角形度？这是一个天真而轻松的得分手:对于每一分，您都知道它应该是 1 还是 0。如果矩阵正确，则将分数加 +1，如果矩阵错误，则将分数加 -1。这里有一些代码，所以我可以明确(未经测试!请查看!)

int Score(Matrix m) {
    var score = 0;
    for (var r = 0; r < m.NumRows; r++) {
        for (var c = 0; c < m.NumCols; c++) {
            var val = m.At(r, c);
            var shouldBe = (c >= r) ? 1 : 0;
            if (val == shouldBe) {
                score++;
            }
            else {
                score--;
            }
        }
    }
    return score;
} 

使用此评分算法，1 和 0 的随机字段将给出 0 分。“相反”的三角形将给出最负的分数，而正确的解决方案将给出最正的分数。将两个分数相差会给你成本。

如果这个记分器不适合您，那么您将需要“调整”它直到它产生您想要的矩阵。

该算法基于这样的前提，即调整此评分器比设计用于排序矩阵的最佳算法要简单得多。