对二进制2D矩阵进行排序？

Question

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

我有一个2D矩阵,每个单元格中有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都在右上方,我希望然后提供每个挑战的内在难度和竞争者排名的排名(这将考虑他们成功的挑战的难度,而不是只是成功的数量.)

关于已接受答案的注意事项:我已接受模拟退火作为"答案",但需要注意的是这个问题没有正确答案.这似乎是一个很好的方法,虽然我实际上没有设法得到一个适合我的问题的评分功能.

Answer 1

基于算法模拟退火可以处理这样的事情没有太多的麻烦.如果你的小矩阵很可能是一个固定的解决方案,那就太好了,但如果你的矩阵变得更大并且问题变得更加困难,那就太棒了.

(但是,它也不能满足您的需求,即可以逐步进行插入.)

预赛

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."相反"三角形将给出最大的负分数,正确的解决方案将给出最大的正分数.差分两个分数会给你带来成本.

如果这个得分手不适合你,那么你需要"调整"它直到它产生你想要的矩阵.

该算法基于这样的前提:调整该记分器比设计用于对矩阵进行排序的最佳算法简单得多.