排序二元二维矩阵？ [英] Sorting a binary 2D matrix?

问题描述

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

I'm looking for some pointers here as I don't quite know where to start researching this one.

我有一个2D矩阵用0或1每个单元中，如：

I have a 2D matrix with 0 or 1 in each cell, such as:

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

和我想对它进行排序所以它是上三角成为可能，像这样：

And I'd like to sort it so it is as "upper triangular" as possible, like so:

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

的行和列，必须保持不动，即元素不能被单独移动，并且只能被交换整体

The rows and columns must remain intact, i.e. elements can't be moved individually and can only be swapped "whole".

据我所知，有可能会是病理性的情况下，基体有多个可能的排序结果（即相同的形状，但不同的原创行/列的身份。）

I understand that there'll probably be pathological cases where a matrix has multiple possible sorted results (i.e. same shape, but differ in the identity of the "original" rows/columns.)

所以，任何人都可以提出，我可能会发现一些出发点呢？现有的库/算法将是巨大的，但我会满足于知道这个问题，我试图解决的名字！

So, can anyone suggest where I might find some starting points for this? An existing library/algorithm would be great, but I'll settle for knowing the name of the problem I'm trying to solve!

我怀疑这是一个线性代数的问题，因为这样，也许有一些类型的图像处理技术，这是适用的。

I doubt it's a linear algebra problem as such, and maybe there's some kind of image processing technique that's applicable.

任何其他的想法放在一边，我最初的猜测仅仅是写一个简单的插入排序的行，然后列和迭代直到它稳定（并希望检测的病理情况下，是不是太辛苦了。）

Any other ideas aside, my initial guess is just to write a simple insertion sort on the rows, then the columns and iterate that until it stabilises (and hope that detecting the pathological cases isn't too hard.)

详细信息：上什么，我试图做可能有助于澄清一些详细信息。每一行再presents竞争对手，每一列重presents一个挑战。在一个特别的挑战每个1或0重新presents成功的竞争对手。

More details: Some more information on what I'm trying to do may help clarify. Each row represents a competitor, each column represents a challenge. Each 1 or 0 represents "success" for the competitor on a particular challenge.

通过分类矩阵使全1是在右上角，我希望能够再提供每个挑战的内在难度排名和竞争对手排名（这会考虑到他们成功的挑战难度时，成功的不只是数。）

By sorting the matrix so all 1s are in the top-right, I hope to then provide a ranking of the intrinsic difficulty of each challenge and a ranking of the competitors (which will take into account the difficulty of the challenges they succeeded at, not just the number of successes.)

注意上公认的答案：我已经接受模拟退火为答案需要提醒的是这个问题并没有一个正确的答案。这似乎是一个很好的方法，虽然我还没有真正设法拿出一个计分函数适用于我的问题。

Note on accepted answer: I've accepted Simulated Annealing as "the answer" with the caveat that this question doesn't have a right answer. It seems like a good approach, though I haven't actually managed to come up with a scoring function that works for my problem.

推荐答案

根据模拟退火算法可以处理这样的事情没有的太的麻烦。不是很大，如果你有小阵其中最有可能HAE一个固定的解决方案，但巨大的，如果你的矩阵得到更大，这个问题变得更加困难。

An Algorithm based upon simulated annealing can handle this sort of thing without too much trouble. Not great if you have small matrices which most likely hae a fixed solution, but great if your matrices get to be larger and the problem becomes more difficult.

（但是，它也失败的愿望，即插入可以逐步完成的。）

(However, it also fails your desire that insertions can be done incrementally.)

preliminaries

1. 设计一个性能功能得分矩阵 - 矩阵更接近你的triangleness应该得到一个更好的成绩比那些较少三角形-Y

1. Devise a performance function that "scores" a matrix - matrices that are closer to your triangleness should get a better score than those that are less triangle-y.

制定一套被的允许的的矩阵运算。您的描述是有点暧昧，但如果你能换行再一个运会 SwapRows（A，B）。另一种可能是 SwapCols（A，B）。

Devise a set of operations that are allowed on the matrix. Your description was a little ambiguous, but if you can swap rows then one op would be SwapRows(a, b). Another could be SwapCols(a, b).

的退火循环

我不会给一个完整的论述在这里，但这个想法很简单。您在使用操作矩阵进行随机变换。你测量有多少更好的矩阵是在手术后（使用性能的功能之前和之后的操作）。然后你决定是否要提交这一转变。你重复这一过程的很多

I won't give a full exposition here, but the idea is simple. You perform random transformations on the matrix using your operations. You measure how much "better" the matrix is after the operation (using the performance function before and after the operation). Then you decide whether to commit that transformation. You repeat this process a lot.

决定是否提交的变换是最有趣的部分：您需要决定是否执行该操作与否。对退火过程结束时，你只接受转换，这提高了矩阵的得分。但早些时候，在一个更​​加混乱的时候，你让不提高分数转换。一开始，该算法是热和任何事情都会发生。最终，该算法冷却，只有良好的转换是允许的。如果线性地冷却该算法，那么是否接受一个变换的选择是：

Deciding whether to commit the transform is the fun part: you need to decide whether to perform that operation or not. Toward the end of the annealing process, you only accept transformations that improved the score of the matrix. But earlier on, in a more chaotic time, you allow transformations that don't improve the score. In the beginning, the algorithm is "hot" and anything goes. Eventually, the algorithm cools and only good transforms are allowed. If you linearly cool the algorithm, then the choice of whether to accept a transformation is:

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

您应该阅读包含在数值方法优秀的信息，这种算法的详细信息

You should read the excellent information contained in Numerical Recipes for more information on this algorithm.

长话短说，你应该学会其中的一些通用算法。这样做将使您解决大班是很难的问题要解决解析。

Long story short, you should learn some of these general purpose algorithms. Doing so will allow you to solve large classes of problems that are hard to solve analytically.

评分算法

这可能是最棘手的部分。您将要设计一个得分手，指导退火过程向着你的目标。在射手应该是一个连续的功能，导致更大的数字为基体接近理想的解决方案。

This is probably the trickiest part. You will want to devise a scorer that guides the annealing process toward your goal. The scorer should be a continuous function that results in larger numbers as the matrix approaches the ideal solution.

你如何衡量理想的解决方案 - triangleness？这里是一个幼稚和简单的射手：对于每一个点，你知道它应该是 1 或 0 。添加+1将比分如果矩阵是正确的，-1，如果它是错的。下面是一些code这样我就可以明确的（未测试！请查看！）

How do you measure the "ideal solution" - triangleness? Here is a naive and easy scorer: For every point, you know whether it should be 1 or 0. Add +1 to the score if the matrix is right, -1 if it's wrong. Here's some code so I can be explicit (not tested! please review!)

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的对立的三角地带将给予最负分，和正确的解决方案将给予最积极的得分。进行比较的两个分数会给你的成本。

With this scoring algorithm, a random field of 1s and 0s will give a score of 0. An "opposite" triangle will give the most negative score, and the correct solution will give the most positive score. Diffing two scores will give you the cost.

如果这个射手不会为你工作，那么你将需要调整，直到它产生你想要的矩阵。

If this scorer doesn't work for you, then you will need to "tune" it until it produces the matrices you want.

这个算法是基于premise了调整此射手比制定最优的算法排序的矩阵要简单得多。

这篇关于排序二元二维矩阵？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！